単射の総数

質問

|A|=m,|B|=n(m<_n)のときの単射f：A→Bの総数を求めよ

この考え方もわかりません　どなたか教えてください

回答No.3

hitomura · ベストアンサー

＞どうしてf(a(m))の取りうる値はn-m+1通り　なのですか？
単写、という言葉の意味は分かりますよね？念のため書きますが
　a≠bならばf(a)≠f(b)
という意味です。

f(a(1))のとりうる値の種類はBの要素数のn個です。
f(a(2))のとりうる値の種類は集合Bからf(a(1))の値として選んだ値を除いた集合の個数であるn-1個です。
f(a(3))のとりうる値の種類は「集合Bからf(a(1))の値として選んだ値を除いた集合」から(a(2))の値として選んだ値を除いた集合の個数である(n-1)-1=n-2個です。
f(a(3))のとりうる値の種類は…

ということをa(m)まで繰り返していけば、a(m)のとりうる値の種類がn-m+1個になることが分かります。

なお、上の「…」で省略した部分が分からない、といわれても、私にはそこをやっていく根気はありません。

回答No.2

starflora

これは単射の問題なので、そのまま考えます。ｍ＜＝ｎというのが条件だと理解します。

　　Ｂの要素のなかで、ｎ－ｍ個が、写像とは関係のない、対応要素のない要素になります。従って、これを排除して考えるのがよいことになります。こういうｎ－ｍ要素を外した、Ｂの部分集合の異なる可能性の数は、ｎから任意にｎ－ｍ個の要素を選ぶ組み合わせです。これは、nＣn-mです。具体的には、n(n-1)(n-2)……(n-m+1)／m！＝nＰn-m／m！＝ｒです。（ｒは適当な文字です）。

　　要素が違うｒ個の集合があるということになり、濃度は、Ａと同じです。

　　このｒ個の集合のそれぞれに対し，Ａからの単射があることになります。その単射の組み合わせ数は、ｍ！となります。

　　先のｒ個の集合は、みな異なる集合です。何故なら、どれも、最低、一個の要素が食い違っているからです。つまり、仮にＢから、｛ａ，ｂ｝要素と｛ａ，ｃ｝要素を除いた二つの集合を考えると、先にはｃがあるがｂがなく、後は、ｂはあるがｃがないという風に違った集合です。

　　ｒ個の集合をＢｒと表現すると（ｒ＝１，２，３……）、Ａ→Ｂｒの単射は、いかなる組み合わせを造っても、同じものはないということになります。何故なら、Ｂｒは、ｒが違えば、それぞれ別の集合だからです。

　　一般に別個のｍ個の要素からなる集合から、同じように、別個のｍ個の集合への単射の数は、すでに上でも述べたように、ｍ！です。従って、Ａに対するＢｒの数をかければ、これが、問題の答えです。すなわち、（nＣn-m）Ｘ（ｍ！）です。ところで、nＣn-m というのは、nＰn-m／ｍ！です。これにｍ！をかけるのですから、答えは、nＰn-m です。

　　回答：　nＰ(n-m)

回答No.1

hitomura

http://oshiete1.goo.ne.jp/kotaeru.php3?q=209227
のほうでも書きましたが、|A|はAの要素数という意味でしょうか？
ここではそうだと解釈します。

A={a(1),a(2),…,a(m)}とします。すると、fは単車なので、
　f(a(1))の取りうる値はn通り、
　f(a(2))の取りうる値はn-1通り、
　　…
　f(a(m))の取りうる値はn-m+1通り、
となります。これを掛け合わせると、
　n*(n-1)*…*(n-m+1)={n*(n-1)*…*1}/{(n-m)*(n-m-1)*…*1}
　　　　　　　　　　=n!/(n-m)!
　　　　　　　　　　=nＰ(n-m)
となります(ただし、nＰ(n-m)のnおよびn-mは下添字)。

補足

どうしてf(a(m))の取りうる値はn-m+1通り　なのですか？