２つの文字をそれぞれ r 個と n- r 個重複して並べるときの 異なる文字列の数は，n!/(r! × (nーr)!) (＝nCr) に等しい

---

文字 "a" を r 個，"b" を nーr 個，重複して並べるとき，何通りの文字列ができるか？

この問題は高校数学の内容であるが，この解をきちんと論理的に導くことは，かなり難しい。
以下，数学の記号法を用いつつ，この解の導き方を示す。


n 個の "a" と nーr 個の "b" に番号を付ける：


v : { 1, ‥‥, n } ─→ { a, b }
v(1) = ‥‥ = v(r) = a
v(r+1) = ‥‥ = v(n) = b

番号を付けた a, b を横一列に並べることは，p₁, ‥‥, p_n を n 個の位置として，つぎの写像で表現される：


f : { p₁, ‥‥, p_n } ─→ { 1, ‥‥, n } (１対１）に対する，
f·v ： p_i ─→ v(f(p_i))　(i = 1, ‥‥, n )
（ 意味：「場所 p_i には，番号 f(p_i) の文字 v(f(p_i) を置く」)

そしてこのとき，異なる f·v の個数が，n 個の "a" と nーr 個の "b" を重複して並べるときの異なる文字列の個数となる。
異なる f·v 全体の集合を S で表す。

{ p₁, ‥‥, p_n } から { 1, ‥‥, n } への１対１写像全体を，F で表す。
この F を
F_s = { f ∈ F | f·v = s }　 (s ∈ S)
で分割する：
　(1)　Ｆ＝ U{ F_s | s ∈ S }

このとき，
　(2)　F_s の要素の数は，r! × (nーr)!


理由：
f·v ∈ F_s に対し，つぎのようにおく：

Pa = (f·v)-1(a)	(文字列 s で，文字 a が置かれている場所全体)
Pb = (f·v)-1(b)	(文字列 s で，文字 b が置かれている場所全体)

また，つぎのようにおく：

Va = v-1(a)	(文字 a に付いている番号全体)
Vb = v-1(b)	(文字 b に付いている番号全体)


このとき，f : { p₁, ‥‥, p_n } ─→ { 1, ‥‥, n } (１対１）は，つぎの形をしている：


f | P_a : P_a ─→ V_a　(１対１)
f | P_b : P_b ─→ V_b　(１対１)




１対１対応：P_a ─→ V_a は r! 通りある。
１対１対応：P_b ─→ V_b は (nーr)! 通りある。
よって，f （すなわち，f·v ∈ F_s となる f ) は，r! × (nーr)! 通りある。
そしてこのことから，F_s の要素の数は，r! × (nーr)!

(1) と (2) より，
F の要素数 = (r! × (nーr)!) × ( S の要素数 )

F の要素数は n! だから，

S の要素数 ＝

n! r! × (nーr)!)

（＝ nCr)

すなわち，
n 個の "a" と nーr 個の "b" を重複して並べるときの異なる文字列の個数 ＝ _nC_r