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

論　　理 授　　業
文字 "a" を r 個，"b" を nーr 個，重複して並べるとき，
何通りの文字列ができるか？
文字 "a" を 3 個，"b" を 4 個，重複して並べるとき，
何通りの文字列ができるか？
n 個の "a" と nーr 個の "b" に番号を付ける：
    v : { 1, ‥‥, n } ─→ { a, b }
    v(1) = ‥‥ = v(r) = a
    v(r+1) = ‥‥ = v(n) = b
番号を付けた a, b を横一列に並べることは，p1, ‥‥, pn を n 個の位置として，つぎの写像で表現される：
    f : { p1, ‥‥, pn } ─→ { 1, ‥‥, n } (１対１）に対する，
    f·v ： pi ─→ v(f(pi))　(i = 1, ‥‥, n )
    （ 意味：「場所 pi には，番号 f(pi) の文字 v(f(pi) を置く」)
このとき，異なる f·v の個数が，n 個の "a" と nーr 個の "b" を重複して並べるときの異なる文字列の個数となる。
異なる f·v 全体の集合を S で表す。 		3 個の "a" と 4 個の "b" に番号を付ける：
    a1, a2, a3, b4, b5, b6, b7
番号 1, 2, ‥‥, 7 を横一列にいろいろな順番で並べるとき，その番号のついた文字が「3 個の a と 4 個の b の文字列」をいろいろつくる：
    b a a b b b a
    ↑↑↑↑↑↑↑
    b5 a3 a1 b7 b4 b6 a2
    ↑↑↑↑↑↑↑
    5 3 1 7 4 6 2
{ p1, ‥‥, pn } から { 1, ‥‥, n } への１対１写像全体を，F で表す。
この F を
    Fs = { f ∈ F | f·v = s }　 (s ∈ S)
で分割する：
　(1)　Ｆ＝ U{ Fs | s ∈ S } 		番号 1, 2, ‥‥, 7 の並び方は 7! 通りある。
この並び方全体を，「同じ文字列をつくる番号の並び方」で仲間分けする：
    例えば，1, 4, 2, 5, 6, 3, 7 と 2, 4, 1, 5, 6, 3, 7 は同じ文字列 a b a b b a b をつくるので，同じ仲間。
    1, 2, 4, 5, 6, 3, 7 はこれと違う文字列 a a b b b a b をつくるので，これとは違う仲間。
このとき，
　(2)　Fs の要素の数は，r! × (nーr)!
    理由：
    f·v ∈ Fs に対し，つぎのようにおく：
      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 : { p1, ‥‥, pn } ─→ { 1, ‥‥, n } (１対１）は，つぎの形をしている：

      f | Pa : Pa ─→ Va　(１対１)
      f | Pb : Pb ─→ Vb　(１対１)


    １対１対応：Pa ─→ Va は r! 通りある。
    １対１対応：Pb ─→ Vb は (nーr)! 通りある。
    よって，f （すなわち，f·v ∈ Fs となる f ) は，r! × (nーr)! 通りある。
    そしてこのことから，Fs の要素の数は，r! × (nーr)!
同じ仲間になる番号 1, 2, ‥‥, 7 の並び方は，3! × 4! ある。
    理由：
    たとえば，文字列 a b a b b a b をつくる番号の並び方が何通りあるか，考えてみる。

      a b a b b a b
      ↑↑↑↑↑↑↑
      m1 n1 m2 n2 n3 m3 n4

    番号 m1, m2, m3 には，1, 2 , 3 が並ぶ。これは 3! 通り。
    番号 n1, n2, n3, n4 には，4, 5 , 6, 7 が並ぶ。これは 4! 通り。
(1) と (2) より，
    F の要素数 = (r! × (nーr)!) × ( S の要素数 )

F の要素数は n! だから，
    S の要素数 ＝ n!
    r! × (nーr)!)    		 （＝ nCr)
すなわち，
    n 個の "a" と nーr 個の "b" を重複して並べるときの異なる文字列の個数 ＝ nCr
番号 1, 2, ‥‥, 7 の並び方は 7! 個あるが，これを「同じ文字列をつくる番号の並び方」で仲間分けしたとき，各グループに属する番号の並び方は 3! × 4! 個。
よって，
    7! = (3! × 4!) × (グループの数)
すなわち，
    グループの数 ＝ 7! / (3! × 4!)
グループの数は，異なる文字列の数と同じだから，
    異なる文字列の数 ＝ 7! / (3! × 4!)