nk / nCk < k! + 1
となるnを、明示的になるべく小さくなるように求めようという話でした。このnをNとします。
逆数を取って、
P ≡ 1...(1 - (k - 1) / N) > 1 / (1 + 1 / k!)
さて、こういうのはlogを取って積分で近似するのが定番です。
log 1 + ... + log(1 - (k - 1) / N) > -log(1 + 1 / k!) > -1 / k!
問題は左辺ですが、これを積分で上から押さえます。
上に凸なので真ん中での近似が使えないため、三角形を引いて近似をより正確にしています。下の図で赤の部分の面積を積分から青の部分を引いて求めるイメージです。
ε ≡ k / N
ここで近似を使います。第2項は、
(1 - x)log(1 - x) = -x + x2 / 2 + x3 / 6 + x4 /12 + ... > -x + x2 / 2 (0 < x < 1)
第3項を上から押さえるのは難しいです。これを
log(1 - x) ≒ -x
と近似すると、
整理して、
N > k! (k2 - k) / 2
これだと少し間違っています。
k exact rough 1 2 0 2 4 2 3 21 18 4 149 144 5 1207 1200 6 10810 10800 7 105853 105840 8 1128977 1128960 9 13063701 13063680 10 163296026 163296000
こう補正するとほぼ合います。
N > k! (k^2 - k) / 2 + k^2 / 4 + k / 12 + 1
k exact rough 1 2 1 2 4 4 3 21 21 4 149 149 5 1207 1207 6 10810 10810 7 105853 105853 8 1128977 1128977 9 13063701 13063701 10 163296026 163296026 11 2195424031 2195424031 12 31614105637 31614105638 13 485707622444 485707622444 14 7933224499250 7933224499251 15 137305808640058 137305808640058 16 2510734786560066 2510734786560066 17 48373490221056074 48373490221056074 18 979563176976384083 979563176976384083 19 20801312169910272092 20801312169910272092 20 462251381553561600102 462251381553561600102 21 10729097856058982400112 10729097856058982400112 22 259644168116627374080123 259644168116627374080123 23 6540560234937899089920134 6540560234937899089920134 24 171243758878374085263360146 171243758878374085263360147 25 4653363012999295795200000159 4653363012999295795200000159 26 131069724866146831564800000171 131069724866146831564800000172 27 3821993177096841608429568000185 3821993177096841608429568000185 28 115247794263227839269568512000199 115247794263227839269568512000199 29 3589755369458318993544708096000213 3589755369458318993544708096000213 30 115384994018303110506794188800000228 115384994018303110506794188800000228
でも、どうしてもうまくいかない。
