ノリの悪い日記

古今東西の映画、ポピュラー音楽、その他をいまここに交錯させながら随想します。

陥没地帯 (269)

前の記事からの流れでメナージュの問題関連について考察する.

この記事では, 重複組合せについて重要な基本を復習しておくことにする.

 n,  r を正の整数としたときに, 未知数  x_1,x_2, \cdots , x_n に関する方程式,

 x_1+ x_2+ \cdots + x_n = r

の負でない整数解の個数は, 重複組合せにより,

 {}_{n + r -1}\mathrm{C}_{r}= {}_{n + r -1}\mathrm{C}_{n-1}

となる.

これから, 正の整数解をもつ個数を求めたければ,

 x_i = x_i'+1 とおいて,

 x_1' + x_2' + \cdots + x_n' = r -n

とすれば,  x_i x_i' は一対一対応しているので, 正の整数解の個数は,

 {}_{n + (r-n) -1}\mathrm{C}_{r-n}= {}_{r-1}\mathrm{C}_{r-n}= {}_{r-1}\mathrm{C}_{n-1}

となる. 以上のことを基本にして, 次の問題を考える.

【問】
集合  X =\{1, 2, \cdots , r\}  k 個の要素をもつ部分集合のうち, 隣あう 2 数を要素として含まないものはいくつあるか?

【解】
部分集合の  k 個の要素を  s_1, \cdots, s_k とし, それぞれの要素の間と両端に入る  X の要素の個数を  x_1, x_2, \cdots, x_{k+1} とする. 要素は小さい順に並べるとする.

 x_1, s_1, x_2,s_2, \cdots , x_k, s_k, x_{k+1}

このとき,

 x_1+ x_2 + \cdots + x_{k+1} = r - k

で,

 x_1, x_{k+1} \geq 0
 x_2, \cdots, x_k > 0

である.  2 \leq i \leq k について

 x_i' = x_i + 1

とおくと,

 x_1+ x_2' + \cdots + x_k' + x_{k+1} = r - 2k+1

で,

 x_1, x_2',\cdots, x_k', x_{k+1} \geq 0

となり, 整数解の順序対の個数は,

 {}_{k+1}\mathrm{H}_{r-2k+1} = {}_{r-k+1}\mathrm{C}_{k}

となる.//

今度は円周上に数字 (整数) を  1 から  r まで順に並べて, やはり隣りあわないように  k 個の数字を選択するやり方が何通りあるか, 考えてみる.

選択する最初の要素をどれかに決め,  2 番目に選択する要素との間に存在する要素の個数を  x_1 とし, 以下同様に  k 番目の選択要素と最初の要素の間にある要素の個数を  x_k とする. そうすると,

 x_1 + x_2 + \cdots + x_k = r - k

で,

 x_1, x_2, \cdots x_k >0

でないといけない. したがって  x_1, \ x_2, \cdots, \ x_k の解の組は,

 {}_{k}\mathrm{H}_{r-2k} = {}_{r-k-1}\mathrm{C}_{r-2k}={}_{r-k-1}\mathrm{C}_{k-1}

通りできる. 最初の選択要素を  1 から r までひとつずつ変更していくが, 円順列のため  k 個選択した要素の順序対に長さ k の巡回置換をしたものはみな同一視される。したがって,  r/k をかければ, 円周に並べた  r 個のものから隣りあわないように  k 個を選択する場合の数,

 \displaystyle{
\frac{r}{k}\cdot{}_{r-k-1}\mathrm{C}_{k-1} = \frac{r}{r-k}\cdot {}_{r-k}\mathrm{C}_{k}
}

が得られる.
//

これで, メナージュ問題の 「ご婦人方からお先に解」へ大分近づいた.