C Program to find Binomial Coefficients

The binomial coefficient C(n, k) — read as “n choose k” — counts the number of ways to choose k items from a set of n distinct items, regardless of order. It appears in the expansion (x + a)ⁿ as the coefficient of each term, in probability calculations, in Pascal’s triangle, and in combinatorics.

There are three standard ways to compute binomial coefficients: the recursive formula (Pascal’s rule), the multiplicative formula, and the factorial formula. This program uses Pascal’s triangle built bottom-up with dynamic programming — no recursion, no factorial, no overflow risk for n ≤ 20.

Pascal’s Triangle and the DP Recurrence

Pascal’s rule says: C(i, j) = C(i−1, j−1) + C(i−1, j), with base cases C(i, 0) = C(i, i) = 1. Building row by row gives every binomial coefficient up to row n in O(n²) time and O(n²) space — and the answer C(n, k) is simply the k-th entry in the last row.

C Program to Find Binomial Coefficient

/* Binomial coefficient C(n,k) using Pascal's triangle (DP)
 * No recursion, no factorial — builds each row from the previous.
 * Compile: gcc -ansi -Wall -Wextra binomial.c -o binomial */
#include <stdio.h>

int main(void)
{
    int n, k, i, j;
    int c[21][21];

    printf("Enter n and k (0 <= k <= n <= 20): ");
    scanf("%d %d", &n, &k);

    if (n < 0 || k < 0 || k > n || n > 20) {
        printf("Error: need 0 <= k <= n <= 20.\n");
        return 1;
    }

    /* build full Pascal's triangle up to row n */
    for (i = 0; i <= n; i++) {
        for (j = 0; j <= i; j++) {
            if (j == 0 || j == i)
                c[i][j] = 1;
            else
                c[i][j] = c[i-1][j-1] + c[i-1][j];
        }
    }

    printf("C(%d, %d) = %d\n", n, k, c[n][k]);

    printf("\nPascal's triangle (rows 0 to %d):\n", n);
    for (i = 0; i <= n; i++) {
        for (j = 0; j <= i; j++)
            printf("%4d", c[i][j]);
        printf("\n");
    }

    return 0;
}

How to Compile and Run

gcc -ansi -Wall -Wextra binomial.c -o binomial
./binomial

Sample Output

# Enter n=5, k=2:
Enter n and k (0 <= k <= n <= 20): 5 2
C(5, 2) = 10

Pascal's triangle (rows 0 to 5):
   1
   1   1
   1   2   1
   1   3   3   1
   1   4   6   4   1
   1   5  10  10   5   1

# Enter n=10, k=3:
C(10, 3) = 120

# Enter n=20, k=10:
C(20, 10) = 184756

Step-by-Step DP Trace: C(4, 2)

Result: c[4][2] = 6. The 4 people can be paired into 6 distinct 2-person groups.

Code Explanation

• int c[21][21] — a 2D array indexed from 0 to 20. Because C89 requires array sizes to be compile-time constants, 21 is hard-coded. For n ≤ 20, every binomial coefficient fits in a 32-bit int (C(20,10) = 184,756).
• Base cases: j == 0 || j == i — the first and last element of every row is always 1. This is C(n, 0) = 1 (one way to choose nothing) and C(n, n) = 1 (one way to choose everything).
• Inner formula: c[i][j] = c[i-1][j-1] + c[i-1][j] — Pascal’s rule. Each entry is the sum of the entry directly above-left and directly above. This reuses already-computed values (overlapping subproblems) — the defining property of dynamic programming.
• Loop bound j <= i — only fills entries c[i][0] through c[i][i], matching the triangle shape. Values beyond column i are undefined in the array and are never accessed.
• Input validation — checks k > n (choosing more than you have — impossible, but the array read c[n][k] could go out of bounds without this guard) and n > 20 (prevents array overflow).

Why DP Beats Factorial for Large n

What This Program Teaches

• Dynamic programming with a 2D table — each cell depends only on two cells in the row above, making Pascal’s triangle the classic entry-point to DP. The same “fill table bottom-up, read the answer from [n][k]” pattern appears in longest common subsequence, edit distance, and knapsack problems.
• Avoiding overflow with DP — the intermediate values in Pascal’s triangle are always binomial coefficients themselves, which are far smaller than factorials. For n ≤ 20, every value fits comfortably in an int.
• Two-variable input validation — the condition k > n must be caught before the 2D array access. Otherwise c[n][k] reads an uninitialized element (undefined behavior in C) and the output is meaningless.
• Triangle-shaped iteration — the inner loop runs 1, 2, 3, … n+1 times for rows 0 through n. Total iterations = n(n+1)/2 — the same triangular-number formula that counts entries in Pascal’s triangle.

Related Programs

• Combinations and Permutations in C
• Pascal’s Triangle in C
• Fibonacci using Recursion in C
• GCD and LCM using Recursion in C
• Fibonacci Terms using Array in C

Recommended book:
The C Programming Language — Kernighan & Ritchie (India) |
(US)
 | 
C Programming: A Modern Approach — K.N. King (India) |
(US)

Practice what you learned: C Aptitude Questions — or try our C Programming Quiz App on Android.