Permutations vs Combinations: nPr, nCr and Pascal's Triangle

Counting questions come in two flavours that look almost identical. "How many ways can three of five runners stand on a podium?" and "how many ways can you pick three of five runners for a relay team?" differ by one word, and their answers differ by a factor of six. The whole topic is one question asked before any formula: does order matter? Everything else, including Pascal's triangle and the modular versions that coding problems ask for, follows from it.

The problem it solves

Interview problems rarely say "compute C(n, k)". They say:

• How many paths from the top-left to the bottom-right of a grid, moving only right or down?
• How many distinct strings can be made by rearranging these letters?
• How many handshakes, pairs, teams or subsets of a given size?
• Answer modulo 10^9 + 7, because the true count has hundreds of digits.

Each is a permutation or a combination in disguise. Recognising which one, and whether repeats or identical items are involved, is the actual skill. A wrong choice is not slightly off; it is off by k!.

The intuition

Permutations: order matters. Fill the positions one at a time. Gold has n candidates, silver n - 1, and so on for k positions: n × (n - 1) × … × (n - k + 1), which is n! / (n - k)!. The (n - k)! is the tail of the factorial you never reached.

Combinations: only membership matters. Count the ordered line-ups, then notice that each group of k people appears once per ordering of those people, k! times. Divide it away: C(n, k) = n! / (k! (n - k)!).

Two facts make combinations easy to reason about:

• Symmetry. C(n, k) = C(n, n - k): choosing who is in fixes who is out.
• Pascal's rule. C(n, k) = C(n - 1, k - 1) + C(n - 1, k): the newest person is either in the group, and you pick the other k - 1 from the rest, or out, and you pick all k from the rest. Written row by row, that rule is Pascal's triangle, and it is the dynamic programming version of the count.

Repeats need one more idea. Rearranging BANANA counts 6! orderings, but swapping the three As among themselves changes nothing, nor does swapping the two Ns: divide by 3! and 2! to get 60. Choosing with repetition allowed, like four scoops from three flavours, is "stars and bars": C(n + k - 1, k), here 15.

Watch it run

The animation starts with five runners and three podium places: gold has five candidates, silver four, bronze three. Multiply them and 5 × 4 × 3 = 60 ordered podiums, which is 5! with the 2! tail cancelled away. But the same three people can stand in 3! = 6 orders, and each of those orders is one of the 60. Divide the repeats out: 60 / 6 = 10 distinct trios, which is C(5, 3). Those counts are already written down: Pascal's row 5 reads 1 5 10 10 5 1, one entry per k. Every entry is the two above it added, 4 + 6 = 10, because the fifth runner is either in the trio or not. The closing rule: if order matters, count permutations; if only membership matters, divide by k!, and the result is never the larger number.

The code

The lesson's numbers, Pascal's rule, and a way to compute C(n, k) without huge intermediate factorials. The multiplicative loop is exact at every step, because after step i the running value is C(n, i + 1), a whole number:

from math import comb, factorial, perm

print(perm(5, 3), factorial(5) // factorial(5 - 3))     # 60 60  -> ordered podiums
print(comb(5, 3), perm(5, 3) // factorial(3))           # 10 10  -> order divided away
print(comb(5, 3) == comb(5, 2))                         # True   -> choose who is left out

def pascal(n):
    """Row n of Pascal's triangle: each entry is the two above it added."""
    row = [1]
    for _ in range(n):
        row = [1] + [a + b for a, b in zip(row, row[1:])] + [1]
    return row

print(pascal(5), pascal(4)[2] + pascal(4)[3])           # [1, 5, 10, 10, 5, 1] 10

def n_choose_k(n, k):
    """Multiplicative form: after step i, c is C(n, i + 1), so every division is exact."""
    k = min(k, n - k)
    c = 1
    for i in range(k):
        c = c * (n - i) // (i + 1)
    return c

print(n_choose_k(52, 5), n_choose_k(60, 30))            # 2598960 118264581564861424

Repeated items and repetition allowed:

from collections import Counter

def arrangements(word):
    """Distinct orderings of a multiset: n! divided by each repeat count's factorial."""
    total = factorial(len(word))
    for count in Counter(word).values():
        total //= factorial(count)
    return total

print(arrangements("BANANA"), comb(3 + 4 - 1, 4))       # 60 15  -> anagrams; 4 scoops of 3 flavours

When a problem asks for the count modulo the prime 10^9 + 7, division is not allowed directly. Precompute factorials, and multiply by the modular inverse of k! and (n - k)! instead, found with Fermat's little theorem and fast exponentiation:

MOD = 10**9 + 7
N = 1000
fact = [1] * (N + 1)
for i in range(1, N + 1):
    fact[i] = fact[i - 1] * i % MOD
inv_fact = [1] * (N + 1)
inv_fact[N] = pow(fact[N], MOD - 2, MOD)                 # Fermat: MOD is prime
for i in range(N, 0, -1):
    inv_fact[i - 1] = inv_fact[i] * i % MOD

def comb_mod(n, k):
    if not 0 <= k <= n:
        return 0
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD

print(comb_mod(1000, 500), comb(1000, 500) % MOD)       # 159835829 159835829

Checked on 500 seeded random cases against brute force: itertools generates every permutation, combination, multiset arrangement and multiset choice, and the counts must match every formula above, including the modular one against Python's exact big integers:

import random
from itertools import combinations, combinations_with_replacement, permutations

random.seed(29)
ok = True
for _ in range(500):
    n = random.randint(0, 8)
    k = random.randint(0, n)
    items = range(n)
    ok &= len(list(permutations(items, k))) == perm(n, k)
    ok &= len(list(combinations(items, k))) == comb(n, k) == n_choose_k(n, k) == pascal(n)[k]
    ok &= len({frozenset(p) for p in permutations(items, k)}) == perm(n, k) // factorial(k)
    if n:                                               # stars and bars needs n >= 1
        ok &= len(list(combinations_with_replacement(items, k))) == comb(n + k - 1, k)
    word = "".join(random.choice("ABC") for _ in range(random.randint(1, 7)))
    ok &= len(set(permutations(word))) == arrangements(word)
    big_n = random.randint(0, N)
    big_k = random.randint(-2, big_n + 2)
    ok &= comb_mod(big_n, big_k) == (comb(big_n, big_k) % MOD if 0 <= big_k <= big_n else 0)
print(ok)                                               # True

The complexity

• One exact count: O(k) multiplications with the multiplicative form, on numbers that grow to C(n, k) itself.
• Many counts modulo a prime: O(N) to build the factorial tables once, then O(1) per query.
• Pascal's triangle: O(n²) time for all rows up to n, useful when the modulus is not prime and inverses may not exist.
• Generating instead of counting: listing all permutations is O(n!) and all subsets O(2^n). Counting never needs that; backtracking does, when the problem wants the items themselves.

Where it goes wrong

• Asking the wrong question first. Seats, rankings and passwords are ordered; committees, hands of cards and subsets are not.
• Overflow in fixed-width integers. 21! already exceeds a signed 64-bit integer. Use the multiplicative form, or modular arithmetic.
• Dividing under a modulus. (a / b) mod p is not (a mod p) / (b mod p); multiply by the inverse, and remember why the modulus is prime.
• Forgetting identical items. Arrangements of a word with repeated letters are fewer than n!.

When it shows up in interviews

Directly as "how many paths through an m × n grid", which is C(m + n - 2, m - 1), the closed form behind unique paths; as the size check for a backtracking answer ("there are C(9, 3) ways, so brute force is fine"); and in probability questions about cards, dice and collisions. The patterns cheat sheet lists the subset and permutation templates these counts bound.

How to say it in an interview

"First I decide whether order matters. If it does, it's a permutation: n choices, then n - 1, for k places, so n! / (n - k)!. If only membership matters, each group was counted k! times, so I divide: n choose k. I compute it multiplicatively so every step stays an integer, or with factorial tables and modular inverses when the answer is taken mod a prime. Repeated items divide by each repeat's factorial, and Pascal's rule, in or out, gives the DP version."