数学ナビゲーター掲示板

HOME HELP 新規作成 新着記事 ツリー表示 スレッド表示 トピック表示 発言ランク ファイル一覧 検索 過去ログ

■47768 / 親記事)  全射の個数を求める問題
  
□投稿者/ Ali 一般人(1回)-(2016/09/27(Tue) 03:53:24)
    下記の問題を教えてください。

    m≦nとする。
    f:{1,2,…n}→{1,2,…,m}で#f^-1(1)=n_1,#f^-1(2)=n_2,…,#f^-1(m)=n_m (n_1+n_2+…+n_m=n)となるような全射fは何通りあるか。
    #f^-1(1)=n_1は1の逆像の要素の個数を表してます。

    多分,n_1!n_2!…n_m!通りかと思うのですがどうやって解答すればいいのか分かりません。
引用返信/返信 [メール受信/OFF] 削除キー/
■47770 / ResNo.1)  Re[1]: 全射の個数を求める問題
□投稿者/ WIZ 一般人(2回)-(2016/09/28(Wed) 01:21:44)
    逆写像や逆関数をf^(-1)と表現することは個人的に誤解を招くものだと考えていますので、
    私の回答ではinv_fと表現させて頂きます。
    また添え字付きの文字についてもn_1ではなく、n[1]と表記させて頂きます。
    組み合わせ(コンビネーション)をC(n,r)と表記することとします。
    階乗演算子!は四則演算よりも優先度が高いものとします。

    先ず具体的な例で数えてみて、推論してみましょう。
    n = 3, m = 2, #inv_f(1) = n[1] = 1, #inv_f(2) = n[2] = 2とします。
    {f(1),f(2),f(3)}としては{1,2,2}{2,1,2}{2,2,1}の3通りとなりますので、
    n[1]!n[2]! = 1!2! = 2とは異なり、スレ主さんの予想した解は誤りということになります。

    {f(1),f(2),・・・,f(n)}のn個の中からn[1]個選んで、その値を1とする。
    この選び方は、C(n,n[1])通り。

    残りのn-n[1]個の中からn[2]個選んで、その値を2とする。
    この選び方は、C(n-n[1],n[2])通り。

    残りのn-n[1]-n[2]個の中からn[3]個選んで、その値を3とする。
    この選び方は、C(n-n[1]-n[2],n[3])通り。

    ・・・・・・

    残りのn-n[1]-n[2]-・・・-n[m-2]個の中からn[m-1]個選んで、その値をm-1とする。
    この選び方は、C(n-n[1]-n[2]-・・・-n[m-2],n[m-1])通り。

    残りのn-n[1]-n[2]-・・・-n[m-1]個の中からn[m]個選んで、その値をmとする。
    この選び方は、C(n-n[1]-n[2]-・・・-n[m-1],n[m])通り。

    但し、最後の選び方の数はn-n[1]-n[2]-・・・-n[m-1] = n[m]より、C(n[m],n[m]) = 1固定ですが。

    以上から、何通りあるかの数は、
    C(n,n[1])*C(n-n[1],n[2])*・・・*C(n-n[1]-n[2]-・・・-n[m-1],n[m])
    = {n!/{n[1]!(n-n[1])!}}{(n-n[1])!/{n[2]!(n-n[1]-n[2])!}}*・・・*{(n-n[1]-n[2]-・・・-n[m-1])!/{n[m]!(n-n[1]-n[2]-・・・-n[m])!}}
    = n!/{n[1]!n[2]!*・・・*n[m]!}
    となると考えられます。
引用返信/返信 [メール受信/OFF] 削除キー/
■47771 / ResNo.2)  Re[2]: 全射の個数を求める問題
□投稿者/ Ali 一般人(2回)-(2016/10/04(Tue) 05:11:57)
    有難うございます。お蔭様でとても参考になりました。
引用返信/返信 [メール受信/OFF] 削除キー/



スレッド内ページ移動 / << 0 >>

このスレッドに書きこむ

Mode/  Pass/

HOME HELP 新規作成 新着記事 ツリー表示 スレッド表示 トピック表示 発言ランク ファイル一覧 検索 過去ログ

- Child Tree -
Edit By 数学ナビゲーター