计算二项式系数部分和的高效Python代码

Question

我的意思是说，计算二项式系数 n 选择 k 的总和可能编写的最有效的代码是什么，其中 n 是固定的，并且您只需要前 k 项的总和，知道 k < n.

例如，如果 n = 4 且 k = 2，那么您应该收到 11，因为它将是 1 + 4 + 6。我能找到的大多数代码只是为了计算单个二项式系数而编写的，而不是为了计算单个二项式系数。部分总和，或者给出某种近似值，该近似值适用于大数，但不适用于小数。

Answer 1

这是问题的线性答案：
首先我们证明 (nC(k+1))/(nCk) = (n-k)/(k+1)

(nC(k+1))/nCk = (n!/(k+1)!(n-k-1)!) / (n!/k!(n-k)!)  
= (k!(n-k)!) / ((k+1)!(n-k-1)!)  
= (k!(n-k)(n-k-1)!) / ((k+1)(k!)(n-k-1)!)  
= (n-k) / (k+1)  

---

现在我们可以使用 (k-1)Cn 在恒定时间内找到 kCn：

def get_bin_co(n, k, prev):
    frac = (n - (k - 1)) / k # note that k here is k+1 in formula
    return prev * frac

众所周知，1Cn 始终等于 n。所以我们可以在线性时间内找到 1Cn ... kCn 的序列（以及序列的和）：

def get_sum(n, k):
    res = 1 + n # initial 1 is for 0Cn
    prev = n
    for i in range(2, k + 1):
        prev = get_bin_co(n, k, prev)
        res += prev
    return res

Answer 2

您可以迭代获得总和，而无需使用阶乘。计算帕斯卡三角形线#N 相对于彼此的项并将它们相加。迭代次数可以通过利用帕斯卡三角线的对称性来优化，因为知道总数始终为 2^N。

def binSum(n,k):
    if k == n  : return 2**n
    if k+k > n : return 2**n - binSum(n,n-k-1)
    s,t = 1,1
    for i in range(k):
       t = t*(n-i)//(i+1)
       s += t
    return s

输出：

for n in range(4,8):
    for k in range(n+1):
        print((n,k),binSum(n,k))

(4, 0) 1
(4, 1) 5
(4, 2) 11
(4, 3) 15
(4, 4) 16
(5, 0) 1
(5, 1) 6
(5, 2) 16
(5, 3) 26
(5, 4) 31
(5, 5) 32
(6, 0) 1
(6, 1) 7
(6, 2) 22
(6, 3) 42
(6, 4) 57
(6, 5) 63
(6, 6) 64
(7, 0) 1
(7, 1) 8
(7, 2) 29
(7, 3) 64
(7, 4) 99
(7, 5) 120
(7, 6) 127
(7, 7) 128

要查看中间结果（

t

的进展），可以将该函数转换为生成器，该生成器将生成高达系数 k 的帕斯卡线 #N：

def pascal(n,k):
    t = 1
    yield t
    for i in range(k):       
       t = t*(n-i)//(i+1)
       yield t

for n in range(10): print(*pascal(n,n))

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

将其与

sum()

一起使用可得到与

binSum()

相同的结果：

sum(pascal(4,2)) # 11