ａ1＞ａ2＞・・・＞ａnとするとき，（ａ1，ａ2，・・・，ａn）の添字を置換して得られるｎ！個の点からなる（ｎ−１）次元の多面体は置換多面体（順列多面体）と呼ばれる．とくにａ1＝ｎ，ａ2＝ｎ−１，・・・，ａn＝１の場合を指すこともある

　置換多面体は置換を１回適用することで同じものになる２頂点を辺で結んでできる．たとえば，ｎ＝４の場合の置換多面体で，頂点１３４２と結ばれるのは１４３２，１３２４，３１４２の３頂点である．

　この多面体は単純ゾノトープで，２^n−２個のファセットをもつ．したがって，ｎ次元置換多面体は（ｎ＋１）！個の頂点と２（２^n−１）個のファセットをもつことになる（２次元置換多面体は六角形，３次元置換多面体は切頂八、面体）．今回のコラムでは置換多面体の仲間たちを紹介したい．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【１】割当多面体

　ｎ次正方行列Ｍは，

［１］各成分が非負で，各行角列の和が１のとき，２重確率行列

［２］各行各列の成分に１がちょうど１つ現れ，他の成分が０のとき，置換行列

と呼ばれる．

　たとえば，置換行列

　　［０，１，０，０］

　　［０，０，０，１］

　　［１，０，０，０］

　　［０，０，１，０］

は完全２部グラフＫ4,4の完全マッチングと対応する．

　一方，任意の２重確率行列は，置換行列の凸結合で表現されることが，バーコフとフォン・ノイマンによって独立に示されている．そのため，２重確率行列全体は置換行列を端点とする凸多面体となり，割当多面体（バーコフ多面体，完全マッチング多面体，２重確率多面体）と呼ばれる．

　この多面体はｎ！個の頂点とｎ^2個のファセットをもつ（ｎ−１）^2次元の多面体である．割当多面体と置換多面体の間には射影写像がある．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【２】結合多面体

　カタラン数

　　｛Ｃn｝＝｛１，２，５，１４，４２，１３２，４２９，１４３０，４８６２，１６７９６，・・・｝

は，凸ｎ角形を対角線で三角形分割する仕方は何通りあるかとか，ｎ対のかみ合い括弧の種類数などいろいろな場面で登場する数なのですが，

　　Ｃn＝2nＣn／（ｎ＋１）＝（２ｎ）！／ｎ！（ｎ＋１）！，

　　Ｃn＝2n+1Ｃn／（２ｎ＋１），

あるいは

　　Ｃn＝2nＣn−2nＣn-1＝１，２，５，１４，４２，・・・

と表されます．

　結合多面体は，Ｃn-1＝2n-2Ｃn-1／ｎ個のファセットをもつ（ｎ−２）次元の多面体となります．たとえば，ｎ＝４の場合の結合多面体は，

　　（＊＊）（＊＊），＊（＊（＊＊）），＊（（＊＊）＊），（＊（＊＊））＊，（（＊＊）＊）＊

が５角形の頂点に対応し，そして辺は結合法則を１回適用することで同じものになる２頂点を結んでできます（２次元結合多面体は五角形，３次元結合多面体は１４面体）．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【３】置換結合多面体

　置換結合多面体はｎ個の文字を結合法則も置換もないものとして任意の順序で掛け合わせた表現に対応する（ｎ−１）次元の多面体である．すべての頂点が原点を中心とする球面に載っていて，球体のセル分割として実現できる（２次元置換結合多面体は１２角形，３次元置換結合多面体は切頂切稜ねじれ重三角錐に似た形）．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【補】カタラン数とオイラーの問題

　凸多角形（ｎ＋２角形）に対角線を描いて，それをいくつかの凸多角形に分けるのではなく，対角線を互いに交わらないように引いて三角形分割する問題を考えよう．

［Ｑ］凸ｎ＋２角形に互いに交わらないｎ−１本の対角線を引いて三角形分割する仕方の数ｃ（ｎ）は？

［Ａ］この問題はオイラーが提起した幾何学問題である（オイラーの問題）．４角形では２通り，５角形では５通りあることは数えられても，６角形ではそう簡単にはいかない（６角形に対しては１４通りある）．

　６角形の場合，たとえばある対角線を引いて３角形と５角形，４角形と４角形，５角形と３角形に分割することができるが，そのような分割の仕方を場合分けすることで，積和型の漸化式

　　ｃ（ｎ＋１）＝ｃ（０）ｃ（ｎ）＋ｃ（１）ｃ（ｎ−１）＋・・・＋ｃ（ｎ）ｃ（０）

が得られる．ただし，ｃ（０）＝ｃ（１）＝１とする．

　これはカタラン数の漸化式であって，カタラン数ｃ（ｎ）はｎの増加に応じて急激に増加する．

　　ｃ（０）＝１，ｃ（１）＝１，ｃ（２）＝２，ｃ（３）＝５，

　　ｃ（４）＝１４，ｃ（５）＝４２，ｃ（６）＝１３２，

　　ｃ（７）＝４２９，ｃ（８）＝１４３０，ｃ（９）＝４８６２，・・・

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

　カタラン数の一般項は

　　ｃ（ｎ）＝2nＣn／（ｎ＋１）＝（２ｎ）！／（ｎ＋１）！ｎ！

であるが，この公式は母関数を用いると簡明に得ることができる．

　カタラン数の母関数を

　　Ｃ（ｘ）＝ｃ（０）＋ｃ（１）ｘ＋ｃ（２）ｘ^2＋・・・＋ｃ（ｎ）ｘ^n＋・・・

とおく．これを２乗すると

　　Ｃ（ｘ）^2＝ｃ（０）ｃ（０）＋（ｃ（０）ｃ（１）＋ｃ（１）ｃ（０））ｘ＋ （ｃ（０）ｃ（２）＋ｃ（１）ｃ（１）＋ｃ（２）ｃ（０））ｘ^2＋・・・

　ここで，

　　ｃ（０）ｃ（０）＝ｃ（１）

　　ｃ（０）ｃ（１）＋ｃ（１）ｃ（０）＝ｃ（２）

　　ｃ（０）ｃ（２）＋ｃ（１）ｃ（１）＋ｃ（２）ｃ（０）＝ｃ（３）

であるから，

　　Ｃ（ｘ）^2＝ｃ（１）＋ｃ（２）ｘ＋ ｃ（３）ｘ^2＋・・・

次数を揃えるために，両辺にｘをかけて

　　ｘＣ（ｘ）^2＝ｃ（１）ｘ＋ｃ（２）ｘ^2＋ ｃ（３）ｘ^3＋・・・

　　ｘＣ（ｘ）^2＝Ｃ（ｘ）−ｃ（０）＝Ｃ（ｘ）−１

　Ｃ（ｘ）に関する２次方程式を解いて，母関数は

　　Ｃ（ｘ）＝｛１−（１−４ｘ）^1/2｝／２ｘ

ここでニュートンの二項展開により，一般項

　　ｃ（ｎ）＝2nＣn／（ｎ＋１）＝（２ｎ）！／（ｎ＋１）！ｎ！

が得られる．

　なお，凸ｎ角形を対角線で三角形分割する仕方は何通りあるかという問題は，回転や反転で同型になるものを同じと数えると，

　　１，１，１，３，４，１２，２７，８２，２２８，７３３，２２８２，７５２８，・・・

となることを付記しておく．

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

　カタラン数から一般項が何かを予想するのは難しいのですが，ここでは

　　Ｃn＝2nＣn／（ｎ＋１）　　　（Ｃ0＝１）

がわかっているものとして，母関数

　　Ｆ（ｔ）＝ΣＣnｔ^n

を求めてみます．

　この級数は，第０項：Ｃ0＝１から始まるので，そのまま項比をとると

　　ａn+1ｘn+1/ａnｘn=(n+1/2)(n+1)/(n+2)*4x/(n+1)

したがって，

　　Ｆ（ｘ）＝2Ｆ1(1/2,1,2,4x)=2/{1+(1-4x)^(1/2)}

　　　　　　＝{1-(1-4x)^(1/2)}/2x

　　(1-4x)^(1/2)＝Σ(-4)^k1/2Ck･ｘ^k

より

　　Ｃn＝-1/2(-4)^(n+1)1/2C(n+1)

これをさらに式変形すれば，

　　Ｃn＝2nＣn／（ｎ＋１）

になる．この結果，二項展開を丹念に使えば

　　{1-(1-4x)^(1/2)}/2x=Σ2nCnx^n/(n+1)

が得られるはず・・・．

　この方法は試してはいないのですが，かなり面倒そうです．実はカタラン数に対しては，漸化式

　　Ｃn＝ΣＣkＣn-k-1＝Ｃ0Ｃn-1＋Ｃ1Ｃn-2＋・・・＋Ｃn-1Ｃ0

が成り立つので，母関数は

　　Ｆ（ｔ）＝ΣＣnｔ^n＝ΣＣkｔ^kΣＣn-k-1ｔ^n-k＋１

　　　　　　＝Ｆ（ｔ）・ｔＦ（ｔ）＋１

すなわち，

　　ｔＦ（ｔ）^2−Ｆ（ｔ）−１＝０

なる２次方程式を満たすことが知られています．

　Ｃ0＝１を満足させなければならないので，複号は負号をとると，

　　Ｆ（ｔ）＝{1-(1-4x)^(1/2)}/2x

がでてきます．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝