Dynamic Programming | Set 9 (Binomial Coefficient) | GeeksforGeeks

Dynamic Programming | Set 9 (Binomial Coefficient) | GeeksforGeeks
Write a function that takes two parameters n and k and returns the value of Binomial Coefficient C(n, k).

A binomial coefficient C(n, k) also gives the number of ways, disregarding order, that k objects can be chosen from among n objects; more formally, the number of k-element subsets (or k-combinations) of an n-element set.

C(n, k) = C(n-1, k-1) + C(n-1, k)
C(n, 0) = C(n, n) = 1

The following code only uses O(k) space.

Also check EPI Java Solution: ComputingBinomialCoefficients.java

int binomialCoeff(int n, int k)

{

    int* C = (int*)calloc(k+1, sizeof(int));

    int i, j, res;

    C[0] = 1;

    for(i = 1; i <= n; i++)

    {

        for(j = min(i, k); j > 0; j--) // backwards, as C[j], C[j-1] still keep old value.

            C[j] = C[j] + C[j-1];

    }

    res = C[k];  // Store the result before freeing memory

    free(C);  // free dynamically allocated memory to avoid memory leak

    return res;

}

int binomialCoeff(int n, int k)

{

    int C[n+1][k+1];

    int i, j;

    // Caculate value of Binomial Coefficient in bottom up manner

    for (i = 0; i <= n; i++)

    {

        for (j = 0; j <= min(i, k); j++) // we don't need to fill until k.

        {

            // Base Cases

            if (j == 0 || j == i)

                C[i][j] = 1;

            // Calculate value using previosly stored values

            else

                C[i][j] = C[i-1][j-1] + C[i-1][j];

        }

    }

    return C[n][k];

}

Java code:

https://programming4interviews.wordpress.com/2011/07/12/binomial-coefficients-cn-k/
It's better we separate base cases from loop: cleaner code, and a little better performance, or even extract as method.

        long[][] binomial = new long[n+1][k+1];
        // base cases
        for (int i = 0; i <= n; i++) {
            binomial[i][0] = 1;
        }
        for (int j = 1; j <= k; j++) {
            binomial[0][j] = 0;
        }
        // bottom-up dynamic programming
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                binomial[i][j] = binomial[i-1][j-1] + binomial[i-1][j];
            }
        }

http://www.geeksforgeeks.org/space-and-time-efficient-binomial-coefficient/

C(n, k) = n! / (n-k)! * k!
        = [n * (n-1) *....* 1]  / [ ( (n-k) * (n-k-1) * .... * 1) * 
                                    ( k * (k-1) * .... * 1 ) ]
After simplifying, we get
C(n, k) = [n * (n-1) * .... * (n-k+1)] / [k * (k-1) * .... * 1]

Also, C(n, k) = C(n, n-k)  // we can change r to n-r if r > n-r

Time Complexity: O(k)

int binomialCoeff(int n, int k)

{

    int res = 1;

    // Since C(n, k) = C(n, n-k)

    if ( k > n - k )

        k = n - k;

    // Calculate value of [n * (n-1) *---* (n-k+1)] / [k * (k-1) *----* 1]

    for (int i = 0; i < k; ++i)

    {

        res *= (n - i);

        res /= (i + 1);

    }

    return res;

}

Java code: http://rosettacode.org/wiki/Evaluate_binomial_coefficients#Java

    private static long binomial(int n, int k)
    {
        if (k>n-k)
            k=n-k;
 
        long b=1;
        for (int i=1, m=n; i<=k; i++, m--)
            b=b*m/i;
        return b;
    }

Following are common definition of Binomial Coefficients.
1) A binomial coefficient C(n, k) can be defined as the coefficient of X^k in the expansion of (1 + X)^n.

2) A binomial coefficient C(n, k) also gives the number of ways, disregarding order, that k objects can be chosen from among n objects; more formally, the number of k-element subsets (or k-combinations) of an n-element set.

Read full article from Dynamic Programming | Set 9 (Binomial Coefficient) | GeeksforGeeks