Combinatorics Basics: nCk, Stars and Bars, Pigeonhole

Combinatorics counts arrangements without listing them. For interviews you need a small toolkit: the sum and product rules, permutations and combinations, computing C(n, k) exactly or modulo a prime, stars and bars for distributing identical items, and the pigeonhole principle for "there must exist" arguments.

Intuition

• Sum rule: if the cases are disjoint, add their counts.
• Product rule: if a choice is made in independent stages, multiply the number of options per stage.
• Permutations: ordered selections of k items out of n: P(n, k) = n! / (n - k)!.
• Combinations: unordered selections: C(n, k) = n! / (k! (n - k)!). Every unordered choice corresponds to k! ordered ones.
• Pascal's rule: C(n, k) = C(n-1, k-1) + C(n-1, k): either item n is chosen or it is not. This builds the whole triangle with additions only.
• Multisets: arranging letters where some repeat: n! / (c1! c2! ...), dividing out the orders of identical letters. Arranging n people around a round table: (n - 1)!, because rotations are the same.

Stars and bars. Distributing n identical items into k labeled boxes (boxes may stay empty) is the same as arranging n stars and k - 1 bars in a row: C(n + k - 1, k - 1). If every box needs at least one item, hand one to each box first: C(n - 1, k - 1). Lower bounds in general are handled the same way, by pre-distributing them.

Pigeonhole principle. Putting n + 1 items into n boxes forces some box to hold at least two; more generally some box holds at least ceil(n / k) of n items in k boxes. It proves existence, and the proof is often an algorithm: find the collision.

When to use it in interviews / OAs

• A counting question whose answer has a closed form: grid paths, distributions, arrangements of letters.
• "Return the count modulo 10^9 + 7" with binomials inside: precompute factorials.
• A DP whose recurrence is Pascal's rule in disguise.
• "Prove that a duplicate / a divisible subarray / a gap must exist", or to bound an answer before searching.

Template: binomial coefficients

def comb_exact(n: int, k: int) -> int:
    if k < 0 or k > n:
        return 0
    k = min(k, n - k)  # C(n, k) = C(n, n - k): fewer steps
    result = 1
    for i in range(k):
        result = result * (n - i) // (i + 1)  # always exact: it equals C(n, i + 1)
    return result


def pascal_table(n: int, mod: int) -> list[list[int]]:
    # C[i][j] for 0 <= j <= i <= n; additions only, so any modulus works
    C = [[1] * (i + 1) for i in range(n + 1)]
    for i in range(2, n + 1):
        for j in range(1, i):
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod
    return C


def make_ncr(n_max: int, p: int = 10**9 + 7):
    # O(n_max) precomputation, then O(1) per query; p must be prime and > n_max
    fact = [1] * (n_max + 1)
    for i in range(1, n_max + 1):
        fact[i] = fact[i - 1] * i % p
    inv_fact = [1] * (n_max + 1)
    inv_fact[n_max] = pow(fact[n_max], p - 2, p)
    for i in range(n_max, 0, -1):
        inv_fact[i - 1] = inv_fact[i] * i % p

    def ncr(n: int, k: int) -> int:
        if k < 0 or k > n:
            return 0
        return fact[n] * inv_fact[k] % p * inv_fact[n - k] % p

    return ncr

Choose by constraints: one exact value (math.comb in Python, or the multiplicative loop) for small inputs; Pascal's table when n is at most a few thousand or the modulus is not prime; factorial tables when there are many queries modulo a prime.

Template: distributions and arrangements

from collections import Counter
from math import factorial


def stars_and_bars(total: int, parts: int, positive: bool = False) -> int:
    # ordered ways to write total as a sum of `parts` integers, each >= 0 (or each >= 1)
    if positive:
        total -= parts  # give every part 1 up front, then distribute the rest freely
        if total < 0:
            return 0
    return comb_exact(total + parts - 1, parts - 1)


def arrangements(word: str) -> int:
    # distinct orderings of a multiset: n! / (c1! * c2! * ...)
    result = factorial(len(word))
    for c in Counter(word).values():
        result //= factorial(c)
    return result


def grid_paths(m: int, n: int) -> int:
    # right/down paths in an m x n grid: choose which of the m + n - 2 moves go down
    return comb_exact(m + n - 2, m - 1)

Template: pigeonhole as an algorithm

Among any n integers there is a non-empty contiguous block whose sum is divisible by n. The n + 1 prefix sums (including the empty prefix) fall into only n remainder classes, so two share a remainder, and the block between them works:

def divisible_subarray(nums: list[int]) -> tuple[int, int]:
    # returns (i, j) such that sum(nums[i:j]) is divisible by len(nums)
    n = len(nums)
    seen = {0: 0}  # prefix remainder -> prefix length
    prefix = 0
    for j, x in enumerate(nums, 1):
        prefix = (prefix + x) % n
        if prefix in seen:
            return seen[prefix], j
        seen[prefix] = j
    raise AssertionError("unreachable by the pigeonhole principle")

Other classic uses: an array of n + 1 values from 1..n must contain a duplicate (the basis of the cycle-detection solution for finding it); the smallest missing positive of n numbers is at most n + 1; with n numbers spread over [lo, hi], some adjacent sorted gap is at least (hi - lo) / (n - 1), which is why bucketing finds the maximum gap in linear time.

Complexity

Method	Precompute	Per query
Multiplicative loop	—	O(min(k, n - k)) big-integer steps
Pascal's triangle	O(n^2) time and memory	O(1)
Factorials mod prime	O(n)	O(1)

Common pitfalls

• Out-of-range k: define C(n, k) = 0 for k < 0 or k > n; many formulas rely on it.
• Overflow: 20! fits in 64 bits, 21! does not. In C++/Java either reduce modulo a prime, use Pascal's rule, or divide early with the multiplicative loop.
• Division under a composite modulus: factorial tables need a prime modulus larger than n. Otherwise use Pascal's triangle.
• Empty vs non-empty boxes: stars and bars changes from C(n + k - 1, k - 1) to C(n - 1, k - 1).
• Identical vs distinct: decide whether the items and the boxes are distinguishable before choosing a formula; mixing them up is the most common counting error.
• "At least one": count the complement ("none") and subtract, instead of adding overlapping cases.

Interview variations

• Unique paths in a grid: C(m + n - 2, m - 1).
• Pascal's triangle and its k-th row: Pascal's rule, or row[i+1] = row[i] * (k - i) / (i + 1).
• Count sorted vowel strings of length n: stars and bars, C(n + 4, 4).
• Ways to reach a point exactly k steps away on a line: choose the number of right steps, C(k, (k + d) / 2).
• Count arrays with a given product: per prime, distribute its exponent among the positions with stars and bars, then multiply.
• Count anagrams of a sentence: multiply the multiset permutation counts of the words.
• Find the duplicate number, first missing positive, maximum gap: pigeonhole arguments.