チェビシェフ多項式の係数計算で現れる二項係数の和の計算とメナージュ問題について（完全解決編）

ずっと気になっていた計算が、望んでいた解法で解くことができたたので、
またちょっとだけ殴り書きしておきます。

発端は私の記事「 直交多項式と超幾何関数(1)〜チェビシェフ多項式と三角関数〜 」において
私が計算に困っていたところでした。
その主張は以下のようなもので：

前回の記事「 チェビシェフ多項式の係数計算で現れる二項係数の和の計算について（準解決編） 」においては、母関数を用いた議論で証明を行なっていた。
母関数は組み合わせ論においては基礎的な理論であるが、
私はどうしても気にいらなかった。

もっと初等的な証明が欲しい！！

何が欲しかったというと、「全単射的証明」が欲しかったのだ。
ある対象を2通りの数え方をして、それが等しいことから等式を導く超古典的な手段。

例えば、
\begin{align*} \sum_{k=0}^n\binom{n}{k}=2^n \end{align*}
のような等式を、同じ「$n$個の0/1からなる文字列」に対して2通りに数えるというのはよく知られている。
「何個の数字が1か」というので分類すると、1の個数$k$個の場所を選ぶ$\binom{n}{k}$通りが出てきて
逆に「それぞれの場所が0/1の2通り」で考えると、$2$を$n$回掛けた$2^n$通りが出てくるのである。

全単射的解法による証明

さて、前置きはこのあたりにして、サクッと証明を述べてしまいたいと思う。
まず少し小細工をしておく。
$k=n/2$の時に$2^{n-2k-1}$のところが$1/2$になってしまって少し面倒であるので、両辺を2倍した
\begin{align*} 2\sum_{j=k}^{[n/2]}\binom{n}{2j}\binom{j}{k} =2^{n-2k}n\frac{(n-k-1)!}{k!(n-2k)!} \end{align*}
の等式を示すことにしたい。
さらに右辺を少し整理する。
\begin{align*} n\frac{(n-k-1)!}{k!(n-2k)!} =\frac{n}{n-k}\frac{(n-k)!}{k!(n-2k)!} =\frac{n}{n-k}\binom{n-k}{k} \end{align*}
したがって、我々が示すべき等式は次のように書き表せる。

数える対象

数える対象は、
「円の上に並んだ$1,2,\cdots, n$の場所の上に並べられた0/1の$n$個の組」と
「その中で1が連続している塊(1個でも塊と呼ぶ)を$k$個塗りつぶす」という
色彩&数字付き円環グラフを考えている。
(注：場所$n$と$1$は隣り合っていることを前提としている)

もちろん、
「1が連続している組が$k-1$個以下である」
みたいな定義を満たさないグラフは省いている。

左辺

さて、この輪の中には「0の塊」と「1の塊」が複数あると想定されている。
(まぁ$k=0$の場合は全てが「0の塊」であるような場合も許されるのだが、それは今は考えない)
すると
0の塊の後ろは1の塊が来て、1の塊の次はまた0の塊が来て、という感じになっている。
この
「0→1に切り替わる境界」と「1→0に切り替わる境界」は個数が等しい。
なぜなら1周で元に戻ってくるからである。

その「0→1」「1→0」それぞれの境界の数の個数を $j$個 とおく。
もちろん$j$は最多で、0と1が交互に並んでいる時を考えると、$[n/2]$個を取りうることがわかる。
この$j$をfixする。
すると
$n$個の「場所同士の間」(周回なので個数と間の数は同じ)の中で $2j$個の「0→1」「1→0」を選ぶ必要がある。
これが$\binom{n}{2j}$通りの選び方である。

次に、境界を選んだとしても、0/1の決め方は一意的ではない。
「全ての場所で0/1をひっくり返したもの」が同じ境界パターンを持つことがわかる。
逆に
どこか特定の境界で「0→1」「1→0」のどちらなのか決めてしまえば、自動的に全部の場所が決まる。
故にこのパターンの分だけ 2倍 する必要がある。

最後に、1の塊を$k$個彩色させる必要があるが、それは $\binom{j}{k}$通りとすぐにわかる。

あとは$j$を動かして和をとることによって左辺の値$\displaystyle 2\sum_{j=k}^{[n/2]}\binom{n}{2j}\binom{j}{k}$が出てくるとわかる。

右辺

左辺とは別の数え方をして右辺の値になることを示したい。

右辺を数える上ではほぼ答えになる、以下の補題を用意する。
でもこれは(突然与えたものではなく)意外と基本的な命題だったりする。

・・・一旦この補題の証明は後回しにしていいっすか！？！？$\quad$ #長い

でもこの補題を仮定すれば右辺はほぼ出来上がったようなもの。
ポイントは
「彩色された1の塊の最も左側」の$k$個は隣なっていない、ということである。
(右でもいいけどw)(どっち回りを左にするかによる)
その選び方が、Kaplanskyの補題により$\frac{n}{n-k}\binom{n-k}{k}$通りだとわかっている。

そして、その「今選んだ$k$個の"彩色された1の最も左側の1"」の左隣は「0に確定」する。
なぜなら、そこには「0→1の変化がある」からだ。
これによりトータル$2k$個の位置と色が確定した。

例えば、1とそこから右向きに来た次の0の間については何が言えるのか。
1の次は、別に1である必要はない。
なぜなら1の塊は単独でも1の塊になり得るからだ。
その後も、別に0や1が来ようが関係ない。1が来たとしても、それは「彩色されてない1の塊」になる。
ただし、その次の0のところは確実に0になっていることは今確定している。
でもその前が0だろうが1だろうが誰も気にしない。

という感じで、残りの(n-2k)個については0/1何であっても誰も気にしない。
$2^{n-2k}$通りである。

以上より右辺は$\displaystyle 2^{n-2k}\frac{n}{n-k}\binom{n-k}{k}$通りと数えられた。
これによって証明完了である。

本当は...

本当は、ここからこの数え方が「本当に全部を数えられているか」を見るために
左辺の数え方と右辺の数え方との間に「全単射の対応がある」ことを書き下す必要がある気がする。
だるい。嫌だ。笑
というか構成方法からほぼ明らかである。

補題の証明

さて、Kaplanskyの補題を示していくことにしよう。
I. Kaplansky (1943)「 Solution of the “Problème des ménages” 」では
メナージュ問題と呼ばれるある古典的な組み合わせ論の問題を解くために補題として使われている。

メナージュ問題が何かは最後においておき、補題の証明をしたい。

ちなみに、この補題の証明については
\begin{align*} (n-k)C(n,k)=n\binom{n-k}{k} \end{align*}
を全単射構成による証明で示すという手段も全然考えうるが一番簡単ではないと思う。

Problème des ménages (メナージュ問題) とは？

Ménageはフランス語で「家計・家事・夫婦・掃除」などの意味を有するが、今は「夫婦」という意味である。
問題は次のようなものである：

例えば、$n=1$の時、そのカップルはお互い向かい合って座るしかないので、条件に反する。$M(1)=0$である。
次に$n=2$の時とかは、どうなるであろうか。
ある男性を基準に考えてみると、両隣は女性でカップルは2組しかないので、自分の配偶者はどちらかに座ることになってしまう。ゆえにこれも条件に反して$M(2)=0$がわかる。

面白いのが、$n=3$の時にこれを満たす座らせ方は発生しうる。
カップルをAa、Bb、Ccって名前をつけると、「A・b・C・a・B・c」って座らせると条件を満たす。

さて、一般に$M(n)$はどうやって求めればいいのだろうか。

メナージュ問題の初出は意外な分野だった

初出はLucasの定式化よりも14年前、
物理学者ピーター・テイト(Peter Guthrie Tait)による結び目理論のある論文(1877)に端を有する。

Taitは「結び目を平面に投影し、交点に文字を付けて曲線を一周し、交点ラベルの出現順番を記録することで結び目図式を文字列に落としたい」ということを考えた。
その発想自体は19世紀頭のGaussから部分的にあったのだが、定式化したのはTaitが最初にはなる。
この枠組みはのちに
Reidemeister移動(1926-27)やAlexander多項式(1928)といった
現代位相幾何でも使われる材料へと繋がっていく流れではある。

どのような結び目がメナージュ型に繋がるのかという詳細は細かくは省くが、
ざっくり言うと
「交点があるように見えるが実はただの小さな輪っかを作っているだけで、少し動かせば消せる“余計な交点”」
みたいなものを除きたいという制約から、
「夫婦が隣り合わない」に比類する近接禁止の条件の個数を数えたくなったようである。

メナージュ問題の答え

さて、以下で証明を載せるために唐突であるがメナージュ問題の答え、すなわち$M(n)$の値を発表する：
\begin{align*} M(n)=(2\cdot n!) \sum_{k=0}^n(-1)^k\frac{2n}{2n-k}\binom{2n-k}{k}(n-k)! \end{align*}
なお最初の項の$2\cdot n!$は｢片方の性別｣の並べ方の数である。
仮に女性を先に並べるとして
・女性を｢奇数番号｣｢偶数番号｣どちらに座らせるかの$2$通り
・$n$人の女性の並べ方として$n!$通り
が考えられるからである。
そこでこの因子で割った残りを$U(n)$として定める。すなわち
\begin{align*} U(n)=\sum_{k=0}^n(-1)^k\frac{2n}{2n-k}\binom{2n-k}{k}(n-k)! \end{align*}
であることを示すことになる。

この$U(n)$は、男性の並べ方であるが、以下のような集合として言い直すことができる:
\begin{align*} U(n)=\#\{ \sigma\in\mathfrak{S}_n \mid {}^\forall i, \sigma(i)\neq i, \sigma(i)\neq i+1 \} \end{align*}
これは、｢$i+0.5$｣みたいな席に男性$i$の配偶者が座っているとする時、男性の座り先$\sigma(i)$は$i$でも$i+1$でもあってはならない、というのを置換群の言葉で言い直したに過ぎない。

ここからは、この$U(n)$の位数をどのように計算するのか見ていきたい。

メナージュ問題の解法 ＜その1： Kaplansky(1943)の証明＞

まずはじめに、Kaplanskyの論文がどのような証明をしているのか追ってみたい。

$U(n)$の条件は、2個あるように見えて実際は($i$が動くので)$2n$個の条件がある。
ここで、それぞれの｢否定｣の条件を以下のように並べて順序つける:

(条件$1_1$) $\sigma(1)= 1$
(条件$1_2$) $\sigma(1)= 2$
(条件$2_1$) $\sigma(2)= 2$
(条件$2_2$) $\sigma(2)= 3$
(条件$3_1$) $\sigma(3)= 3$
……
(条件$(n-1)_2$) $\sigma(n-1)= n$
(条件$n_1$) $\sigma(n)= n$
(条件$n_2$) $\sigma(n)= 1$

求める$U(n)$は、これら全ての条件を満たさないものの個数と言い換えることができる。
ここで包含と排除の原理を使いたい。
すなわち、1つ$k$をfixしたときに、
この$2n$個の条件のうち$k$個を共通して満たすものの個数をどのようにして計算するかという話である。

各条件は、男性1人の場所を指定するので、
その条件がバッティングするということは
同じ男性に複数箇所の移動先があるもしくは男性同士の行き先が被るということに限られる。
まず｢同じ男性に複数箇所の移動先がある｣場合は
例えば男性1に対しては条件$1_1$と条件$1_2$が被るとまずい
男性2に対しては条件$2_1$と条件$2_2$が被るとまずい
……のような条件になることがわかる。
一方で｢男性同士の行き先が被る｣場合は
例えば場所2に対しては条件$1_2$と条件$2_1$が被るとまずい
場所3に対しては条件$2_2$と条件$3_1$が被るとまずい
……のような条件になることがわかる。

よって、条件$1_1$から$n_2$までの$2n$個を円環状に並べた時に、｢隣り合う条件を同時に含むとダメ｣となり
それと同時に
｢隣り合う条件を含まなければ成立｣する。
なぜなら
$k$人の条件づけられた男性の位置が矛盾なく定められたとしたら
残りの$(n-k)$人は自由に席を決めて良い
からである。
その｢矛盾ない条件の組｣に対しては$(n-k)!$通りの並べ方があると言うことができる。
それを｢$k$個の矛盾の無い(隣り合わない)条件を円環状の$2n$個の中から選ぶ｣すなわち$C(2n,k)$個分足し合わせる必要がある。

ゆえに包含と排除の原理より
\begin{align*} U(n)&=\sum_{k=0}^n(-1)^kC(2n,k)(n-k)!\\ &=\sum_{k=0}^n(-1)^k\frac{2n}{2n-k}\binom{2n-k}{k}(n-k)! \end{align*}
となり与えられた式を導くことができる。
ここで、本来包含と排除の原理は要素数$2n$まで考えるべきだが、今｢矛盾のない条件付け｣は男性の人数$n$人が最大なので、$k\ge n+1$についての和は考えなくて良いことに注意する。

メナージュ問題の解法 ＜その2： Bogart-Doyle(1985)の証明＞

こちらも書いておくべきだろうと思うので。
この証明も包含と排除の原理を使うという意味ではKaplanskyの証明に類するが、その使い方は大きく異なる。

直接的に$M(n)$を求めに行きたい。
指定した夫婦$k$組が隣り合う並べ方を$W_k$とおく時(これはカップルの取り方によらない)
包含と排除の原理より次の和
\begin{align*} M(n)=\sum_{k=0}^n(-1)^k\binom{n}{k}W_k \end{align*}
を計算すれば良いことになる。

さて、指定した夫婦$k$組が隣り合うためには何が必要か。
まず円周上の$2n$頂点に重ならないドミノを$k$個置く数を数える必要がある。
でもこの個数は実は$\displaystyle \frac{2n}{2n-k}\binom{2n-k}{k}$として書くことができる。
......どこかで見たことある数だなぁ！！

実際、これは「$2n$個の場所同士の間」の中で「隣り合わない$k$個の場所」を選ぶ選び方と同じである。
なので、上で計算した$C(2n,k)$と一致するのである。

次に、残りの場合の数を計算していく：
・男性女性が「偶数番目・奇数番目」どちらの席を取るか、$2$通り
・指定された$k$組のペアが指定された$k$個のドミノのどこに座るのか、$k!$通り
・残り$(n-k)$人の男性はどこに座らせても良い：$(n-k)!$通り
・残り$(n-k)$人の女性はどこに座らせても良い：$(n-k)!$通り

これらを全て掛け合わせると
\begin{align*} M(n) &=\sum_{k=0}^n(-1)^k\binom{n}{k}\frac{2n}{2n-k}\binom{2n-k}{k}(2\cdot k!)\{(n-k)!\}^2 \\ &=\sum_{k=0}^n(-1)^k\frac{n!}{k!(n-k)!}\frac{2n}{2n-k}\binom{2n-k}{k}(2\cdot k!)\{(n-k)!\}^2 \\ &=(2\cdot n!)\sum_{k=0}^n(-1)^k\frac{2n}{2n-k}\binom{2n-k}{k}(n-k)! \end{align*}
となり、Kaplanskyの証明と同じ結果が与えることができた。

ちなみに

この $U(n)$ の数表を与えておく。

この値は OEIS A000179 に収録されている。
なお、$U(1)=-1$なのは、、、とりあえず細かいことは気にしない。（本当は場合分けすべきだ笑）
また$M(n)$の方は OEIS A059375 に収録されている。

さらに実はこんな定理が成り立つ:

すなわち、片方の性別を止めたときに、夫婦問題が成立する確率がおよそ$e^{-2}\fallingdotseq 0.13533...$になるということだ。

この$U(n)$の振る舞いについては、色々と面白い結果が知られていて
\begin{align*} U(n) &\sim e^{-2}n!\sum_{k\ge 0}\frac{(-1)^k}{k!(n-1)_k} \\ U(n) &=e^{-2}n!\left(1-\frac{1}{n}-\frac{1}{2n^2}+\frac{1}{3n^3}+\frac{37}{24n^4}+\frac{329}{120n^5}+O\left(\frac{1}{n^6}\right)\right) \end{align*}
みたいな漸近展開を得ることができる。

証明は、今はしないでおく。
定理2の$e^{-2}$の極限になること自体は$U(n)$の表示式から結構簡単にわかったりする。

おまけ

撹乱順列、と私は最初に見にしたのだが、完全順列、と呼ばれることも多いかな？
今回の$U(n)$に非常によく似ていてかつ知名度が圧倒的に高いものが存在する。

\begin{align*} K_n:=\#\{\sigma\in\mathfrak{S}_n \mid {}^\forall i, \sigma(i)\neq i\}=n!\sum_{k=0}^\infty\frac{(-1)^k}{k!} \end{align*}

メナージュ問題を満たす置換はこの完全順列をも満たしている。
ちなみに、この完全順列の総数は
\begin{align*} \lim_{n\to\infty}\frac{K_n}{n!}=e^{-1} \end{align*}
であり、こっちは$e^{-1}$倍の頻度で起こるのが面白い。
あとは、$K_n$の漸近展開の式にはBell数が出てきたり、色々とまだまだ面白い性質はいっぱいある。