组合数

从五个不同的数中选出三个不同的数的方法恰好有十种，即$\binom{5}{3}=10$ （注：我国教材中常写作$C_5^3$），一般地，组合数公式如下： $$\binom{n}{k}=\frac{n!}{(n-k)!k!}.$$ 可以验证，当$n=23$时首次出现超过一百万的组合数：$\binom{23}{10}=1144066$。

对$1\le n\le 100$，有多少个不同形式的组合数$\binom{n}{k}$超过一百万？

本题难度:

解答

数字不大，直接计算也没有问题，不过为了避免不必要的高精度计算，可以用递推公式$\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$，再把大于一百万的值都置为一百万零一。结果是$4075$。

infty=1000001
t=0
b=[1,1]
for n in range(2,101):
    b=[1]+[min(b[k-1]+b[k],infty) for k in range(1,n)]+[1]
    t+=b.count(infty)
print t