■記事リスト / ▼下のスレッド
| ■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!通りかと思うのですがどうやって解答すればいいのか分かりません。
|
|
|
▽[全レス2件(ResNo.1-2 表示)]
| ■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]!}
となると考えられます。
|
|
|
| ■47771 / ResNo.2) |
Re[2]: 全射の個数を求める問題
|
□投稿者/ Ali 一般人(2回)-(2016/10/04(Tue) 05:11:57)
| 有難うございます。お蔭様でとても参考になりました。
|
|
|
■記事リスト /
レス記事表示 →
[親記事-2]
|
で表示されます。
で表示されます。
ベクトルについて。(1)