陥没地帯 (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+ a_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$ , $x_2 = s_2-1$ , $\cdots$ , $x_k = s_k -1$ , $x_{k+1} = s_{k+1} +1$

とすると,

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

の正の整数解が, $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-1$ 個の選択数字すべてについて一つ必要なことがわかる. 隣接しない条件のために必ず必要な数字の個数は全部で $k$ 個になる. そうすると, 残った $r-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}$

通りできる. 最初の要素の選択の仕方は, $r$ 通りあるが, 最初の要素を $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} }$

が得られる.
//

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