2022-03-09

Stieltjes連分数のn階収束子はマッチング多項式の比である

概要

Stieltjes連分数を普通の分数で書いたときの式
$\displaystyle\cfrac{1}{1-\cfrac{a_1x}{1-\cfrac{a_2x}{\qquad\cfrac{\ddots}{1-a_kx}}}}=\frac{F(x)}{G(x)}$
において，多項式 $F,G$ がライングラフのマッチング多項式であることを示す．
証明はFlajoletの補題に基づいてStieltjes連分数をDyck路の母関数とみて，適当な対合を作る方法で行う．

用語の準備

Stieltjes連分数

列 $a_1,a_2,\ldots$ が与えられていて， $a_i\neq 0$ とする．自然数 $k$ に対して $k$ 階のStieltjes連分数 (S-連分数)とは，以下の連分数である．
$S_k(a;x)\triangleq\cfrac{1}{1-\cfrac{a_1x}{1-\cfrac{a_2x}{\qquad\cfrac{\ddots}{1-a_kx}}}}$

Dyck路

Dyck路と呼ばれる組合せ論的オブジェクトを定義する．
第一象限の整数点の集合 $\{(i,j)\mid i,j\geq 0, i,j\in\mathbb{Z}\}$ を節点集合とし，有向枝集合を
$(i,j)\to(i+1,j+1)\qquad i\geq 0,j\geq 0,\\ (i,j)\to(i+1,j-1)\qquad i\geq 0,j\geq 1$
で定めた有向グラフを考える．
このグラフにおいて，点 $(0,0)$ から点 $(0,2n)\ n\geq 0$ への道を，Dyck路という．
このグラフの枝重み $v$ を
$v( (i,j)\to(i+1,j+1))\triangleq 1\qquad i\geq 0,j\geq 0,\\ v( (i,j)\to(i+1,j-1))\triangleq a_jx\qquad i\geq 0,j\geq 1$
と定める．
この枝重みを使って，Dyck路 $\omega$ の重み $v(\omega)$ を，Dyck路に含まれる枝重みの積と定める．
但し $(0,0)$ から $(0,0)$ へ行く一点だけのDyck路の重みは $1$ とする．
Dyck路のピークとは，Dyck路において $(i,j)\to(i+1,j+1)\to(i+2,j)$ という順番で節点が出現する部分のことである．

また，雑に言い換えるとDyck路とは斜め上と斜め下のステップを組み合わせて， $(0,0)$ から出発して $y\geq 0$ の範囲からはみ出ないように $x$ 軸に戻ってくるような歩き方のことである．
$2n$ 歩のDyck路の数はカタラン数 $C_n$ であることが知られている．

上は，Dyck路の例である．その重みとピークを書いておいた．
上述の重み $v$ は，一点だけのDyck路の重みを $1$ とし，点 $(i,j)$ から斜め下に行くたびに $a_jx$ を掛けていくことを意味する．掛けるべき重みは，図中に赤字で書いてある．

S-連分数はDyck路の母関数である

組合せ論界隈ではよく知られているように，S-連分数はDyck路の母関数である．
第一象限において $0\leq y\leq k$ の範囲だけを動くDyck路の集合を $D_k$ と書くことにする．
例えば，上の画像のDyck路は， $D_3$ に含まれるが $D_2$ には含まれない．
このとき以下が成立する．
定理 (Flajoletの補題)
任意の自然数 $k$ に対して
$\displaystyle S_k(a,x)=\sum_{\omega\in D_k}v(\omega)$
が成り立つ．
この補題について詳しくは
Combinatorial aspects of continued fractions - ScienceDirect
を参照せよ．

マッチング多項式

整数 $s,t\ (s\leq t)$ が与えられているとする．集合 $\{i\mid s\leq i\leq t\}$ を節点集合とし，無向枝集合を $\{\{s,s+1\},\{s+1,s+2\},\ldots,\{t-1,t\}\}$ で定めた無向グラフを $[s,t]$ と書く．
グラフ $[s,t]$ のマッチングの集合を $M(s,t)$ と書く．
無向グラフのマッチングとは，枝集合の部分集合であって，pairwise disjointなもののことである．

グラフ $[s,t]$ の枝 $\{s,s+1\}$ の重みを $-a_{s+1}x$ と定め，マッチング $m\in M(s,t)$ の重みを $m$ に含まれる枝の重みの積と定め， $w(m)$ とかく．
但し，枝を一つも含まないマッチング $m=\emptyset$ の重みは $1$ とする．
マッチング $M(s,t)$ の母関数
$\displaystyle F_{s,t}(a;x)\triangleq \sum_{m\in M(s,t)}w(m)$
をマッチング多項式と呼ぶ．
普通はこの多項式を多少変形したものをマッチング多項式と呼ぶが，ここではめんどくさいのでこのように定義する．

上は $[0,3]$ のマッチングの集合 (左)と，それぞれのマッチングの重み (右)，そしてマッチング多項式 (下)を説明する図である．
なお，マッチング多項式 $F_{0,n}(a;x)$ は以下の漸化式で計算できる．
$F_0\triangleq 1,\ F_1\triangleq 1-a_1x,\ F_{n}\triangleq F_{n-1}-a_nxF_{n-2}$

$n$ 階のStieltjes連分数は，マッチング多項式の比である

定理
任意の自然数 $n$ に対して
$\displaystyle S_{n}(a;x)=\frac{F_{1,n}(a;x)}{F_{0,n}(a;x)}$
が成り立つ．
証明
等価な式
$F_{1,n}(a;x)=S_{n}(a;x)F_{0,n}(a;x)$
を示す．
集合 $I$ を $I\triangleq D_n\times M(0,n)$ とし， $I$ の部分集合 $J$ を
$J\triangleq\{(\omega,m)\mid \omega{\rm は一点のみのDyck路},\ m{\rm は点}0{\rm をマッチングに含まない}\}$
と定める．
すると，Flajoletの補題より右辺は集合 $I$ の母関数，左辺は集合 $J$ の母関数である．
つまり
$\displaystyle F_{1,n}(a;x)=\sum_{(\omega,m)\in J}v(\omega)w(m),\qquad S_n(a;x)F_{0,n}(a;x)=\sum_{(\omega,m)\in I}v(\omega)w(m)$
である．
よって，この等式を示すには，対合 $\varphi\colon I\setminus J\ni(\omega,m)\mapsto (\omega',m')\in I\setminus J$ であって，
$v(\omega)w(m)=-v(\omega')w(m')$
なるものを作ればよい．
組 $(\omega,m)\in I\setminus J$ が与えられたとき，非負整数 $p,q$ を以下で定める．
但しDyck路のピークの中で， $x$ 座標が一番小さいピークを最初のピークという．

Dyck路 $\omega$ に含まれる最初のピークが $(i,j)\to(i+1,j+1)\to(i+2,j)$ という形だとする．このとき $p\triangleq j+1$ とする．ピークが存在しないとき，つまり $\omega$ が一点だけのとき $p\triangleq -\infty$ とする．
マッチング $m$ に含まれる枝 $\{i,i+1\}$ のうち， $i$ が最小のものをとり $q\triangleq i+1$ とする．枝が存在しないとき，つまり $m=\emptyset$ のときは $q\triangleq \infty$ とする．

そして対合で移る相手 $(\omega',m')$ を以下の通り定める．

$p+1\geq q$ のとき，マッチングの枝 $\{q-1,q\}$ を取り除き，Dyck路 $\omega$ において $(q-1,q-1)\to(q,q)\to(q+1,q)$ という部分を挿入する．(これは必ず可能である．)
$p+1\lt q$ のとき，Dyck路の最初のピークすなわち $(p-1,p-1)\to(p,p)\to(p+2,p-1)$ という部分を取り除き，マッチングに枝 $\{p-1,p\}$ を加える．(これも必ず可能である．)

このように $\varphi$ を定めればそれは重みの符号を反転する対合である．
（証明終わり）

上は対合の様子を説明する図である．Dyck路とマッチングの組 $(\omega,m)$ をとったとし，
図中の $y$ 軸にあたる部分に，マッチング $m$ を縦向きに置いてある．(a)ではマッチングの赤い部分につけられた重みが $-a_qx$ であるが，対合で移したあとの (b)ではDyck路に挿入された赤い部分の重みが $a_qx$ に変わっており，重みの符号が反転していることがわかる．

2022-02-19

組合せ論的タコ

母関数全単射的証明

Combinatorial species (Combinatorial species - Wikipedia)は，離散オブジェクトの指数型母関数を扱うための現代的な手法である．
本稿ではspeciesの理論自体を説明することはしないが，大まかに言えばspeciesの理論は離散オブジェクトの組合せ論的な構造の情報を，直接母関数の等式へ変換する理論である．
詳しくは代表的な教科書Combinatorial Species and Tree-like Structuresをみるとよい．

本稿では，speciesの理論の練習問題としてよく登場するタコ (combinatorial octopus)と呼ばれるオブジェクトをspeciesの理論を用いて解析する．
本稿の元ネタは，上記教科書の練習問題である．

準備

まず，後に必要になるのでサイクルおよび長さ1以上の道の指数型母関数を求めておく．

サイクルとは， $n\ (n\geq 1)$ 個の要素を向きづけられた環状に並べる方法のことで，その数は円順列として馴染み深い $(n-1)!$ 通りである．
サイクルの指数型母関数は
$\displaystyle C(x)\triangleq\sum_{n\geq 1}\frac{x^n}{n!}(n-1)!=-\log(1-x)$
である．

長さ1以上の道とは， $n\ (n\geq 1)$ 個の要素を向きづけられた直線状に並べる方法のことで，その数は $n!$ 通りである．
長さ1以上の道の指数型母関数は
$\displaystyle L_{+}(x)\triangleq\sum_{n\geq 1}\frac{x^n}{n!}n!=\frac{1}{1-x}-1=\frac{x}{1-x}$
である．

タコの定義

タコとは，長さ1以上の道を，向きづけられた環状に $1$ 個以上並べる構造のことである．
例えば，下図は要素 $\{1,2,\ldots,17\}$ によるタコの一つである．

なお，今扱っているタコはラベル付きのタコである．グラフとして同型でもラベルが違うタコは区別する．

タコは，サイクルの一つ一つの点を，長さ1以上の道に置き換えた構造であると言える．
speciesの理論によれば，オブジェクトの世界での「点を別の構造に置き換える」操作は，母関数の世界での「代入」を意味するから，タコの母関数は
$\displaystyle {\rm Oct}(x)=\sum_{n\geq 0}\frac{x^n}{n!}{\rm Oct}_n=C(L_{+}(x))=-\log\left(\frac{1-2x}{1-x}\right)$
である．
ただし， $n$ 個の要素によるタコの数を ${\rm Oct}_n$ とかく．

ここから，要素数 $1,2,3,\ldots$ のタコの数はそれぞれ $1, 3, 14, 90, 744, 7560,\ldots$ である．
(OEIS: A029767)

サイクルとの間の全単射

タコの母関数は，次のように変形できる．
$\displaystyle {\rm Oct}(x)=-\log(1-2x)-(-\log(1-x))=C(2x)-C(x).$
ここから，オブジェクトの組合せ論的な対応関係
${\rm Oct}+C=C(2X)$
の成立が予想される．
上式はspeciesの言葉で書いてるが，speciesの言葉を使わないで書くと以下のことを言っている．

要素 $\{1,\ldots,n\}$ のタコの集合を ${\rm OCT}_n$ ，要素 $\{1,\ldots,n\}$ のサイクルの集合を ${\rm C}_n$ と書き，
要素 $\{1,\ldots,n\}$ の色付きサイクルの集合を ${\rm CC}_n$ と書く．
色付きサイクルとはサイクルの各点に対して色 $\in\{{\rm 赤},{\rm 青}\}$ を決めたものである．
これらの集合の間に全単射
${\rm CC}_n\to {\rm OCT}_n\sqcup {\rm C}_n$ がとれる．

（実際は，全単射がspeciesの同型となるためには，要素数が等しい以上の強い条件が必要である．）
これを満たす全単射は次のものがとれる．
色付きサイクルにおいて，赤い要素(Aとする)の次に青い要素(Bとする)が並んでいる場所があるとする．
このとき，Bから初めてサイクルを一周してAに至るまで，サイクル上の要素を順に見ていく．
今見ている要素が青いとき，キューにその要素をプッシュする．
今見ている要素が赤いとき，キューにその要素をプッシュし，そのキューをタコの触手の一本とする．この際，色はなくす．

これにより，タコができる．
要素がすべて赤い場合は，そのまま色をなくし触手の長さがすべて $1$ のタコとみなす．
要素がすべて青い場合は，タコは作らず，色をなくし要素数 $n$ のサイクルとみなす．

下図は， $n=8$ のときのこの対応の例である．

タコの数

タコの母関数
$\displaystyle {\rm Oct}(x)=C(2x)-C(x)$
を変形すると
$\displaystyle {\rm Oct}(x)=\sum_{n\leq 1}(n-1)!\frac{(2x)^n}{n!}-\sum_{n\leq 1}(n-1)!\frac{x^n}{n!}=\sum_{n\leq 1}(n-1)!(2^n-1)\frac{x^n}{n!}$
となるから，要素数 $n$ のタコの数は
${\rm Oct}_n=(n-1)!(2^n-1)$ である．

2021-12-24

置換の符号の一般化が無理だった話

置換

置換の符号とは，対称群 $S_n$ から $S_2=\{+1,-1\}$ への唯一の非自明な準同型で ${\rm sign}$ とかきます．
この置換の符号を使って，例えば行列式などが
$\displaystyle\det A = \sum_{\sigma\in S_n}{\rm sign}(\sigma)A_{1,\sigma(1)}\cdots A_{n,\sigma(n)}$
などと定義できるのでした．

ここで，符号の値域を $S_2$ ではなく， $S_3$ にすると，置換の符号を精密化した「一般化符号」ができて面白いんじゃないかと思いました．
ここでは，次のような写像 $f\colon S_n\to S_3$ を「一般化符号」と呼ぶことにしました．

$f$ は準同型である
$\forall \sigma\in S_3$ に対し $|f^{-1}(\sigma)|=n!/6$ である．
$\forall\sigma\in S_n$ に対し ${\rm sign}(\sigma)={\rm sign}(f(\sigma))$ である．

結論から言うと，そのような準同型 $f$ は $n\geq 5$ のとき存在しませんでした．

命題　 $n\geq 5$ のとき，そのような写像 $f$ は存在しない．
証明：
$n\geq 5$ のとき， $S_n$ の正規部分群は $\{{\rm id}\},A_n,S_n$ だけである．（知りませんでした...）
（group theory - Proving that $A_n$ is the only proper nontrivial normal subgroup of $S_n$, $n\geq 5$ - Mathematics Stack Exchange）
準同型の核は正規部分群なので， $|{\rm Ker}\ f|=1,n!/2,n!$ である．
$n!/6$ にはならないので，終了．
（証明終わり）

今後は，準同型であるという条件を外して，他の意味で良さそうな「一般化符号」がないか考えてみようと思います．

2021-12-18

重複組合せの数について

全単射的証明高校数学

$n$ 個の文字から重複を許して $k$ 個とるとり方は
$\displaystyle\binom{n+k-1}{k}$ 通りである．このことを二通りの方法で示す．

証明その１

$n$ 個の文字 $x_1,\ldots,x_n$ から重複を許して $k$ 個とるとり方は，
$k$ 個の (区別できない)ボールと $n-1$ 個の (区別できない)仕切りを一列に並べる並べ方と一対一対応する．
なぜならば，そのようにボールと仕切りを並べると，仕切りで区切られた $n$ 個の小部屋が一列に並ぶ．
各小部屋の中には，ボールが $k_i$ 個入っているとする．
この並べ方を，文字 $x_i$ を $k_i$ 個とる文字のとり方に対応させれば，その対応は一対一である．
（証明終わり）

この対応の例を下の図に書いておく．

証明その２

$x_1,\ldots,x_n$ のラベルがついた $n$ 個の箱と， $y_1,\ldots,y_{k-1}$ のラベルがついた $k-1$ 個の箱があり，それらの箱に合計 $k$ 個の (区別できない)ボールを入れる入れ方は $\displaystyle\binom{n+k-1}{k}$ 通りである．
（一つの箱には，高々一個のボールしか入れないとする．）

この入れ方を入力とし， $n$ 個の文字 $x_1,\ldots,x_n$ から重複を許して $k$ 個とるとり方を出力する対応を構成する．

箱 $x_1,\ldots,x_n$ には少なくとも合計一個のボールが入る．どの箱にボールが入ったかによって，取り出す文字を重複度を除き定める．
一方，箱 $y_1,\ldots,y_{k-1}$ には合計 $0$ 個から $k-1$ 個のボールが入る．どの箱にボールが入ったかによって各文字の重複度を定める．

箱 $x_1,\ldots,x_n$ に合計 $j\ (1\leq j\leq k)$ 個のボールが入ったとする．
ボールが入った箱のラベルを $x_{t(1)},\ldots,x_{t(j)}$ とかく．
このとき，箱 $y_1,\ldots,y_{k-1}$ には合計 $k-j$ 個のボールが入っている．
箱 $y_1,\ldots,y_{k-1}$ のうち，ボールが入っていない箱に注目する．
そのような箱は $j-1$ 個存在しそれらのラベルを $y_{s(1)},\ldots,y_{s(j-1)}$ とする．

文字 $x_1,\ldots,x_n$ から重複を許して $k$ 個取り出す取り出し方を次の通り定める：
取り出す文字は $x_{t(1)},\ldots,x_{t(j)}$ とする．
文字 $x_{t(i)}\ (1\leq i\leq j)$ の重複度を $s(i)-s(i-1)$ と定める．
但し， $s(0)\triangleq 0,s(j)\triangleq k$ とする．
この対応は一対一である．
（証明終わり）

この対応の例を下の図に書いておく．

2021-12-09

n変数論理関数の数

命題
$n$ 変数論理関数，つまり写像 $f\colon\{0,1\}^n\to \{0,1\}$ は $2^{2^n}$ 通り存在する．

証明
$f\colon\{0,1\}^n\to \{0,1\}$ と書いた時点でほとんど明らかな気がするが，証明するには真理値表が何通り書けるかを考えればよい．
$(0,0,\ldots,0)$ から $(1,1,,\ldots,1)$ までの $2^n$ 通りの入力が，それぞれ $\{0,1\}$ のどちらになるかを決めるので， $2^{2^n}$ 通りになる．
（証明終わり）

蛇足
最初は、異なる和積標準形が何個あるか数えようとしていたが、挫折した。
どうやるんだろう。

追記：もともとは「論理式の数」という題名でしたが，誤りであるとの指摘があったため「論理関数の数」としました．

2021-11-10

添字の動く範囲にminが絡むある和について

全単射的証明母関数

以下の命題の代数的証明と組合せ論的証明を紹介する．また，組合せ論的証明に基づいてパラメータを増やす拡張を行う．

定理
自然数 $n,r$ について
$\displaystyle\sum_{\substack (n,n+1,\ldots,n+r-1)\geq (\ell_0,\ldots,\ell_{r-1})\geq 0\\ \min\{\ell_0,\ldots,\ell_{r-1}\}\geq c\geq 0}q^{\ell_0+\cdots+\ell_{r-1}+c}=\frac{\prod_{i=1}^{r+1}(1-q^{n+i})}{(1-q)^r(1-q^{r+1})}$
が成立する．

上式左辺は，添字 $\ell_{i}$ が動く範囲が $0\leq\ell_{i}\leq n+i\ (0\leq i\leq r-1)$ だということを表す．
また右辺は， $q$ -解析の記号 $\displaystyle[n]\triangleq \frac{1-q^n}{1-q}$ を使うと $\displaystyle\frac{\prod_{i=0}^{r+1}[n+i]}{[r+1]}$ と書ける．

代数的証明

twitterにて証明を募集したところ，NKSさん (@nkswtr1)が教えてくれた証明を紹介する．
https://twitter.com/nkswtr1/status/1451845616653402114

この証明では，和の順番を入れ替えてまず添字 $c$ に関しての和と見ることがポイントだったようだ．

（証明終わり）

組合せ論的証明

右辺の分母を左辺に持ってきた形
$\displaystyle[r+1]\left(\sum_{\substack (n,n+1,\ldots,n+r-1)\geq (\ell_0,\ldots,\ell_{r-1})\geq 0\\ \min\{\ell_0,\ldots,\ell_{r-1}\}\geq c\geq 0}q^{\ell_0+\cdots+\ell_{r-1}+c}\right)=\prod_{i=1}^{r+1}[n+i]$
を示す．
整数の $r+1$ 個組の二つの集合を
$I\triangleq\{(\ell_0,\ldots,\ell_{r-1};c)\mid 0\leq \ell_i\leq n+i\ (0\leq i\leq r-1),\ 0\leq c\leq \min\{\ell_0,\ldots,\ell_{r-1}\}\}$
$J\triangleq\{(t_0\ldots,t_{r})\mid 0\leq t_{i}\leq n+i\ (0\leq i\leq r)\}$
と定義する．
式を示すには，全単射 $\{0,\ldots,r\}\times I\ni (x,(\ell_0,\ldots,\ell_{r-1};c))\mapsto (t_0,\ldots,t_{r})\in J$
であって，
(式１)：　 $\displaystyle x+\sum_{i=0}^{r-1}\ell_{i}+c=\sum_{j=0}^rt_r$
を満たすものを作ればよい．
全単射は次のように作る．

$(x,(\ell_0,\ldots,\ell_{r-1};c))$ に対して，
$(t_0,\ldots,t_r)\triangleq (\ell_0,\ldots,\ell_{r-x-1},c,\ell_{r-x}+1,\ldots,\ell_{r-1}+1)$ と定める．
つまり，列 $(\ell_0,\ldots,\ell_{r-1})$ の後ろから $x$ 番目の位置に $c$ を挿入し，それより後ろはすべて $+1$ するということである．
この対応は全単射的である．なぜならば，できた列 $(t_0,\ldots,t_r)$ の中で一番小さい要素のうち一番右にあるものが $c$ として挿入されたものだと分かるからである．
またこの対応は(式１)を満たす．
（証明終わり）

組合せ論に基づく拡張

組合せ論的証明をよく見ると追加のパラメータとして $a_i$ を入れた次の拡張ができる．
定理
自然数 $n,r$ について
$\displaystyle\sum_{x=0}^r\sum_{\substack (n,n+1,\ldots,n+r-1)\geq (\ell_0,\ldots,\ell_{r-1})\geq 0\\ \min\{\ell_0,\ldots,\ell_{r-1}\}\geq c\geq 0}q^{\ell_0+\cdots+\ell_{r-1}+c+x}\left(\prod_{i=0}^{r-1}a_{\ell_i-i}\right)a_{c-r+x}$
$\displaystyle=\prod_{i=0}^r\sum_{j=0}^{n+i}q^ja_{j-i}$

が成立する．
この式は，全ての $a_i$ を $a_i=1$ とすると元の式に戻る．

証明
(右辺)
$\displaystyle=\sum_{(t_0,\ldots,t_{r})\in J}q^{t_0+\cdots+t_r}\prod_{i=0}^ra_{t_i-i}$
ここで全単射を使って $J$ から $I$ にうつすと
$\displaystyle=\sum_{x=0}^r\sum_{(\ell_0,\ldots,\ell_{r-1};c)\in I}q^{\ell_0+\cdots+\ell_{r-x-1}+(\ell_{r-x}+1)+\cdots+(\ell_{r-1}+1)+c}\left(\prod_{i=0}^{r-x-1}a_{\ell_i-i}\right)\left(\prod_{i=r-x+1}^{r}a_{\ell_{i-1}+1-i}\right)a_{c-(r-x)}$
=(左辺)

（証明終わり）

蛇足

和の変数を増やす違う拡張もやってみました

昨日のやつがウケがよかったから拡張版も作った

添字の動く範囲の上限が
i_0,…,i_{r-1},j_0,…,j_{c-1}
で連続してるように見えて、実は一個開いてるのがチャームポイント pic.twitter.com/IXI2iKj3jo
— 岩 (@iwalion) 2021年10月24日

2021-06-13

第一種スターリング数の行列式，組合せ論的証明

全単射的証明スターリング数置換行列式

記事概要

本記事では以下を組合せ論的に示す．

証明は対合を構成することで行う．
具体的には例えば $n=4$ のときは

が成り立つ．

定義や準備など

調べたところ，第二種スターリング数の行列式を考えた研究には[1]がある．
また，数学質問サイトStack exchangeには第一種スターリング行列のマイナーについての
質問 [2]があり，本記事で述べる証明がこの質問への理解に繋がるのではないかと考えている．
以下準備１，２で定義などを書いたあと証明を述べる．

準備１：第一種スターリング数について

第一種スターリング数 $c_{n,k}$ を， $n$ 文字の置換のうち $k$ 個のサイクルからなるものの個数と定義する．
以前の記事で述べたように， $c_{n,k}$ は多項式 $x(x+1)\cdots(x+n-1)$ の $x^k$ の係数に等しい．

この事実を使うと，各 $n,k$ に対して $c_{n,k}$ の値が簡単に計算できる．
以下は， $c_{n,k}$ の値を表にしたものである．（赤い部分の意味は後述．）

n\k	0	1	2	3	4	5	6	7
0	1	0	0	0	0	0	0	0
1	0	1	0	0	0	0	0	0
2	0	1	1	0	0	0	0	0
3	0	2	3	1	0	0	0	0
4	0	6	11	6	1	0	0	0
5	0	24	50	35	10	1	0	0
6	0	120	274	225	85	15	1	0
7	0	720	1764	1624	735	175	21	1

この表を行列としてみると，逆行列が組合せ論的意味を持つなどそれ自体面白いのだが，
今回は上の赤色の部分を取り出し，その行列式を明示的に求めることを考える．

例えば上の赤字で示した例だと

となる．
この関係がより一般に成立することを述べたのが本記事の定理である．

準備２：置換と0-1タブロー

以下では置換をそのまま使うのではなく，置換を「0-1タブロー」と呼ばれるより扱いやすいオブジェクトに変換した上で用いる．
0-1タブローについては以前の記事にも述べたが，もう一度書いておく．
なお，0-1タブローに関するちゃんとした文献としては [3]を参照するとよい．

定義 0-1タブローとは，strictな分割 $\lambda=(\lambda_1>\lambda_2>\cdots>\lambda_r)$ のヤング図形において，各行に一箇所づつ記号「×」を書き込んだものである．

0-1タブローは例えば，以下のようなものである．

分割 $\lambda$ に対し，分割の長さを $\ell(\lambda)$ とかく．例えば上図の分割 $\lambda=(5,4,3,1)$ では $\ell(\lambda)=4$ である．
$\lambda_1\leq n,\ell(\lambda) = r$ を満たす0-1タブロー全体を ${\rm T}(n,r)$ とかく．例えば，上図の0-1タブローは ${\rm T}(6,4)$ の元である．
次の補題は置換と0-1タブローとの一対一対応を示す．

補題１ ([3])
集合 $\{\sigma\in\mathfrak{S}_n\mid \sigma はサイクルをk個持つ\}$ と集合 ${\rm T}(n-1,n-k)$ との間に全単射が存在する．

証明
まず， $n$ 文字の任意の置換は，空置換から始めて $i=1,\ldots,n$ のそれぞれについて

新しいサイクル $(i)$ を追加する
既存のサイクルに $i$ を追加する

のどちらかを順番に行って作ることができる．

例えば，置換 $(1526)(34)(7)\in\mathfrak{S}_7$ は，空置換へ

(1)を追加する．
1のあとに2を追加し(12)にする
(3)を追加し(12)(3)にする．
3のあとに4を追加し(12)(34)にする
1のあとに5を追加し(152)(34)にする
2のあとに6を追加し(1526)(34)にする
(7)を追加し(1526)(34)(7)にする

という手順で作られるものである．また，この作り方の手順は一意的である．

置換 $\sigma$ に対応する0-1タブロー $T$ を，空タブローから初めて $i=1,\ldots,n$ について

$(i)$ を追加したときは，何もしない
$k\ (k < i)$ のあとに $i$ を追加したときは，タブローの最上段に長さ $i-1$ の行を追加し，左から $k$ 番目に「×」をつける

により作られるタブローと定める．

この対応とタブローの作り方の例を，以下に書いておく．

タブローの作り方から， $n$ 文字の置換でサイクル $k$ 個のものは， ${\rm T}(n-1,n-k)$ の元に対応し，逆もまた言えることがわかる．
（証明終わり．）

定理のステートメント再掲

定理を再掲する．
定理　任意の自然数 $n$ について，以下が成立する．

定理の証明

まず，行列式の定義から
$\displaystyle\det(c_{n+i-1,j})_{i,j=1}^n=\sum_{\sigma\in\mathfrak{S}_n}{\rm sign}(\sigma)c_{n,\sigma(1)}c_{n+1,\sigma(2)}\cdots c_{2n-1,\sigma(n)}$

である．ここで，集合 $I$ を次のように定義する．
$I\triangleq\{(\sigma;\alpha_1,\alpha_2,\ldots,\alpha_n)\mid ☆\}$
☆に入る条件は次の通り：

$\sigma\in\mathfrak{S}_n$ ,
$\alpha_1\in\mathfrak{S}_n$ であり， $\alpha_1$ のサイクルの数は $\sigma(1)$ ,
$\alpha_2\in\mathfrak{S}_{n+1}$ であり， $\alpha_2$ のサイクルの数は $\sigma(2)$ ,
・・・
$\alpha_n\in\mathfrak{S}_{2n-1}$ であり， $\alpha_n$ のサイクルの数は $\sigma(n)$ ．

この $I$ を使うと，和は
$\displaystyle \sum_{\sigma\in\mathfrak{S}_n}{\rm sign}(\sigma)c_{n,\sigma(1)}c_{n+1,\sigma(2)}\cdots c_{2n-1,\sigma(n)}=\sum_{(\sigma;\alpha_1,\ldots,\alpha_n)\in I}{\rm sign}(\sigma)$
と書ける．

一方，集合 $I$ の部分集合 $J\subseteq I$ を次のように定義する．
$J\triangleq\{(\sigma;\alpha_1,\alpha_2,\ldots,\alpha_n)\mid ★\}$
★に入る条件は次の通り：

$\sigma={\rm id}\in\mathfrak{S}_n$ ,
$\alpha_1=({\rm xxxx})\in\mathfrak{S}_n$ ,
$\alpha_2=({\rm xxxx})(n+1)\in\mathfrak{S}_{n+1}$ ,
・・・
$\alpha_n=({\rm xxxx})(n+1)(n+2)\cdots(2n-1)\in\mathfrak{S}_{2n-1}$ ．

ただし， $({\rm xxxx})$ は $\{1,\ldots,n\}$ の巡回置換なら何でもいいということを表す．

この集合 $J$ に関して
$\displaystyle\sum_{(\sigma;\alpha_1,\ldots,\alpha_n)\in J}{\rm sign}(\sigma)=((n-1)!)^n$
である．これは ${\rm sign}({\rm id})=1$ であり，和に寄与するのは実質 $\{1,\ldots,n\}$ の巡回置換 $n$ 個分だということから分かる．

よって，我々が示すべきことは
$\displaystyle \sum_{(\sigma;\alpha_1,\ldots,\alpha_n)\in I}{\rm sign}(\sigma)=\sum_{(\sigma;\alpha_1,\ldots,\alpha_n)\in J}{\rm sign}(\sigma)$
である．
つまり同じことだが書き換えると
$\displaystyle \sum_{(\sigma;\alpha_1,\ldots,\alpha_n)\in I\setminus J}{\rm sign}(\sigma)=0$
を示せばよい．

これは，写像 $\varphi\colon I\setminus J\ni(\sigma;\alpha_1,\ldots,\alpha_n)\mapsto (\sigma';\alpha_1',\ldots,\alpha_n')\in I\setminus J$ であって，

${\rm sign}(\sigma) = -{\rm sign}(\sigma')$
$\varphi\circ\varphi={\rm id}_{I\setminus J}$

なるものを作ることで示される．
（このような写像，というか対合が存在すれば集合 $I\setminus J$ には ${\rm sign}(\sigma)$ が $+1$ のものと $-1$ のものが同じ数存在する事がわかるからである．このような論法をinvolution principleという．以前の記事でも軽く紹介したことがある．）

以下，そのような対合 $\varphi$ を構成する．
方針としては， $(\sigma;\alpha_1,\ldots,\alpha_n)\in I\setminus J$ において置換 $\alpha_i$ と $\alpha_{i+1}$ に注目し，何らかの (もとに戻せる)方法でこの二つの置換のサイクルの数を入れ替える写像を $\varphi$ とすればよい．
そうすれば， $\sigma$ に隣接互換を当てることになり，符号が反転する．

0-1タブロー $T$ に対して，その最上段の長さと段の数をそれぞれ $\lambda_1(T),\ell(T)$ と書くことにする．
例えば，以下の0-1タブロー $T$ については， $\lambda_1(T)=5,\ell(T)=4$ である．

また $T$ において「×」印を無視することで得られるヤング図形を， $T$ の基礎ヤング図形と呼ぶ．

鍵となるのは次の補題である．

補題２
$(\sigma;\alpha_1,\ldots,\alpha_n)\in I\setminus J$ とする．
補題１の対応関係により置換 $\alpha_1,\ldots,\alpha_n$ に対応する0-1タブローをそれぞれ $T_1,\ldots,T_n$ とする．
このとき，添字 $i\in\{1,\ldots,n-1\}$ であって $\lambda_1(T_i) < \lambda_1(T_{i+1})$ であるものが存在する．

証明
そのような添字が存在しないと仮定すると，
$\lambda_1(T_1) \geq \lambda_1(T_2) \geq \cdots \geq \lambda_1(T_n)$ である．

すると以下のように，タブロー $T_n,T_{n-1},\ldots$ の基礎ヤング図形はある決まった形でなければならないことが分かる．
$\alpha_n$ は $n$ 文字の置換なので $n-1\geq \lambda_1(T_1)$ であり，背理法の仮定から $n-1\geq\lambda_1(T_n)$ である．
このとき，strictnessの条件から $n-1\geq\ell(T_n)$ である．
置換 $\alpha_n$ のサイクルの数は $2n-2-\ell(T_n)+1$ であり，集合 $I$ の定義からこれは $1$ から $n$ の範囲になければならない．すなわち $1\leq 2n-2-\ell(T_n)+1\leq n$ ．
以上の考察で得られた不等式を解けば $\ell(T_n)=n-1$ が分かり，strictnessの条件から $\lambda_1(T_n)=n-1$ ．
つまり，タブロー $T_n$ の基礎ヤング図形は分割 $(n-1,n-2,\ldots,1)$ で表される階段型のものでなくてはならず，これは置換 $\alpha_n$ が
$\alpha_n = ({\rm xxxx})(n+1)(n+2)\ldots(2n-1)$ という形でなくてはならないことを意味する．

次に同様の考察から置換 $\alpha_{n-1}$ のサイクルの数は $2n-3-\ell(T_{n-1})+1$ であり，集合 $I$ の定義からこれは $1$ から $n-1$ の範囲になければならない．ここから結局 $\ell(T_{n-1})=n-1$ が分かり，
$T_{n-1}$ の基礎ヤング図形は $T_n$ と同じ階段型で
置換 $\alpha_{n-1}$ は $\alpha_n = ({\rm xxxx})(n+1)(n+2)\ldots(2n-2)$ という形である．

これを同様に進めていくと，結局仮定が成り立つためには
$(\sigma;\alpha_1,\ldots,\alpha_n)\in J$ でなくてはならないことが分かり，矛盾となる．
（証明終わり．）

対合 $\varphi$ を構成する．
補題２より， $\lambda_1(T_i)<\lambda_1(T_{i+1})$ であるような添字 $i\ (1\leq i\leq n-1)$ が存在する．
そのような添字 $i$ の中で最大のものをとる．
「 $T_{i+1}$ の最上段を取り除いて $T_{i}$ の最上段の上にくっつけ， $T_{i}$ と $T_{i+1}$ を入れ替える．」
そうして得られたものを， $\varphi(\ (\sigma;\alpha_1,\ldots,\alpha_n)\ )$ の値とする．

これに関しては具体例を見たほうが早いと思うので，下図を見てほしい．

この写像 $\varphi$ はいかにも対合である．
また一番大事なことだが，この写像 $\varphi$ は置換 $\alpha_i$ と $\alpha_{i+1}$ のサイクルの数を入れ替える．
よってこの写像 $\varphi$ は二つの条件

${\rm sign}(\sigma) = -{\rm sign}(\sigma')$
$\varphi\circ\varphi={\rm id}_{I\setminus J}$

を満たしている．