陥没地帯 (270) - ノリの悪い日記

記事 $(268)$ がきっかけで, メナージュの問題 *1について書いている. 直前の記事を使って, 記事 $(268)$ の入試問題における大人 $n$ 人, 子ども $n$ 人のときの子どもの配置の仕方は,

$\displaystyle{ \sum_{i=0}^n(-1)^i \frac{2n}{2n-i}\cdot {}_{2n-i}\mathrm{C}_i\cdot(n-i)!}$

通りであることを示す. 証明は, 高校数学でも場合の数のところで必ず習う, 集合の包除原理を使ってなされる. 見事な数え上げだと思う.

【証明】

まず, 大人の並び方をひとつ固定し, $n =5$ であれば, $5$ 人の子どもを配置する場所は

$1A2B3C4D5E1$

のアルファベット文字 $A$ から $E$ の場所である. まず, 子どもの配置が禁じられる条件を以下のように $10$ (一般には $2n$ ) 個作る. この禁じられた条件につける $1$ から $2n$ までの番号こそが, 実はこの数え上げの鍵なのである. $n =5$ として書き下してみる.

$1:$ 子ども $1$ が場所 $E$ にいる.
$2:$ 子ども $1$ が場所 $A$ にいる.
$3:$ 子ども $2$ が場所 $A$ にいる.
$4:$ 子ども $2$ が場所 $B$ にいる.
$5:$ 子ども $3$ が場所 $B$ にいる.
$6:$ 子ども $3$ が場所 $C$ にいる.
$7:$ 子ども $4$ が場所 $C$ にいる.
$8:$ 子ども $4$ が場所 $D$ にいる.
$9:$ 子ども $5$ が場所 $D$ にいる.
$10:$ 子ども $5$ が場所 $E$ にいる.

上の禁じられた条件のリストで, たとえば, $1$ と $2$ は排反の条件であることがわかる. $2$ と $3$ も排反である. $10$ と $1$ も排反である. つまりこのように禁じられた条件のリストを作れば, 隣接する条件番号はみな排反で, 実際の配置として同時には作りえないものばかりである. 一般には禁じられた条件の $1$ から $2n$ までの条件番号を円周上に並べたとき, そこから番号が隣りあわないようにして $i$ 個の番号を選択すれば, 禁じられた配置を作ることができる. そのような選択の仕方が何通りあるかは, 直前の記事の最後ですでに求めてある. その式の $r$ に $2n$ を $k$ に $i$ を代入すれば,

$\displaystyle{ \frac{2n}{2n-i}\cdot {}_{2n-i}\mathrm{C}_{i} }$

通りである. 選択した $i$ 個の条件によって子どもを $i$ 人配置すると残る $n -i$ の場所に子どもを配置する仕方は制約のない $(n-i)!$ 通りある. つまり,

$\displaystyle{ \frac{2n}{2n-i}\cdot {}_{2n-i}\mathrm{C}_{i}\cdot(n-i)! }$

は, 隣りあわない禁止条件を $i$ 個選択したときの, 子どもの配置として許されないものの総数である (もちろん他の条件と重複して数えている配置が存在する).

あとは集合の包除原理を使えばよい. 大人と子どもが交互に並ぶ以外に, 何も条件を課さない子どものならび方は, 大人の配置をひとつ固定すれば, $n!$ 通りである ( $i = 0$ の場合に相当). 求める子どもの配置数は, $n!$ から, 条件 $1$ , または, 条件 $2$ , または, $\cdots$ , または, 条件 $2n$ が当てはまる禁じられた子どもの並び方の総数を引いたものである.

集合の包除原理を $3$ つの集合の和集合について書くと,

$n(A \cup B\cup C) \\= n(A)+ n(B) + n(C) -n(A \cap B) \\ \quad - n(B \cap C) - n (C \cap A) \\ \quad + n(A \cap B \cap C)$

この包除原理は, $3$ つの集合よりも多い和集合の場合でも成立する.

以上から, 大人 $n$ 人, 子ども $n$ 人のとき, 大人の配置を最初にひとつ固定すると, 子どもの配置の仕方は,

$\displaystyle{ \sum_{i=0}^n (-1)^i \frac{2n}{2n-i}\cdot {}_{2n-i}\mathrm{C}_i\cdot (n-i)!}$

通りあることが証明できた.
//

*1:メナージュはフランス語で, この場合「夫婦」の意味であるが「夫婦の問題」あるいは「伴侶の問題」などと書くのは何か妙な, 場違いな感じがしなくもないので, 「メナージュの問題」とする. 宮崎大の入試問題は性差別撤廃の実現のために問題の設定を大人と子どもに変えたのかもしれない. ただ, 問題の優雅さが若干損なわれた感がしてしまうのは, ことによると背番号を大人と子どもがつけて手をつなぐという秋の大運動会のような新たな状況設定によるせいかもしれない.