■角柱と反角柱(その26)

 漸化式を解いてみると

  f(n,0)=2^n-1 → OK

  f(n,1)=2^n-2(n−1)n/2 → OK

  f(n,2)=2^n-2n(n−1)(n−2)/3 → OK

  f(n,3)=2^n-4n(n−1)(n−2)^2/3 → OK

  f(n,n−1)=2^n-1+2n → n>3のとき,OK

 k>2では

  f(n,k)=n!/(k+1)!(n−k)!{2^n-1(n−k)+2^n-k(k+1)}

ときれいな形にまとまった.

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

 これより

  f(n,k)=2^n-kn!/k!(n−k)!+2^n-1n!/(k+1)!(n−k−1)!

=2^n-k(n,k)+2^n-1(n,k+1)

となるが,右辺第1項はn次元立方体のk面数公式である.

 n次元立方体のk面数公式とn次元正軸体のk面数公式は

  k ←→ n−k−1

と置き換えたものである.右辺第2項はn次元正軸体のk面数公式

  2^k+1(n,k+1)

と似ているが,そうではない.

  2^n-1(n,k+1)=2^n-k-2・2^k+1(n,k+1)

=2^n-k-2・n次元正軸体のk面数

=2^n-k-2・n次元正立方体のn−k−1面数

であるから,右辺第2項はn次元立方体のn−k−1面数に2^n-k-2をかけたものということになる.

 すなわち,

  f(n,k)=n次元立方体のk面数+2^n-k-2(n次元立方体のn−k−1面数)

ということになる.k>2であるから

  f(n,3)=n次元立方体の3次元面数+2^n-5(n次元立方体のn−4次元面数)

  f(n,4)=n次元立方体の4次元面数+2^n-6(n次元立方体のn−5次元面数

  f(n,n−1)=n次元立方体のn−1次元面数+2^-1(n次元立方体の0次元面数)=2n+2^n-1

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