■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)と同じで,思ったほど影響を受けないことがわかる.
===================================