要素数nの集合Aから要素数kの集合Bへの関数が全射となるようなものの個数を考える問題についてです。(

要素数nの集合Aから要素数kの集合Bへの関数が全射となるようなものの個数を考える問題についてです。(n>k)

私は、まずnこの要素のうちk個の要素をBのk個の要素に一対一で対応させて、残りのn-k個の要素をBの任意の要素に対応させることで、全射な関数を生成しようとしたのですが、そうして作成した場合、関数の総数は
nCk • k! • k^(n-k)
個になると思っていたのですが、一般に知られている全射の総数の定理とは違ったものになってしまいました。

おそらく考え方に誤解があってのこととは思うのですが、自分で訂正ができませんでした。

どこに勘違いがあるのか指摘頂けると助かります。

No.1 ベストアンサー 回答者： ありものがたり 回答日時： 2019/09/26 21:54

その数え方だと、例えば A の元 x,y,z が B の元 v に対応する関数は、

最初に A の元のうち k 個の対応先を考えた時に x→v としてから、Aの残りの元の対応先を y→v, z→v とした場合と
最初に y→v としてから x→v, z→v とした場合、最初に z→v としてから x→v, y→v とした場合で
3重に数えられてしまっている。

この回答へのお礼

回答ありがとうございました

お礼日時：2019/09/27 06:45

No.2 回答者： tknakamuri 回答日時： 2019/09/26 22:35

例えば、集合Aが2個、集合Bが1個の場合

あなたの式だと
2C1・1!・1^1=2

しかし、この問題はn個の区別できる球を
k個の区別できる(球を1個以上合む)グループに分けるのと同じことなので
k=1では常にー通り。

n=2、k=1 をあなたの考え方に沿って考えると

A1→B1、A2→B1
という写像と
A2→B1、A1→B1
という写像を別の写像と捉えている。
これはまずい。


https://mathtrain.jp/zensya

この回答へのお礼

回答ありがとうございました

お礼日時：2019/09/27 06:45