CODEWITHSUNDEEP
pythonalgorithmcombinationsbinomial-coefficients
Mark Rewath
Mark Rewath

Reputation: 11

Efficient python code to calculate partial sum of binomial coefficients

I mean to say, what's the most efficient code possible to write for calculating the sum of binomial coefficients n choose k, where n is fixed and you only want the sum to the first k terms, knowing that k < n.

For example, if n = 4 and k = 2 then you should receive 11 because it'll be 1 + 4 + 6. Most of the code I've been able to find is just written for computing a single binomial coefficient rather than a partial sum, or is giving some sort of approximation that works well for large numbers but not small ones.

Upvotes: 0

Views: 178

Answers (2)

Alain T.
Alain T.

Reputation: 42133

You can obtain the sum iteratively without using factorials. Compute the terms of pascal triangle line #N relative to each other and add them up. The number of iterations can be optimized by leveraging the symmetry of a pascal triangle line knowing that the total is always 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

output:

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

To see the intermediate results (progression of t), the function can be converted to a generator that will produce pascal line #N up to coefficient k:

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

Using this one with sum() gives the same result as binSum():

sum(pascal(4,2)) # 11

Upvotes: 0

Navid Naseri
Navid Naseri

Reputation: 126

This is a linear answer for the question:
First we prove that (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)

Now we can find kCn using (k-1)Cn in a constant time:

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

As we know 1Cn is always equal to n. So we can find the sequence(and sum of the sequence) of 1Cn ... kCn in a linear time:

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

Upvotes: 1

Related Questions