nCr / Pascal Triangle

Why nCr / Pascal Triangle Matters

You have five volunteers and need a team of two. How many different teams can you form? Listing them works for five people, but becomes impractical for hundreds. The binomial coefficient C(n, r), pronounced “n choose r” and often written nCr, counts ways to select r distinct items from n distinct items when order does not matter and repetition is not allowed. Here, C(5, 2) = 10: choosing Alice and Ben gives the same team as choosing Ben and Alice.

Pascal's triangle computes these counts by addition. Each interior entry is the sum of the two entries above it. This lesson turns that picture into a dynamic programming algorithm, compresses its storage to one array, and explains the update order that keeps the answer correct. The same counts describe shortest grid routes, fixed-weight binary strings, and coefficients in binomial expansions.

Core Concepts and Terminology

The input is a nonnegative integer n and an integer r. For 0 ≤ r ≤ n, the output is C(n, r) = n! / (r!(n − r)!). We define C(n, r) = 0 when r < 0 or r > n; negative n is an invalid input for this lesson. The boundary values C(n, 0) = C(n, n) = 1 include C(0, 0) = 1: there is exactly one way to select nothing.

To understand the recurrence, single out the last volunteer. Teams excluding that volunteer choose all r members from the other n − 1 people. Teams including that volunteer choose their remaining r − 1 members from those same people. Every team belongs to exactly one group, so we add the counts.

Row numbering starts at zero. Row n contains C(n, 0), C(n, 1), …, C(n, n); thus the top “1” is row 0. Symmetry, C(n, r) = C(n, n − r), follows because choosing a team uniquely determines who is left out.

How nCr / Pascal Triangle Works, Step by Step

A full triangle stores every row, but the recurrence only needs the preceding row. We can go further and reuse a single array. Set k = min(r, n − r), allocate k + 1 entries, initialize dp[0] = 1, and initialize the other entries to zero. Entries beyond a row's diagonal represent impossible selections and remain zero until first reached.

For each row i from 1 through n, visit j from min(i, k) down to 1 and replace dp[j] with dp[j] + dp[j − 1]. Leave dp[0] equal to 1. After row n, return dp[k]. If r is outside 0…n, return zero before allocating; if k = 0, return one immediately.

The descending order is essential. When updating column j, both dp[j] and dp[j − 1] must still come from the previous row. Columns to the right have already been updated, but neither operand has. A left-to-right loop would reuse a value from the new row and count too much.

The diagram uses ordinary counts. The programs below apply “mod M” after each addition; the same control flow and proof then hold for remainders.

flowchart TD
    A["Read n and r"] --> B{"n negative?"}
    B -->|Yes| X["Reject input"]
    B -->|No| C{"r outside 0 through n?"}
    C -->|Yes| Z["Return 0"]
    C -->|No| D["k = min(r, n - r)"]
    D --> E{"k = 0?"}
    E -->|Yes| O["Return 1"]
    E -->|No| F["dp = [1, 0, ..., 0]; i = 1"]
    F --> G{"i at most n?"}
    G -->|No| R["Return dp[k]"]
    G -->|Yes| H["j = min(i, k)"]
    H --> I{"j at least 1?"}
    I -->|Yes| J["dp[j] = (dp[j] + dp[j - 1]) mod M"]
    J --> K["j = j - 1"]
    K --> I
    I -->|No| L["i = i + 1"]
    L --> G

Worked Example with a Full Trace

Compute C(5, 2). Symmetry gives k = min(2, 3) = 2, so we keep just three entries. Begin with row 0: [1, 0, 0]. The final zero means “there are no ways to choose two items from zero items,” rather than an uninitialized value.

Every assignment is recorded below. In each addition, the first term is the old dp[j] and the second is the old dp[j − 1].

1. Row i = 1: j = 1: 0 + 1 = 1 → [1, 1, 0]. Column 2 is not visited.
2. Row i = 2: j = 2: 0 + 1 = 1 → [1, 1, 1]; then j = 1: 1 + 1 = 2 → [1, 2, 1].
3. Row i = 3: j = 2: 1 + 2 = 3 → [1, 2, 3]; then j = 1: 2 + 1 = 3 → [1, 3, 3].
4. Row i = 4: j = 2: 3 + 3 = 6 → [1, 3, 6]; then j = 1: 3 + 1 = 4 → [1, 4, 6].
5. Row i = 5: j = 2: 6 + 4 = 10 → [1, 4, 10]; then j = 1: 4 + 1 = 5 → [1, 5, 10].

Return dp[2] = 10. Independently, the ten teams from A, B, C, D, E are AB, AC, AD, AE, BC, BD, BE, CD, CE, and DE. The formula agrees: 5 × 4 / (2 × 1) = 10.

Implementation in Python, C++, and Java

All three programs use the same descending update and the explicit modulus M = 1,000,000,007. They return C(n, r) modulo M, which equals the full count only when that count is smaller than M. The six sample counts satisfy that condition. Modular addition is exact integer arithmetic; no floating-point factorials or divisions are involved. Pascal addition works for any positive modulus, whether prime or composite.

Each tab is a complete, standalone program with its own imports and sample data, so any one of them can be copied and run on its own.

Python uses its built-in arbitrary-precision integers. C++ uses long long; because each stored residue is below M, each sum is at most 2M − 2 = 2,000,000,012 and fits safely. Java uses BigInteger and explicitly reduces each sum. The programs reject negative n and return zero for an out-of-range r.

MOD = 1_000_000_007


def ncr_mod(n: int, r: int) -> int:
    if n < 0:
        raise ValueError("n must be nonnegative")
    if r < 0 or r > n:
        return 0
    k = min(r, n - r)
    if k == 0:
        return 1
    dp = [0] * (k + 1)
    dp[0] = 1
    for i in range(1, n + 1):
        for j in range(min(i, k), 0, -1):
            dp[j] = (dp[j] + dp[j - 1]) % MOD
    return dp[k]


def main() -> None:
    samples = [(5, 2), (6, 3), (0, 0), (5, 0), (5, 5), (3, 4)]
    print(f"modulus = {MOD}")
    for n, r in samples:
        print(f"C({n}, {r}) = {ncr_mod(n, r)}")


if __name__ == "__main__":
    main()

#include <algorithm>
#include <iostream>
#include <stdexcept>
#include <utility>
#include <vector>

constexpr long long MOD = 1'000'000'007LL;

long long ncr_mod(int n, int r) {
    if (n < 0) {
        throw std::invalid_argument("n must be nonnegative");
    }
    if (r < 0 || r > n) {
        return 0;
    }
    const int k = std::min(r, n - r);
    if (k == 0) {
        return 1;
    }
    std::vector<long long> dp(static_cast<std::size_t>(k) + 1, 0);
    dp[0] = 1;
    for (long long i = 1; i <= n; ++i) {
        const int upper = static_cast<int>(std::min(i, static_cast<long long>(k)));
        for (int j = upper; j >= 1; --j) {
            dp[j] = (dp[j] + dp[j - 1]) % MOD;
        }
    }
    return dp[k];
}

int main() {
    const std::vector<std::pair<int, int>> samples = {
        {5, 2}, {6, 3}, {0, 0}, {5, 0}, {5, 5}, {3, 4}
    };
    std::cout << "modulus = " << MOD << '\n';
    for (const auto& sample : samples) {
        const int n = sample.first;
        const int r = sample.second;
        std::cout << "C(" << n << ", " << r << ") = "
                  << ncr_mod(n, r) << '\n';
    }
}

import java.math.BigInteger;
import java.util.Arrays;

public class Main {
    private static final BigInteger MOD = BigInteger.valueOf(1_000_000_007L);

    public static BigInteger ncrMod(int n, int r) {
        if (n < 0) {
            throw new IllegalArgumentException("n must be nonnegative");
        }
        if (r < 0 || r > n) {
            return BigInteger.ZERO;
        }
        int k = Math.min(r, n - r);
        if (k == 0) {
            return BigInteger.ONE;
        }
        BigInteger[] dp = new BigInteger[k + 1];
        Arrays.fill(dp, BigInteger.ZERO);
        dp[0] = BigInteger.ONE;
        for (long i = 1; i <= n; ++i) {
            int upper = (int) Math.min(i, (long) k);
            for (int j = upper; j >= 1; --j) {
                dp[j] = dp[j].add(dp[j - 1]).mod(MOD);
            }
        }
        return dp[k];
    }

    public static void main(String[] args) {
        int[][] samples = {
            {5, 2}, {6, 3}, {0, 0}, {5, 0}, {5, 5}, {3, 4}
        };
        System.out.println("modulus = " + MOD);
        for (int[] sample : samples) {
            int n = sample[0];
            int r = sample[1];
            System.out.println("C(" + n + ", " + r + ") = " + ncrMod(n, r));
        }
    }
}

Run the Python tab with python ncr.py. Save the C++ tab as main.cpp, compile with g++ -std=c++14 main.cpp -o ncr, and run ./ncr. Save the Java tab as Main.java, compile with javac Main.java, and run java Main. Each program prints these exact seven lines:

• modulus = 1000000007
• C(5, 2) = 10
• C(6, 3) = 20
• C(0, 0) = 1
• C(5, 0) = 1
• C(5, 5) = 1
• C(3, 4) = 0

To obtain unrestricted full counts, remove the reduction in Python or Java and retain arbitrary-precision integers. C++ then needs an arbitrary-precision library or a proven bound on every intermediate value; simply deleting % MOD can overflow. A useful distinction test is C(40, 20): its full count is 137846528820, while these programs return 846527861.

Complexity, Correctness, and Invariants

Let k = min(r, n − r). For 1 ≤ k ≤ n/2, the number of inner-loop updates is 1 + 2 + … + k + (n − k)k = nk − k(k − 1)/2. The running time is therefore Θ(nk) and auxiliary storage is Θ(k + 1). For fixed n and r, the loop schedule is deterministic: best, average, and worst case coincide. Without an input distribution, there is no separate average-case bound to compute.

Across different r values for a fixed n, the boundary and invalid-selection cases take Θ(1) time and space; valid nonboundary cases range from Θ(n) time when k = 1 to Θ(n²) time when k is near n/2. These are unit-cost arithmetic bounds for the fixed-modulus programs. Unrestricted integer counts require accounting for growing bit lengths: near the middle of row n, values have Θ(n) bits, so additions no longer have constant cost.

For correctness, use induction on the completed row. Initially dp[0] = C(0, 0) = 1 and all higher stored entries are zero. Suppose the stored array represents row i − 1. While processing row i from right to left, an update at j adds the still-old values C(i − 1, j) and C(i − 1, j − 1), giving C(i, j). Entries already processed belong to row i; entries not yet processed belong to row i − 1. The unchanged dp[0] supplies the boundary value one. After the last update, the stored prefix represents row i, completing the induction. Modular reduction preserves this argument as a congruence, and symmetry makes column k answer the original query r.

The multiplicative alternative starts with result = 1 and, for t = 1…k, sets result = result × (n − k + t) / t. Each division is exact over the integers when multiplication is performed first. It often wins for one full-count query; Pascal DP remains valuable when explaining dynamic programming, retaining rows, or working modulo a composite number without division. Fixed-width multiplication can overflow even when a final result fits.

Variants, Pitfalls, and Optimizations

Choose the representation to match the output. To display an entire triangle through row n, generate each row from the previous one and emit it; storing the full output takes Θ(n²) entries. To return one complete row, keep n + 1 entries and update right to left. To answer one coefficient, symmetry and truncation reduce storage to k + 1 entries. Memoized recursion removes repeated subproblems but retains recursion depth and typically stores many more states than the one-row version.

Choose the arithmetic to match the question. Exact counts and modular residues are different outputs. Pascal addition supports composite moduli directly. Factorial/inverse-factorial shortcuts require invertible denominators; for a prime modulus p, the standard table method assumes n < p. For very large n modulo a prime, Lucas's theorem is another approach: write n and r in base p and combine the corresponding small binomial coefficients modulo p. Those small coefficients still need an efficient method; a huge prime does not make preprocessing automatically cheap.

Keep the indexing consistent. The top of Pascal's triangle is row 0, and row n has n + 1 entries. A prompt asking for the “first five rows” usually means rows 0 through 4. Guard invalid r before using symmetry or allocating an array. Keep dp[0] = 1, including when n = 0.

Practice Problems and Real-World Use

Start by tracing a tiny input before optimizing. For each problem, specify whether you need a full count or a remainder, whether items are distinct, and whether order or repetition matters. Those choices determine whether a binomial coefficient is the right model.

For example, a shortest route across an a-by-b grid has a + b moves: choose which a positions contain a right move, giving C(a + b, a). This assumes unrestricted movement using only right and down steps; blocked cells require a grid recurrence instead of this single formula. Similarly, selecting a test cohort is a counting problem, while actually sampling that cohort uniformly requires an additional sampling algorithm.

For independent Bernoulli trials with common success probability p, the probability of exactly r successes is C(n, r) × pʳ × (1 − p)ⁿ⁻ʳ. The coefficient counts which trials succeeded; the remaining factors give the probability of any one such pattern. For numerical probability calculations, use the full coefficient or an appropriate stable probability method, not a modular residue.

Before considering your implementation complete, check C(n, 0) = C(n, n) = 1, symmetry for every valid r on small rows, and Pascal's recurrence for interior entries. When computing modulo M, check the recurrence modulo M as well. Compare small outputs with independently enumerated subsets, then include C(40, 20) to confirm that the modular behavior is intentional.