■fベクトルの見積もり(その12)

 fベクトルの最大値は[d/2]と[(3d−1)/4]の間にくるという.(その8)では

  fk≦(n,k)f0=n!f0/(n/2)!(n/2)!

n!/(n/2)!(n/2)!〜(2πn)^1/2(n/e)^n/(πn)(n/2e)^n=(2/πn)^1/2・2^n

としたが,

n!/(3n/4)!(n/4)!

ではどうなるだろうか?

n!/(3n/4)!(n/4)!〜(2πn)^1/2(n/e)^n/(6πn/4)^1/2(2πn/4)^1/2(3n/4e)^3n/4(n/4e)^n/4=(8/3πn)^1/2・4^3n/4/3^n

すなわち,

  fk≦(8/3πn)^1/2・4^n/3^3n/4・f0

となる.

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

【1】置換多面体の場合

  f0=(n+1)!

  fn-1=2(2^n−1)

  (8/3πn)^1/2・4^n/3^3n/4・(n+1)!>2^64

  (8/3πn)^1/2・4^n/3^3n/4・(2π(n+1))^1/2((n+1)/e)^(n+1)>2^64

 (16(n+1)/3n)^1/2・4^n/3^3n/4・((n+1)/e)^(n+1)>2^64

  1/2・ln16/3+2nln2−3n/4・ln3+(n+1){ln(n+1)−1}>64ln2

  n=17でオーバーフローすることがわかる.

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

【2】正軸体版の場合

  f0=2^nn!

  fn-1=3^n−1

  (8/3πn)^1/2・4^n/3^3n/4・2^n・2^nn!>2^64

  (8/3πn)^1/2・2^3n/3^3n/4・n!>2^64

  (8/3πn)^1/2・2^3n/3^3n/4・(2πn)^1/2(n/e)^n>2^64

  (16/3)^1/2・2^3n/3^3n/4・(n/e)^n>2^64

1/2・ln(16/3)+3nln2−3n/4ln3+n(lnn−1}>64ln2

  n=15でオーバーフローすることがわかる.

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

[雑感]結果は(その8)と同じで,思ったほど影響を受けないことがわかる.

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