053. 组合选择(Combinatoric selections)

从12345这个数字中挑选出三个数共有十种方式:

$$ 123, 124, 125, 134, 135, 145, 234, 235, 245,345 $$
在组合学中,我们将其记为\(C(5,3)=10\)。一般地:
$$ C(n,r)=\frac{n!}{r!(n-r)!},\ where\ r\le n $$
其中\(n!=n\times(n-1)\times\cdots\times3\times2\times1\)\(0!=1\)。我们可以发现,只到\(n=23\),才有一个组合数\(C(23,10)=1144066\)超过了一百万。那么,对于\(1\le n\le 100\)中有多少个\(C(n,r)\)大于一百万(可以重复计算)?

分析:我们在十五题中已经编写过计算组合数的函数,这里可以直接拿来用。当然,我们遍历一至一百,找到所有大于一百万的组合数,统计其个数即为题目所求,但还有一个效率更高的方法。我们知道对于特定的\(n\)\(C(n,r)\)先随着\(r\)的增加而增加,到达最大值后再随着\(r\)的增加而减少,且组合数具有对称性,即\(C(n,r)=C(n,n-r)\)。显然,如果\(C(n,r)\)大于一百万,那么从\(C(n,r)\)\(C(n,n-r)\)中的所有数都会大于一百万,这样的数的个数\(k=(n-r)-r+1\),因此对于特定的\(n\),只要找到第一个大于一百万\(r\)的值,就不需要继续往后寻找,可以直接知道对于这个特定的\(n\),有多少个数会大于一百万。题目已经说明,在\(n=23,r=10\)时会有第一个数大于一百万,则我们可以从23开始遍历,依次寻找每个\(n\)值下大于一百万的第一个\(r\)值,然后计算出在这个\(n\)下有多少数大于一百万,最后把所有的值加总,即为在\(1\le n\le100\)时组合数大于一百万的个数。代码如下:

# time cost = 997 µs ± 5.72 µs

from math import factorial as fac

def comb_num(n,k):
    num = fac(n)/(fac(n-k)*fac(k))
    return num

def main():
    count = 0
    for n in range(23,101):
        for r in range(1,n//2):
            if comb_num(n,r) > 10**6:
                count += (n - 2*r + 1)
                break
    return count