前の記事からの流れでメナージュの問題関連について考察する.
この記事では, 重複組合せについて重要な基本を復習しておくことにする.
, を正の整数としたときに, 未知数 に関する方程式,
の負でない整数解の個数は, 重複組合せにより,
となる.
これから, 正の整数解をもつ個数を求めたければ,
とおいて,
とすれば, と は一対一対応しているので, 正の整数解の個数は,
となる. 以上のことを基本にして, 次の問題を考える.
【問】
集合 の 個の要素をもつ部分集合のうち, 隣あう 数を要素として含まないものはいくつあるか?
【解】
部分集合の 個の要素を とし, それぞれの要素の間と両端に入る の要素の個数を とする. 要素は小さい順に並べるとする.
このとき,
で,
である. について
とおくと,
で,
となり, 整数解の順序対の個数は,
となる.//
今度は円周上に数字 (整数) を から まで順に並べて, やはり隣りあわないように 個の数字を選択するやり方が何通りあるか, 考えてみる.
選択する最初の要素をどれかに決め, 番目に選択する要素との間に存在する要素の個数を とし, 以下同様に 番目の選択要素と最初の要素の間にある要素の個数を とする. そうすると,
で,
でないといけない. したがって の解の組は,
通りできる. 最初の選択要素を から までひとつずつ変更していくが, 円順列のため 個選択した要素の順序対に長さ の巡回置換をしたものはみな同一視される。したがって, をかければ, 円周に並べた 個のものから隣りあわないように 個を選択する場合の数,
が得られる.
//
これで, メナージュ問題の 「ご婦人方からお先に解」へ大分近づいた.