数学の命題示しました

主に組合せ論について,読んだ本で出てきたことや,考えたことを書きます.

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

記事概要

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

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

 \det\begin{pmatrix}
6&11&6&1\\
24&50&35&10\\
120&274&225&85\\
720&1764&1624&735
\end{pmatrix}=1296=((4-1)!)^4
が成り立つ.

定義や準備など

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

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

第一種スターリング数 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

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

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

 \det\begin{pmatrix}
6&11&6&1\\
24&50&35&10\\
120&274&225&85\\
720&1764&1624&735
\end{pmatrix}=1296=((4-1)!)^4
となる.
この関係がより一般に成立することを述べたのが本記事の定理である.

準備2:置換と0-1タブロー

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

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

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

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タブローとの一対一対応を示す.

補題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. 1のあとに2を追加し(12)にする
  3. (3)を追加し(12)(3)にする.
  4. 3のあとに4を追加し(12)(34)にする
  5. 1のあとに5を追加し(152)(34)にする
  6. 2のあとに6を追加し(1526)(34)にする
  7. (7)を追加し(1526)(34)(7)にする

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

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

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

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

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

置換と0-1タブローの対応の例

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



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

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

 \det\begin{pmatrix}
c_{n,1}&\cdots&c_{n,n}\\
\vdots&&\vdots\\
c_{2n-1,1}&\cdots&c_{2n-1,n}
\end{pmatrix}
= ((n-1)!)^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である.

0-1タブロー T

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

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

補題
 (\sigma;\alpha_1,\ldots,\alpha_n)\in I\setminus Jとする.
補題1の対応関係により置換 \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を構成する.
補題2より, \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はいかにも対合である.
また一番大事なことだが,この写像 \varphiは置換 \alpha_i \alpha_{i+1}のサイクルの数を入れ替える.
よってこの写像 \varphiは二つの条件

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

を満たしている.

(証明終わり)

蛇足

 q-拡張もそのままできるはずである.