A dynamic programming approach to the n-couples problem

ncouples.py

from math import factorial


def binomial_coefficient(n, k):
    """
    Find the binomial coefficient of nCk. This is space efficient
    because it doesn't store the entire Pascal's Triangle; only the
    current row you're working on.
    :param n:
    :param k:
    :return:
    """
    # We only need to store up to k integers for the row of
    # Pascal's Triangle
    b = [0 for _ in range(k + 1)]
    b[0] = 1
    for i in range(1, n + 1):
        # start at the last integer (up to the kth one)
        # of the last row and calculate the new row
        j = min(i, k)
        while j > 0:
            b[j] += b[j - 1]
            j -= 1
    # We've found nCk
    return b[k]


def no_couples(n):
    total = 0
    for k in range(0, n + 1):
        # (nCk)*2^k*(2n-k)!*(-1)^k
        total += binomial_coefficient(n, k) * 2 ** k * factorial(2 * n - k) * (-1) ** k
    return total

for x in range(11):
    print "{}: {}".format(x, no_couples(x))