第一種スターリング数の行列式,組合せ論的証明
記事概要
本記事では以下を組合せ論的に示す.
証明は対合を構成することで行う.
具体的には例えばのときは
定義や準備など
調べたところ,第二種スターリング数の行列式を考えた研究には[1]がある.
また,数学質問サイトStack exchangeには第一種スターリング行列のマイナーについての
質問 [2]があり,本記事で述べる証明がこの質問への理解に繋がるのではないかと考えている.
以下準備1,2で定義などを書いたあと証明を述べる.
準備1:第一種スターリング数について
第一種スターリング数を,文字の置換のうち個のサイクルからなるものの個数と定義する.
以前の記事で述べたように,は多項式のの係数に等しい.
この事実を使うと,各に対しての値が簡単に計算できる.
以下は,の値を表にしたものである.(赤い部分の意味は後述.)
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 |
この表を行列としてみると,逆行列が組合せ論的意味を持つなどそれ自体面白いのだが,
今回は上の赤色の部分を取り出し,その行列式を明示的に求めることを考える.
例えば上の赤字で示した例だと
となる.この関係がより一般に成立することを述べたのが本記事の定理である.
準備2:置換と0-1タブロー
以下では置換をそのまま使うのではなく,置換を「0-1タブロー」と呼ばれるより扱いやすいオブジェクトに変換した上で用いる.
0-1タブローについては以前の記事にも述べたが,もう一度書いておく.
なお,0-1タブローに関するちゃんとした文献としては [3]を参照するとよい.
定義 0-1タブローとは,strictな分割 のヤング図形において,各行に一箇所づつ記号「×」を書き込んだものである.
0-1タブローは例えば,以下のようなものである.
分割に対し,分割の長さをとかく.例えば上図の分割ではである.
を満たす0-1タブロー全体をとかく.例えば,上図の0-1タブローはの元である.
次の補題は置換と0-1タブローとの一対一対応を示す.
証明
まず,文字の任意の置換は,空置換から始めてのそれぞれについて
- 新しいサイクルを追加する
- 既存のサイクルにを追加する
のどちらかを順番に行って作ることができる.
例えば,置換は,空置換へ
- (1)を追加する.
- 1のあとに2を追加し(12)にする
- (3)を追加し(12)(3)にする.
- 3のあとに4を追加し(12)(34)にする
- 1のあとに5を追加し(152)(34)にする
- 2のあとに6を追加し(1526)(34)にする
- (7)を追加し(1526)(34)(7)にする
という手順で作られるものである.また,この作り方の手順は一意的である.
置換に対応する0-1タブローを,空タブローから初めてについて
- を追加したときは,何もしない
- のあとにを追加したときは,タブローの最上段に長さの行を追加し,左から番目に「×」をつける
により作られるタブローと定める.
この対応とタブローの作り方の例を,以下に書いておく.
タブローの作り方から,文字の置換でサイクル個のものは,の元に対応し,逆もまた言えることがわかる.
(証明終わり.)
定理の証明
まず,行列式の定義から
である.ここで,集合を次のように定義する.
☆に入る条件は次の通り:
- ,
- であり,のサイクルの数は,
- であり,のサイクルの数は,
- ・・・
- であり,のサイクルの数は.
このを使うと,和は
と書ける.
一方,集合の部分集合を次のように定義する.
★に入る条件は次の通り:
- ,
- ,
- ,
- ・・・
- .
ただし,はの巡回置換なら何でもいいということを表す.
この集合に関して
である.これはであり,和に寄与するのは実質の巡回置換個分だということから分かる.
よって,我々が示すべきことは
である.
つまり同じことだが書き換えると
を示せばよい.
これは,写像であって,
なるものを作ることで示される.
(このような写像,というか対合が存在すれば集合にはがのものとのものが同じ数存在する事がわかるからである.このような論法をinvolution principleという.以前の記事でも軽く紹介したことがある.)
以下,そのような対合を構成する.
方針としては,において置換とに注目し,何らかの (もとに戻せる)方法でこの二つの置換のサイクルの数を入れ替える写像をとすればよい.
そうすれば,に隣接互換を当てることになり,符号が反転する.
0-1タブローに対して,その最上段の長さと段の数をそれぞれと書くことにする.
例えば,以下の0-1タブローについては,である.
またにおいて「×」印を無視することで得られるヤング図形を,の基礎ヤング図形と呼ぶ.
鍵となるのは次の補題である.
補題2
とする.
補題1の対応関係により置換に対応する0-1タブローをそれぞれとする.
このとき,添字であってであるものが存在する.
証明
そのような添字が存在しないと仮定すると,
である.
すると以下のように,タブローの基礎ヤング図形はある決まった形でなければならないことが分かる.
は文字の置換なのでであり,背理法の仮定からである.
このとき,strictnessの条件からである.
置換のサイクルの数はであり,集合の定義からこれはからの範囲になければならない.すなわち.
以上の考察で得られた不等式を解けばが分かり,strictnessの条件から.
つまり,タブローの基礎ヤング図形は分割で表される階段型のものでなくてはならず,これは置換が
という形でなくてはならないことを意味する.
次に同様の考察から置換のサイクルの数はであり,集合の定義からこれはからの範囲になければならない.ここから結局が分かり,
の基礎ヤング図形はと同じ階段型で
置換はという形である.
これを同様に進めていくと,結局仮定が成り立つためには
でなくてはならないことが分かり,矛盾となる.
(証明終わり.)
対合を構成する.
補題2より,であるような添字が存在する.
そのような添字の中で最大のものをとる.
「の最上段を取り除いての最上段の上にくっつけ,とを入れ替える.」
そうして得られたものを,の値とする.
これに関しては具体例を見たほうが早いと思うので,下図を見てほしい.
この写像はいかにも対合である.
また一番大事なことだが,この写像は置換とのサイクルの数を入れ替える.
よってこの写像は二つの条件
を満たしている.
(証明終わり)
蛇足
-拡張もそのままできるはずである.