■ピックの公式と三角形分割(その18)

 a1>a2>・・・>anとするとき,(a1,a2,・・・,an)の添字を置換して得られるn!個の点からなる(n−1)次元の多面体は置換多面体(順列多面体)と呼ばれる.とくにa1=n,a2=n−1,・・・,an=1の場合を指すこともある

 置換多面体は置換を1回適用することで同じものになる2頂点を辺で結んでできる.たとえば,n=4の場合の置換多面体で,頂点1342と結ばれるのは1432,1324,3142の3頂点である.

 この多面体は単純ゾノトープで,2^n−2個のファセットをもつ.したがって,n次元置換多面体は(n+1)!個の頂点と2(2^n−1)個のファセットをもつことになる(2次元置換多面体は六角形,3次元置換多面体は切頂八、面体).今回のコラムでは置換多面体の仲間たちを紹介したい.

===================================

【1】割当多面体

 n次正方行列Mは,

[1]各成分が非負で,各行角列の和が1のとき,2重確率行列

[2]各行各列の成分に1がちょうど1つ現れ,他の成分が0のとき,置換行列

と呼ばれる.

 たとえば,置換行列

  [0,1,0,0]

  [0,0,0,1]

  [1,0,0,0]

  [0,0,1,0]

は完全2部グラフK4,4の完全マッチングと対応する.

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

 この多面体はn!個の頂点とn^2個のファセットをもつ(n−1)^2次元の多面体である.割当多面体と置換多面体の間には射影写像がある.

===================================

【2】結合多面体

 カタラン数

  {Cn}={1,2,5,14,42,132,429,1430,4862,16796,・・・}

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

  Cn=2nCn/(n+1)=(2n)!/n!(n+1)!,

  Cn=2n+1Cn/(2n+1),

あるいは

  Cn=2nCn−2nCn-1=1,2,5,14,42,・・・

と表されます.

 結合多面体は,Cn-1=2n-2Cn-1/n個のファセットをもつ(n−2)次元の多面体となります.たとえば,n=4の場合の結合多面体は,

  (**)(**),*(*(**)),*((**)*),(*(**))*,((**)*)*

が5角形の頂点に対応し,そして辺は結合法則を1回適用することで同じものになる2頂点を結んでできます(2次元結合多面体は五角形,3次元結合多面体は14面体).

===================================

【3】置換結合多面体

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

===================================

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

 凸多角形(n+2角形)に対角線を描いて,それをいくつかの凸多角形に分けるのではなく,対角線を互いに交わらないように引いて三角形分割する問題を考えよう.

[Q]凸n+2角形に互いに交わらないn−1本の対角線を引いて三角形分割する仕方の数c(n)は?

[A]この問題はオイラーが提起した幾何学問題である(オイラーの問題).4角形では2通り,5角形では5通りあることは数えられても,6角形ではそう簡単にはいかない(6角形に対しては14通りある).

 6角形の場合,たとえばある対角線を引いて3角形と5角形,4角形と4角形,5角形と3角形に分割することができるが,そのような分割の仕方を場合分けすることで,積和型の漸化式

  c(n+1)=c(0)c(n)+c(1)c(n−1)+・・・+c(n)c(0)

が得られる.ただし,c(0)=c(1)=1とする.

 これはカタラン数の漸化式であって,カタラン数c(n)はnの増加に応じて急激に増加する.

  c(0)=1,c(1)=1,c(2)=2,c(3)=5,

  c(4)=14,c(5)=42,c(6)=132,

  c(7)=429,c(8)=1430,c(9)=4862,・・・

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

 カタラン数の一般項は

  c(n)=2nCn/(n+1)=(2n)!/(n+1)!n!

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

 カタラン数の母関数を

  C(x)=c(0)+c(1)x+c(2)x^2+・・・+c(n)x^n+・・・

とおく.これを2乗すると

  C(x)^2=c(0)c(0)+(c(0)c(1)+c(1)c(0))x+ (c(0)c(2)+c(1)c(1)+c(2)c(0))x^2+・・・

 ここで,

  c(0)c(0)=c(1)

  c(0)c(1)+c(1)c(0)=c(2)

  c(0)c(2)+c(1)c(1)+c(2)c(0)=c(3)

であるから,

  C(x)^2=c(1)+c(2)x+ c(3)x^2+・・・

次数を揃えるために,両辺にxをかけて

  xC(x)^2=c(1)x+c(2)x^2+ c(3)x^3+・・・

  xC(x)^2=C(x)−c(0)=C(x)−1

 C(x)に関する2次方程式を解いて,母関数は

  C(x)={1−(1−4x)^1/2}/2x

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

  c(n)=2nCn/(n+1)=(2n)!/(n+1)!n!

が得られる.

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

  1,1,1,3,4,12,27,82,228,733,2282,7528,・・・

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

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

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

  Cn=2nCn/(n+1)   (C0=1)

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

  F(t)=ΣCnt^n

を求めてみます.

 この級数は,第0項:C0=1から始まるので,そのまま項比をとると

  an+1xn+1/anxn=(n+1/2)(n+1)/(n+2)*4x/(n+1)

したがって,

  F(x)=2F1(1/2,1,2,4x)=2/{1+(1-4x)^(1/2)}

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

  (1-4x)^(1/2)=Σ(-4)^k1/2Ck・x^k

より

  Cn=-1/2(-4)^(n+1)1/2C(n+1)

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

  Cn=2nCn/(n+1)

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

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

が得られるはず・・・.

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

  Cn=ΣCkCn-k-1=C0Cn-1+C1Cn-2+・・・+Cn-1C0

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

  F(t)=ΣCnt^n=ΣCkt^kΣCn-k-1t^n-k+1

      =F(t)・tF(t)+1

すなわち,

  tF(t)^2−F(t)−1=0

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

 C0=1を満足させなければならないので,複号は負号をとると,

  F(t)={1-(1-4x)^(1/2)}/2x

がでてきます.

===================================