陥没地帯 (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$ 数を要素として含まないものはいくつあるか?

【解】
問の部分集合を $S$ とし, その $k$ 個の要素を小さいものから順に, $s_1$ , $s_1+s_2$ , $s_1+s_2+ s_3$ , $\cdots$ , $s_1+ s_2+ \cdots + s_k$ とし, さらに $s_{k+1} = r -(s_1+ s_2 + \cdots + s_k)$ とすると,

$s_1+ s_2 +\cdots + s_k + s_{k+1} = r$
$s_1 \geq 1$ , $s_2 \geq 2$ , $\cdots$ , $s_k \geq 2$ , $s_{k+1} \geq 0$

となる. ここでさらに,

$x_1= s_1-1$ , $x_2 = s_2-2$ , $\cdots$ , $x_k = s_k -2$ , $x_{k+1} = s_{k+1}$

とすると,

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

の負でない整数解が, $x_1, \cdots, x_{k+1}$ となる. 求める部分集合の数は,

${}_{r-k+1}\mathrm{C}_{k}$

となる.//

結果はわかったが, 重複組合せでは仕切り棒を使うのでそれを使って別のやり方で証明してみる.

具体的な方がわかりやすいので, 数字は, $1$ から $15$ までにし, $4$ つの数字を隣あわないように選択することにしよう.

$**|**|***|*|***$

上の図はちょっとわかりにくいが, 左から数字の $1$ から $15$ が順に並んでいると考えて欲しい. $*$ は選択しない数字を表わし, $|$ は選択する数字を表わす. この例では, 選択する数字は, $3$ , $6$ , $10$ , $12$ の $4$ つである.

問題の条件で数字は隣あわないのだから, 最初から $3$ つの $|$ のすぐ右にある $*$ は必ずないとそもそも問題の条件をみたさない. だから、数学的には過剰な要素なので省略することにする.

$**|*|**||***$

少しわかりにくくなったかもしれないが, 最初の $3$ つの $|$ のすぐ右隣の $*$ は省略されていることがわかっていれば, 論理的には前の図と同じことである.

それで, この図は $*$ が $4-1=3$ つ減っているが, この図で組合せ,

${}_{15-4+1}\mathrm{C}_{4}$

を求めれば, 上と同じ結果が得られていることがわかると思う.

以上から, 選択する数字が, $k$ 個だったら, $r-k+1$ 個の数字から, $k$ 個の数字を選ぶ組合せ ${}_{r-k+1}\mathrm{C}_{k}$ を計算すればよいということである. //

※
意外と簡単なことがわかったので, 調子に乗って, 今度は円周上に数字 (整数) を $1$ から $r$ まで順に並べて, やはり隣りあわない $k$ 個の数字を選択するやり方が何通りあるか, 考えてみる.

まず, 最初の数字を $1$ つ選択する. これには, $r$ 通りある. 残り $k-1$ 個の数字を選択するのであるが, 選択する数字が隣接しないという条件を考えると, 直線に並べるときとは様子が違って, 今回は隣接しない条件のために省略する数字の個数は全部で $k$ 個になる. そうすると, 最終的に残った $r-k-1$ 個の数字から $k-1$ 個の数字を選ぶので,

${}_{r-k-1}\mathrm{C}_{k-1}$

となる. 次に最初に選択する数字を順に変更することで, 場合の数 $r$ をかけるが, 同じ数字の組合せが $k$ 回出現するので, さらに $k$ で割ると求める場合の数が得られる (たとえば, $k=3$ , $r = 8$ として, $(1,4,7)$ , $(4,7,1)$ , $(7,1,4)$ は同じ選択の組である). 以上から,

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

※ この場合はむしろ, 最初のように整数解の個数で考えた方がわかりやすいかもしれない. 選択する最初の要素をどれかに決め, $2$ 番目に選択する要素との間に存在する要素の個数を $x_1$ とし, 以下同様に $k$ 番目の選択要素と最初の要素の間にある要素の個数を $x_k$ とする. そうすると,

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

で, 選択要素がどれも隣りあわないことから, $x_1, x_2, \cdots x_k$ は,すべて正の整数でないといけない. したがって $x_1, \ x_2, \cdots, \ x_k$ の解の組は,

${}_{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} }$

が得られる.
//

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