全射の総数

質問

|X|=4、|Y|=3であるとき、写像f：X→Yで全射になる写像の総数はいくらか

この回答は36なのですが、考え方が良くわかりません、誰か教えてください、お願いします

回答No.2

starflora · ベストアンサー

この問題に関しての回答でよいということなら記します。

　　ＸとＹは、要素の差が１しかありません。これがもっとたくさんだと、計算が複雑で解きにくいのですが、ここでは、差１なので、順列組み合わせの考え方を使います。

　　Ｙの要素は３個ですから、これを三つの位置と考え、この位置に、Ｘの四つの要素を入れて行くことにします。この場合、Ｘの要素のどれか二つが、Ｙの同じ位置に入ることになります。そこで、Ｘの要素から二つを組み合わせる可能性の数を考えると、それは４・３で１２ですが、これは順列でないので、２で割ると６が出てきます。

　　Ｘの四個の要素のなかで、二つを選ぶと、残りの二個は自動的に決まります。つまり、６通りに分けて、それぞれ要素が違う三つの要素があると考えてよいのです。こう言っても分かりにくいかも知れませんから、具体的に、その６通りを以下に書いてみます。Ｘ＝｛ａ，ｂ，ｃ，ｄ｝とします。

　　ケース１）｛（ａ，ｂ），ｃ，ｄ｝
　　ケース２）｛（ａ，ｃ），ｂ，ｄ｝
　　ケース３）｛（ａ，ｄ），ｂ，ｃ｝
　　ケース４）｛（ｂ，ｃ），ａ，ｄ｝
　　ケース５）｛（ｂ，ｄ），ａ，ｃ｝
　　ケース６）｛（ｃ，ｄ），ａ，ｂ｝

　　これら６個のケースは、すべて要素が違う集合と考えても構いません。Ｙの三つの要素の位置に、これら６ケースごとで、三つの要素を入れて行く（対応させて行く）ことを考えると、これが、Ｘ→Ｙの全射になります。６個のケースで、三つの要素の順列を入れ替えても、６個のケースで、同じ、重複した順序はできません。

　　従って、Ｙの三つの位置に対する順列を取ると、３・２・１＝６で、これと、ケースの数６をかけると、６・６＝３６になり、これが、答えです。

　　注記）六個のケースの三つの要素（二つの要素の組み合わせで、一つの新しい要素を造っていることに注意）の順列をどう入れ替えても、６個のケース全体で、同じ重複した組み合わせはできないというのがポイントです。「二重要素」を定義しているので、重複が排除されるのです。

回答No.1

hitomura

|X|はXの要素数という意味でしょうか？
ここではそうだと解釈します。

X={a,b,c,d},Y={x,y,z}とします。
fは全射ですからf(X)=Yとなります。
つまり、f(a),f(b),f(c),f(d)のいずれかはxでいずれかはyでいずれかはzとなります。

これは、f(a),f(b),f(c),f(d)のいずれか２つは同じ値になることをあらわします。
その同じ値となるXの元の組み合わせは(4*3)/(2*1)=6通りとなります。

つぎに、同じ値となるXの元、それ以外の値となるXの元(アルファベット順で若い方)、それ以外の値となるXの元(アルファベット順で後の方)がそれぞれfによってYのどの値に移されるかを考えると、これは順列となるので、可能性としては3*2*1=6通りとなります。

以上の可能性を掛け合わせると、写像f：X→Yで全射になる写像の総数が出てきます。

補足

これは、f(a),f(b),f(c),f(d)のいずれか２つは同じ値になることをあらわします。
その同じ値となるXの元の組み合わせは(4*3)/(2*1)=6通りとなります。

ここがよく分からないのですが...