階乗の分割　　 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　当ＨＰの読者のＫ．Ｓ．さんより、平成２４年１月１０日付けで標記話題をメールで頂いた。

　相異なるＮ個のものの順列（Ｎ個の置換）の総数は、Ｎ！個である。このＮ！を、例えば、

互換の個数で分けたり、様々に（不動点の個数、連結の個数、あみだくじの交点、...ｅ.ｔ.ｃ.）

類別したものの和として表すことができる。以下では対称なものについて考えてみた。

（１）　ヤング図形

　　ヤング図形のマス目に、１、２、・・・、ｎ を入れるとき、「左から右、上から下の順で増加

　する」という規則を守って入れる方法の個数を ｆ^λ とする。このとき、

　　　Ｎ！＝Σ（ｆ^λ）²　（Σは、全てのヤング図形にわたり和を取るものとする。）

例　１！＝１²　、２！＝１²＋１²

　　３つのマス目のヤング図形は、次の３種類。

（イ）	（ロ）	（ハ）

　（イ）（ハ）の場合は、左または上から順に「123」の１通り。（ロ）の場合は、左上が[1」で、右
上または左下は、「2」または「３」の２通りの入れ方がある。

　よって、　３！＝１²＋２²＋１²　が成り立つ。

　同様にして、　４！＝１²＋３²＋２²＋３²＋１²　、５！＝１²＋４²＋５²＋６²＋５²＋４²＋１²

　　　　　　　　　　・・・・・・・・・・・・・・・・・・・・・・・・・・・・・


　　　　空舟さんからのコメントです。（平成２４年２月２６日付け）

　　　　　　Ｎ！＝Σ（ｆ^λ）²　（Σは、全てのヤング図形にわたり和を取るものとする。）

　　　　は、どうして成り立つのでしょうか？


　　　（コメント）　一つのヤング図形に対して、数字の並べ方の総数を、ｆ_λとするとき、
　　　　　　Ｎ！＝Σ（ｆ^λ）² が成り立つという事実は、一見とても美しいが、いざ、それを示
　　　　　　そうと思うとき、途方に暮れてしまう。この公式は、そんな妖しさを持つ。実際に、
　　　　　　示すことはかなり難しい．．．雰囲気。ｆ_λ自体は、Frobenius などの尽力で求める
　　　　　　公式（フック公式）が知られているが、Ｎ！の分割公式を得るには、1938 年に
　　　　　　Robinson により発見された「Robinson-Schensted 対応」が１対１対応であること
　　　　　　を示す必要があるらしい。（→　参考：「ヤング図形の組合せ論」）


　　　　空舟さんからのコメントです。（平成２４年２月２６日付け）

　　　３次の場合、（ヤング盤は、"/"で改行を表すものとする）

　　　　123　12/3　13/2　1/2/3　の４通りで、順に、ａ、ｂ₁、ｂ₂、ｃ とします。

　　　３次の置換が、同じ形のヤング盤同士の写像と対応されます。

　　　　(123)：　ａ　→　ａ
　　　　(132)：　ｂ₁　→　ｂ₁
　　　　(213)：　ｂ₂　→　ｂ₂
　　　　(312)：　ｂ₁　→　ｂ₂
　　　　(231)：　ｂ₂　→　ｂ₁
　　　　(321)：　ｃ　→　ｃ

　　　　森田英章　著（北海道大学理学研究科）
　　　　「On the Robinson-Schensted correspondence」の176-177ページに分かりやすい図
　　　　があります。

　　　置換の数字を順に挿入して作られるヤング盤Pと、その作る過程順に数字を振ったヤ
　　ング盤Qによって、置換に対応する写像P→Qという風に構成されるようです。（そして、
　　逆対応を得る方法があって、対応は1対1）このような対応があることを認めれば、
　　　（置換の個数＝Ｎ！）＝Σ(形ごとのヤング盤の種類)²
　　が成り立つことが分かる。


　　　空舟さんが、上記の話題を「Ｎ^Ｎの分割」に拡張されました。（平成２４年２月２7日付け）

　　　ヤング図形を使ったＮ^Ｎの分割を考えました。多少無理やり感があるのですが、紹介し
　　てみます。

　　　ヤング図形λのマス目に、1、2、・・・、N を入れる時について、

　　　　A：「左から右には増加するが上下は問わない。」

　　　　B：「各行の右端だけに数字を入れる。

　　　　上下に接するもの同士では上から下に増加する。」

　　　この２つの規則を守る入れ方をそれぞれ a_λ、b_λ とします。
　　　（もちろん同じ数字は２回以上使わない。）

　　そうすると、Σ(a_λ・b_λ)＝Ｎ^Ｎ　となります。

　　　具体的に、N=3　だと、λは、(3)、(21)、(111) の３つで、この順に

　　　　　a_λ=1、3、6　　　b_λ=3、6、1　　となって、　Σ(a_λ・b_λ)＝3+18+6=3³

　　N=4　の場合、λは、(4)、(31)、(22)、(211)、(1111) の５つで、この順に

　　　　　aλ=1、4、6、12、24　　　bλ=4、12、6、12、1

　　となって、　Σ(a_λ・b_λ)＝4+48+36+144+24=4⁴

　　（N進数のN桁の数字の分類と対応させることで構成しました。）


（２）　互換の個数

　　互換の個数で、Ｎ！を分割する。

　　　　_ＮＤ_ｒ ： 文字の個数Ｎ個の順列のうち、転倒数（大小の順が逆転している数）が ｒ
　　　　　　　　の順列の個数

例　１２３ の順列は、１２３、１３２、２１３、２３１、３１２、３２１　の６通り

　　このうち、　１２３ の転倒数は、０　・・・　₃Ｄ₀＝１

　　　　　　　　　１３２、２１３ の転倒数は、１　・・・　₃Ｄ₁＝２

　　　　　　　　　２３１、３１２ の転倒数は、２　・・・　₃Ｄ₂＝２

　　　　　　　　　３２１ の転倒数は、３　・・・　₃Ｄ₃＝１

　　以上から、　３！＝₃Ｄ₀＋₃Ｄ₁＋₃Ｄ₂＋₃Ｄ₃　と分割される。

　同様にして、

　　　₁Ｄ₀＝１　、₂Ｄ₀＋₂Ｄ₁＝１＋１　、₃Ｄ₀＋₃Ｄ₁＋₃Ｄ₂＋₃Ｄ₃＝１＋２＋２＋１

　　　₄Ｄ₀＋₄Ｄ₁＋₄Ｄ₂＋₄Ｄ₃＋₄Ｄ₄＋₄Ｄ₅＋₄Ｄ₆＝１＋３＋５＋６＋５＋３＋１

　　　₅Ｄ₀＋₅Ｄ₁＋₅Ｄ₂＋₅Ｄ₃＋₅Ｄ₄＋₅Ｄ₅＋₅Ｄ₆＋₅Ｄ₇＋₅Ｄ₈＋₅Ｄ₉＋₅Ｄ₁₀

　　　＝１＋４＋９＋１５＋２０＋２２＋２０＋１５＋９＋４＋１

　　　　・・・・・・・・・・・・・・・・・・・・・・・・・・・・・

　　一般に、　Ｎ！＝Σ_{ｋ=0〜Ｎ（Ｎ-1）/2 Ｎ}Ｄ<sub>ｋ

　　　　Ｎ</sub>Ｄ₀＝１　、_ＮＤ_{Ｎ（Ｎ-1）/2}＝１　、_ＮＤ_ｒ＝_ＮＤ<sub>Ｎ（Ｎ-1）/2-ｒ

　　　　Ｎ</sub>Ｄ_ｒ＝_Ｎ-1Ｄ₀＋_Ｎ-1Ｄ₁＋・・・＋_Ｎ-1Ｄ_ｒ　　（ただし、ｒ≦[Ｎ（Ｎ−１）/２]）


（３）　オイラーによる係数

　　　_ＮＥ_ｒ＝Σ_s=0〜ｒ-1 （-１）^ｓ・_Ｎ+1Ｃ_ｓ（ｒ−ｓ）^Ｎ　とすると、　Ｎ！＝Σ_{ｒ=1〜Ｎ Ｎ}Ｅ_ｒ

例　３！＝１＋４＋１　、４！＝１＋１１＋１１＋１　、５！＝１＋２６＋６６＋２６＋１


（４）　対称ではないが．．．

　　　Ｎ！＝Σ_ｒ=0〜Ｎ （-１）^Ｎ-ｒ・_ＮＣ_ｒ（ｘ＋ｒ）^Ｎ

例　２！＝₂Ｃ₀（ｘ＋０）²−₂Ｃ₁（ｘ＋１）²＋₂Ｃ₂（ｘ＋２）²＝ｘ²−２（ｘ＋１）²＋（ｘ＋２）²


（コメント）　１月１０日に頂いたものですが、アップが２月２６日になってしまいました。申し訳
　　　　　　ありません。いろいろな見方が出来て、ためになりました！


　階乗及び累乗の分割について、Ｋ．Ｓ．さんからの続報です。（平成２４年３月２８日付け）
３月１日付けでメールをいただいて、そのままになっていました。Ｋ．Ｓ．さんにお詫び申し上
げます。

（５）　第１種スターリング数による階乗の分割

　ｎ≧ｋ≧０　に対して、ｘ（ｘ＋１）（ｘ＋２）・・・（ｘ＋ｎ−１）のｘ^ｋの係数を、_ｎＳ_ｋ と表し、第１種
スターリング数と言う。ただし、₀Ｓ₀＝１ とする。

例　_ｎＳ₀　・・・　定義より、明らかに定数項は、０　なので、_ｎＳ₀＝０

　　_ｎＳ₁　・・・　ｘ の係数は、（ｎ−１）！　なので、_ｎＳ₁＝（ｎ−１）！

　　_ｎＳ_ｎ-1　・・・　ｘ^ｎ-1 の係数は、１＋２＋・・・＋（ｎ−１）＝ｎ（ｎ−１）/２　なので、

_ｎＳ_ｎ-1＝ｎ（ｎ−１）/２

　　_ｎＳ_ｎ　・・・　ｘ^ｎ の係数は、１　なので、_ｎＳ_ｎ＝１

　ｎ＞ｋ＞０　に対して、次の漸化式が知られている。：　_ｎ+1Ｓ_ｋ＝_ｎＳ_ｋ-1＋ｎ・_ｎＳ_ｋ

　実際に、　ｘ（ｘ＋１）（ｘ＋２）・・・（ｘ＋ｎ−１）（ｘ＋ｎ）
　　　　　　＝ｘ²（ｘ＋１）（ｘ＋２）・・・（ｘ＋ｎ−１）＋ｎ・ｘ（ｘ＋１）（ｘ＋２）・・・（ｘ＋ｎ−１）

において、左辺のｘ^ｋの係数は、_ｎ+1Ｓ_ｋ で、右辺のｘ^ｋの係数は、

　　ｘ（ｘ＋１）（ｘ＋２）・・・（ｘ＋ｎ−１）のｘ^ｋ-1の係数に
　　ｘ（ｘ＋１）（ｘ＋２）・・・（ｘ＋ｎ−１）のｘ^ｋの係数をｎ倍して加えたものに等しいので、

　_ｎ+1Ｓ_ｋ＝_ｎＳ_ｋ-1＋ｎ・_ｎＳ_ｋ　が成り立つことが分かる。

　このとき、　Ｎ！＝Σ_{ｒ=0〜Ｎ N}Ｓ_ｋ　が成り立つ。

（６）　オイラーの係数による階乗の分割

　オイラーの係数 Ｔ（ｎ，ｋ）　（→　参考；「Ａ００８２９２」）について、

　漸化式　Ｔ（ｎ，ｋ）＝（ｎ−ｋ＋１）Ｔ（ｎ−１，ｋ−１）＋ｋＴ（ｎ−１，ｋ）

　　　　　　Ｔ（ｎ，１）＝Ｔ（ｎ，ｎ）＝１

が成り立つ。このとき、

　　　Ｎ！＝Σ_ｒ=0〜Ｎ Ｔ（ｎ，ｋ）　が成り立つ。

　上記の三角形は、オイラーの三角形と言われる。



　　　以下、工事中