2011-06-14

順列とpermutohedronの次元

Permutohedron 正多面体

組合せ最適化に関連してpermutohedronについて書いている(こちらとか)
「どうして(how)」ああいう形をしているのかについて考える
なぜ考えるかというと、permutohedronの頂点をグループ化したいから、グループ化する、ということはどういうことなのか、ということを考えたいから
まず、N個の要素の並べ方の場合の数について考える
- N個のうち、１つを選んで、残りのN-1個から１つを選んで、…という繰り返し、というのが一つの説明
- もう一つの説明を考える
  - N=1のボールの並べ方は１個、その長さは１。そのことを $S_1=1,L_1=1$ と書くことにする(Sは並べ方の数、Lは長さ)
  - N=2に増やすとき、置き場所は、既にあるボールの「前」に置くか、「後」に置くかの２通り。これは $L_1+1$ 通りの置き方がある、とも言い換えられる。式で書くと $S_2=S_1\times (L_1+1)$ 、また、長さはボールの数だから $L_2=L_1+1$
  - 漸化式になった。 $S_N=S_{N-1} \times (L_{N-1}+1)$ , $L_N=L_{N-1}+1$ , $S_1=1,L_1=1$
  - これを解くと $S_N=\prod_{i=1}^N i = N!$
これを幾何的に考えることにする
- N=1のとき、それは「点」がポツリとある、０次元な世界。ボールの配置は(b1)の一通り
- N=2にするときは、次元を１つ上げて、１次元にする。そのうえで、２個のボールの配置の仕方は２通り。(b1,b2)と(b2,b1)
  - このとき、(b1)の点を原点(0)とし、(b1,b2),(b2,b1)の点をそれぞれ、座標(0.5),(-0.5)に対応させることとする
  - 確かに次元は１つ上がった
  - ２個の点を「２−１＝１」次元空間に「平等」に配置した
- N=3にするときには、N=2のときの配置の場合の数２のそれぞれについて、３通りの置き方がある
  - ３つのものを「平等」に配置するためには、３−１＝２次元が必要で、「正三角形」の３頂点に配置すればよい
  - ２個のボールの並べ方２通りが原点から(-0.5),(0.5)にすでに置かれていて、この次元を使うわけにはもう行かないから、次元を２つ増やして３次元にしてみよう
  - 第２、第３の次元について、正三角形の頂点座標は $C(\cos(t),\sin(t));t=0,\frac{2\pi}{3},\frac{4\pi}{3}$ で与えればよい。１辺の長さが１の正三角形にするとすると、 $C=\frac{1}{\sqrt{3}}$ なのでから、(b1,b2,b3),(b1,b3,b2),(b3,b1,b2)は、 $(0.5,C\cos(t_1),C\sin(t_1)),(0.5,C\cos(t_2),C\sin(t_2)),(0.5,C\cos(t_3),C\sin(t_1)),=\frac{1}{\sqrt{3}}$ に配置し、(b2,b1,b3),(b2,b3,b1),(b3,b2,b1)は $(-0.5,C\cos(t_1),C\sin(t_1)),(-0.5,C\cos(t_2),C\sin(t_2)),(-0.5,C\cos(t_3),C\sin(t_1))$ に配置してみよう
  - これは、３次元空間にある三角柱
- N=4にすると、さらに４−１＝３次元を追加することになるので
- この方式では $\frac{N(N-1)}{2}$ 次元空間に順列を配置することになる
- これはpermutohedronとは異なるけれども、順列の「体系的な」配置方法の一つだろう
さて、N=3の場合に話を戻そう
- 正三角形を底面とする三角柱に６つの並べ方を対応させた
- いかにも、「非対称」で気持ちが悪い
- b1,b2,b3はたまたま1,2,3の番号が振られているだけで平等だとすると、もっと対称性の高い配置にできるはず
- では、６つの点(６つの並べ方)を３次元空間に配置するような配置の仕方で、「平等」なのは、「正●面体」である
- ３次元空間の正●面体は、「正四面体」「正六面体(立方体)」「正八面体」「正十二面体」「正二十面体」である(Wiki)
- このうち、頂点数が６個なのは、「正八面体」
正八面体に６つの順列を配置しよう
- 先の議論で、「２つのボール」の並べ方で１次元を使用し、そのあと、３番目のボールの配置の仕方が２次元平面上の正三角形の頂点に対応づけられることを見た
- 正八面体には正三角形が８面あり、４対を形成している
- この４対のうち、３対に(1,2)<->(2,1)に3を加えた正三角形２つ、(2,3)<->(3,2)に1を加えた正三角形２つ、(3,1)<->(1,3)に2を加えた正三角形２つを対応づけて、６頂点への順列の対応付けを取ることができる
- ここで気になることが残る
- ４対の正三角形対のうち、３対は、上記のように「意味を持たせ」ることができた。残った１対はどういう位置づけなのだろう？
  - わからないなりに、この正三角形の頂点に対応する配列は、第１、第２、第３要素のいずれも、重複していないことを特徴とする
さて。これ(『長さNの順列N!種類を $\frac{N(N-1)}{2}$ 次元空間の正多面体の頂点に対応づく。その正多面体は、頂点数がN!で、「面」は正N-1単体である』)が一般化できるものなのかどうか…
もう一つの方法を考えてみる
- 重複を許さない順列は、重複を許した順列から、「ただの１ペアでも重複していたら、取り除いた」ものである
- 重複順列は $N^N$
- N=2の場合の重複というのは、「対角成分」を除いたもの
- N=3の場合は、３つのペアのすべてのペアに関する対角成分を除いたもの
- Nを増やしてもどんどん「対角成分」を除いてやると、どんどん、除かれる成分の割合が増えて行き、ほとんど除かれる。 $N^N-N!$ が除かれる成分数