■源氏香図(その7)

 2円または3円が交わったヴェン図を描いたことがあるだろう.2円の場合,共通部分がひとつできるが,3円の場合は2円の共通部分が3つ,3円の共通部分がひとつできる.

 中学・高校で4円以上が取り扱われることはまずないが,n円となっても原理は同じである.それは,共通部分に含まれるものを引いて,引き過ぎた分を足し直してということを繰り返す包除原理である.

 包除公式の例として,第2種スターリング数やデーン・サマービル関係式をあげることができる.

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

【1】第2種スターリング数

 1≦k≦nとし,n個の数字をk個のグループに分ける方法の総数で,ただし,各グループは少なくとも1つの数字を含むものの数をnSkとする.

 nSkは第2種スターリング数と呼ばれるもので,漸化式

  n+1Sk=nSk-1+knSk

が成り立つ.

  nS1=1

  nS2=2^n-1−1=(2^n−2)/2!

  nS3=3^n-1/2−2^n-1+1/2=(3^n−3・2^n+3)/3!

  nS4=4^n-1/6−3^n-1/2+2^n-2−1/6=(4^n−4・3^n+6・2^n−4)/4!

 一般項は

  nSk=1/k!Σ(−1)^k-jkCjj^n

以下,

  nS5=(5^n−5・4^n+10・3^n−10・2^n+5)/5!

  nS6=(6^n−6・5^n+15・4^n−20・3^n+15・2^n−6)/6!

と続く.

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

【2】デーン・サマービル関係式

 各頂点がn本の辺上にあるn価のn次多面体(単純多面体)に対しては,デーン・サマービル関係式

  fk=Σ(0,k)(−1)^j(n−j,n−k)fj

が成り立つ.

 k次元面はn−k個のファセットの共通部分に含まれる,残りのn−j個のファセット上のあるものを引いて,引き過ぎた分を足し直してということを繰り返した包除公式である.

 単純n次多面体に対して,与えられたj次面を含むk次面の数は(n−j,n−k)になる.k=nのときがオイラー関係式

  fn=Σ(0,n)(−1)^jfj

であるが,オイラー関係式は単純多面体だけでなく任意の多面体に対して成り立つ.

 デーンは1905年に5次元においてこの関係式を証明した.およそ20年後の1927年,サマービルが一般の場合を証明した.

[例]空間充填2(2^n−1)胞体の面数はデーン・サマービル関係式を満たす.

2次元:(f0,f1)=(6,6)

3次元:(f0,f1,f2)=(24,36,14)

4次元:(f0,f1,f2,f3)=(120,240,150,30)

5次元:(f0,f1,f2,f3,f4)=(720,1800,1560,540,62)

6次元:(f0,f1,f2,f3,f4,f5)=(5040,15120,16800,8400,1806,126)

[例]3^n−1胞体の面数はデーン・サマービル関係式を満たす.

2次元:(f0,f1)=(8,8)

3次元:(f0,f1,f2)=(48,72,26)

4次元:(f0,f1,f2,f3)=(384,768,464,80)

5次元:(f0,f1,f2,f3,f4)=(3840,9600,8160,2640,242)

6次元:(f0,f1,f2,f3,f4,f5)=(46080,138240,151680,72960,14168,728)

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