Counting Problems and Combinatorics in DSA

Counting problems appear throughout DSA interviews and competitive programming. “How many ways…?”, “Count all valid…?”, and “What is the total number of…?” are all combinatorics questions in disguise. This guide covers the essential counting techniques you need.

Permutations (nPr)

A permutation is an arrangement where order matters. The number of ways to arrange r items from a set of n items:

nPr = n! / (n - r)!

from math import factorial

def nPr(n, r):
    """
    Number of permutations: arrange r items from n.
    Order matters.
    """
    if r > n:
        return 0
    return factorial(n) // factorial(n - r)


# Arrange 3 items from 5
print(f"5P3 = {nPr(5, 3)}")  # 60

# All arrangements of 4 items
print(f"4P4 = {nPr(4, 4)}")  # 24 = 4!

Permutations with repetition

When elements can repeat, each position has n choices:

def permutations_with_repetition(n, r):
    """
    n choices for each of r positions.
    Like a combination lock.
    """
    return n ** r

# 4-digit PIN with digits 0-9
print(f"PINs: {permutations_with_repetition(10, 4)}")  # 10000

Permutations of multiset

When some elements are identical:

def multiset_permutations(word):
    """
    Permutations of a word with repeated letters.
    Formula: n! / (k1! * k2! * ... * km!)
    """
    from collections import Counter

    n = len(word)
    freq = Counter(word)
    result = factorial(n)
    for count in freq.values():
        result //= factorial(count)
    return result


print(f"MISSISSIPPI: {multiset_permutations('MISSISSIPPI')}")
# 11! / (4! * 4! * 2! * 1!) = 34650
print(f"AABB: {multiset_permutations('AABB')}")
# 4! / (2! * 2!) = 6

Combinations (nCr)

A combination is a selection where order does not matter:

nCr = n! / (r! * (n - r)!)

def nCr(n, r):
    """
    Number of combinations: choose r items from n.
    Order does NOT matter.
    """
    if r > n or r < 0:
        return 0
    return factorial(n) // (factorial(r) * factorial(n - r))


print(f"5C3 = {nCr(5, 3)}")  # 10
print(f"5C2 = {nCr(5, 2)}")  # 10 (same! nCr = nC(n-r))
print(f"10C0 = {nCr(10, 0)}")  # 1 (empty set)

Efficient computation (avoid overflow)

Computing factorials directly can overflow. Compute nCr incrementally:

def nCr_safe(n, r):
    """
    Compute nCr without computing full factorials.
    Uses the identity: C(n,r) = C(n,r-1) * (n-r+1) / r
    """
    if r > n - r:
        r = n - r  # C(n,r) = C(n, n-r)

    result = 1
    for i in range(r):
        result = result * (n - i) // (i + 1)

    return result


print(f"C(100, 50) = {nCr_safe(100, 50)}")
# Very large number, but computed without overflow

Pascal’s triangle

Pascal’s triangle gives a visual and computational way to find combinations. Each entry is the sum of the two entries above it:

C(n, r) = C(n-1, r-1) + C(n-1, r)

def build_pascals_triangle(n):
    """
    Build Pascal's triangle up to row n.
    triangle[n][r] = C(n, r)
    Time: O(n^2), Space: O(n^2)
    """
    triangle = [[1]]

    for i in range(1, n + 1):
        row = [1]
        for j in range(1, i):
            row.append(triangle[i - 1][j - 1] + triangle[i - 1][j])
        row.append(1)
        triangle.append(row)

    return triangle


# Print first 8 rows
triangle = build_pascals_triangle(7)
for i, row in enumerate(triangle):
    padding = " " * (7 - i) * 2
    values = "  ".join(f"{v:3d}" for v in row)
    print(f"{padding}{values}")


def nCr_pascal(n, r, triangle=None):
    """Look up C(n,r) from precomputed Pascal's triangle."""
    if triangle is None:
        triangle = build_pascals_triangle(n)
    return triangle[n][r]

Pascal’s triangle properties

def demonstrate_pascal_properties():
    """Show key properties of Pascal's triangle."""
    t = build_pascals_triangle(10)

    # Property 1: Row sums are powers of 2
    for n in range(6):
        print(f"  Row {n} sum: {sum(t[n])} = 2^{n} = {2**n}")

    print()

    # Property 2: Symmetry
    for n in range(5):
        for r in range(n + 1):
            assert t[n][r] == t[n][n - r], "Symmetry violated!"
    print("  Symmetry verified: C(n,r) = C(n, n-r)")

    # Property 3: Hockey stick identity
    # Sum of C(r,r) + C(r+1,r) + ... + C(n,r) = C(n+1, r+1)
    r = 2
    for n in range(r, 8):
        diagonal_sum = sum(t[i][r] for i in range(r, n + 1))
        print(f"  Sum C({r},{r})..C({n},{r}) = {diagonal_sum} = C({n+1},{r+1}) = {t[n+1][r+1]}")


demonstrate_pascal_properties()

Catalan numbers

Catalan numbers are one of the most important sequences in combinatorics. The nth Catalan number is:

Cn = C(2n, n) / (n + 1) = (2n)! / ((n+1)! * n!)

The first few: 1, 1, 2, 5, 14, 42, 132, 429, 1430, …

def catalan(n):
    """
    Compute nth Catalan number.
    """
    return nCr_safe(2 * n, n) // (n + 1)


def catalan_dp(n):
    """
    Compute Catalan numbers using DP.
    C(0) = 1
    C(n) = sum of C(i) * C(n-1-i) for i from 0 to n-1
    Time: O(n^2)
    """
    dp = [0] * (n + 1)
    dp[0] = 1

    for i in range(1, n + 1):
        for j in range(i):
            dp[i] += dp[j] * dp[i - 1 - j]

    return dp[n]


for i in range(10):
    print(f"  C({i}) = {catalan(i)}")

Application 1: valid parentheses count

The number of valid arrangements of n pairs of parentheses is the nth Catalan number.

def count_valid_parentheses(n):
    """
    Count valid parenthesizations with n pairs.
    This is exactly the nth Catalan number.
    """
    return catalan(n)


# Verify by generating all valid parentheses
def generate_parentheses(n):
    result = []

    def backtrack(s, open_count, close_count):
        if len(s) == 2 * n:
            result.append(s)
            return
        if open_count < n:
            backtrack(s + "(", open_count + 1, close_count)
        if close_count < open_count:
            backtrack(s + ")", open_count, close_count + 1)

    backtrack("", 0, 0)
    return result


for n in range(1, 6):
    generated = generate_parentheses(n)
    formula = count_valid_parentheses(n)
    print(f"  n={n}: generated={len(generated)}, formula={formula}")

Application 2: number of BSTs

The number of structurally unique BSTs with n nodes is the nth Catalan number.

def num_trees(n):
    """
    LeetCode 96: Count unique BSTs with nodes 1..n.
    For each root i, left subtree has i-1 nodes, right has n-i.
    numTrees(n) = sum of numTrees(i-1) * numTrees(n-i) for i=1..n
    This is exactly the Catalan recurrence!
    """
    dp = [0] * (n + 1)
    dp[0] = 1  # Empty tree

    for nodes in range(1, n + 1):
        for root in range(1, nodes + 1):
            left_count = root - 1
            right_count = nodes - root
            dp[nodes] += dp[left_count] * dp[right_count]

    return dp[n]


for n in range(1, 8):
    print(f"  BSTs with {n} nodes: {num_trees(n)}")

Application 3: grid paths (Catalan constraint)

Count paths from (0,0) to (n,n) using only right and up moves, never going above the diagonal. This equals C(n).

def catalan_paths(n):
    """
    Paths from (0,0) to (n,n) that stay on or below the diagonal.
    At every point, the number of right steps >= number of up steps.
    """
    return catalan(n)


# Verify with DP
def count_paths_dp(n):
    """
    dp[i][j] = number of paths to (i, j) staying below diagonal.
    Constraint: j <= i at all times (more right steps than up steps).
    """
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 1

    for i in range(n + 1):  # right steps
        for j in range(i + 1):  # up steps (j <= i)
            if i > 0:
                dp[i][j] += dp[i - 1][j]  # from left
            if j > 0:
                dp[i][j] += dp[i][j - 1]  # from below

    return dp[n][n]


for n in range(1, 8):
    print(f"  n={n}: formula={catalan_paths(n)}, DP={count_paths_dp(n)}")

More Catalan applications

Count	Formula
Valid parentheses with n pairs	C(n)
Distinct BSTs with n nodes	C(n)
Paths in grid below diagonal	C(n)
Triangulations of convex (n+2)-gon	C(n)
Full binary trees with n+1 leaves	C(n)
Non-crossing partitions of n elements	C(n)
Mountain ranges with n up-strokes	C(n)

Inclusion-exclusion principle

When counting elements in a union of sets, subtract overcounting:

|A union B| = |A| + |B| - |A intersect B|

For three sets:

|A union B union C| = |A| + |B| + |C|
                    - |A intersect B| - |A intersect C| - |B intersect C|
                    + |A intersect B intersect C|

def count_divisible(n, divisors):
    """
    Count numbers from 1 to n divisible by at least one of the divisors.
    Uses inclusion-exclusion.
    """
    from itertools import combinations
    from math import gcd

    def lcm(a, b):
        return a * b // gcd(a, b)

    total = 0
    for size in range(1, len(divisors) + 1):
        for combo in combinations(divisors, size):
            # LCM of the combination
            current_lcm = combo[0]
            for d in combo[1:]:
                current_lcm = lcm(current_lcm, d)

            count = n // current_lcm

            # Add for odd-size subsets, subtract for even-size
            if size % 2 == 1:
                total += count
            else:
                total -= count

    return total


# Numbers from 1 to 100 divisible by 2, 3, or 5
print(count_divisible(100, [2, 3, 5]))  # 74


def derangements(n):
    """
    Count permutations where no element is in its original position.
    Uses inclusion-exclusion on "element i is fixed."
    D(n) = n! * sum_{k=0}^{n} (-1)^k / k!
    """
    result = 0
    for k in range(n + 1):
        if k % 2 == 0:
            result += factorial(n) // factorial(k)
        else:
            result -= factorial(n) // factorial(k)
    return result


for n in range(1, 8):
    print(f"  D({n}) = {derangements(n)}")
# D(1)=0, D(2)=1, D(3)=2, D(4)=9, D(5)=44, D(6)=265, D(7)=1854

Surjective functions (onto mappings)

def surjections(n, m):
    """
    Count surjective functions from n-element set to m-element set.
    Every element in the codomain must be mapped to.
    Uses inclusion-exclusion.
    """
    if n < m:
        return 0

    total = 0
    for k in range(m + 1):
        sign = (-1) ** k
        total += sign * nCr_safe(m, k) * (m - k) ** n

    return total


print(f"Surjections from 4 to 3: {surjections(4, 3)}")  # 36
print(f"Surjections from 5 to 3: {surjections(5, 3)}")  # 150

Pigeonhole principle

If n+1 items are put into n containers, at least one container has at least 2 items. Simple but powerful for proving existence.

def find_duplicate(nums):
    """
    Given n+1 numbers in range [1, n], find a duplicate.
    Pigeonhole: n+1 items in n slots => duplicate exists.
    Floyd's cycle detection finds it in O(n) time, O(1) space.
    """
    # Phase 1: find meeting point
    slow = fast = nums[0]
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break

    # Phase 2: find cycle start
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]

    return slow


print(find_duplicate([1, 3, 4, 2, 2]))  # 2
print(find_duplicate([3, 1, 3, 4, 2]))  # 3


def pigeonhole_substring(s, k):
    """
    In any string of length > 26*k, some character appears more than k times.
    More useful: find the most common substring of length L.
    """
    from collections import Counter
    if len(s) < k:
        return None

    freq = Counter()
    for i in range(len(s) - k + 1):
        freq[s[i:i+k]] += 1

    return freq.most_common(1)[0]

Stars and bars

Distribute n identical items into k distinct bins. The number of ways:

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

def stars_and_bars(n, k):
    """
    Number of ways to distribute n identical items into k distinct bins.
    Each bin can have 0 or more items.
    """
    return nCr_safe(n + k - 1, k - 1)


def stars_and_bars_positive(n, k):
    """
    Each bin must have at least 1 item.
    Equivalent to distributing n-k items into k bins (each gets 1 first).
    """
    if n < k:
        return 0
    return nCr_safe(n - 1, k - 1)


# Distribute 10 cookies among 3 children
print(f"10 cookies, 3 children (0+ each): {stars_and_bars(10, 3)}")  # 66
print(f"10 cookies, 3 children (1+ each): {stars_and_bars_positive(10, 3)}")  # 36

# How many solutions to x1 + x2 + x3 = 10, xi >= 0?
print(f"Solutions to x1+x2+x3=10: {stars_and_bars(10, 3)}")  # 66

Application: count paths in a grid

def grid_paths(m, n):
    """
    Count paths from top-left to bottom-right in an m x n grid.
    Can only move right or down.

    Need (m-1) down moves and (n-1) right moves.
    Total moves = (m-1) + (n-1) = m+n-2
    Choose which (m-1) moves are down: C(m+n-2, m-1)
    """
    return nCr_safe(m + n - 2, m - 1)


print(f"3x3 grid paths: {grid_paths(3, 3)}")    # 6
print(f"3x7 grid paths: {grid_paths(3, 7)}")    # 28
print(f"10x10 grid paths: {grid_paths(10, 10)}")  # 48620

Modular arithmetic for large numbers

Combinatorial values can be astronomically large. In competitive programming, answers are typically required modulo 10^9 + 7.

MOD = 10**9 + 7

def mod_pow(base, exp, mod):
    """
    Fast modular exponentiation.
    Time: O(log exp)
    """
    result = 1
    base %= mod
    while exp > 0:
        if exp % 2 == 1:
            result = (result * base) % mod
        exp //= 2
        base = (base * base) % mod
    return result


def mod_inverse(a, mod):
    """
    Modular inverse using Fermat's little theorem.
    a^(-1) mod p = a^(p-2) mod p (when p is prime)
    """
    return mod_pow(a, mod - 2, mod)


def nCr_mod(n, r, mod=MOD):
    """
    Compute C(n, r) mod p using Fermat's little theorem.
    Requires p to be prime.
    Time: O(r + log p)
    """
    if r > n or r < 0:
        return 0

    numerator = 1
    denominator = 1

    for i in range(r):
        numerator = (numerator * ((n - i) % mod)) % mod
        denominator = (denominator * ((i + 1) % mod)) % mod

    return (numerator * mod_inverse(denominator, mod)) % mod


# Precompute factorials for multiple queries
def precompute_factorials(max_n, mod=MOD):
    """
    Precompute factorials and inverse factorials for O(1) nCr queries.
    Time: O(max_n) precomputation, O(1) per query
    """
    fact = [1] * (max_n + 1)
    for i in range(1, max_n + 1):
        fact[i] = fact[i - 1] * i % mod

    inv_fact = [1] * (max_n + 1)
    inv_fact[max_n] = mod_inverse(fact[max_n], mod)
    for i in range(max_n - 1, -1, -1):
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % mod

    return fact, inv_fact


def nCr_fast(n, r, fact, inv_fact, mod=MOD):
    """O(1) combination query after precomputation."""
    if r > n or r < 0:
        return 0
    return fact[n] * inv_fact[r] % mod * inv_fact[n - r] % mod


# Example: precompute and query
fact, inv_fact = precompute_factorials(200000)
print(f"C(100000, 50000) mod 10^9+7 = {nCr_fast(100000, 50000, fact, inv_fact)}")

Lucas’ theorem (for small primes)

def nCr_lucas(n, r, p):
    """
    Lucas' theorem for C(n, r) mod p where p is a small prime.
    C(n,r) mod p = product of C(ni, ri) mod p
    where ni and ri are digits of n and r in base p.
    """
    if r == 0:
        return 1
    return (nCr_safe(n % p, r % p) * nCr_lucas(n // p, r // p, p)) % p


print(f"C(100, 40) mod 13 = {nCr_lucas(100, 40, 13)}")

Interview problems

Count of binary strings without consecutive 1s

def count_binary_strings(n):
    """
    Count binary strings of length n with no two consecutive 1s.
    This is Fibonacci-like!
    a = strings ending in 0, b = strings ending in 1
    """
    if n <= 0:
        return 0

    # Ending in 0: previous can end in 0 or 1
    # Ending in 1: previous must end in 0
    a, b = 1, 1  # length 1: "0" and "1"

    for _ in range(2, n + 1):
        a, b = a + b, a

    return a + b


for n in range(1, 8):
    print(f"  n={n}: {count_binary_strings(n)}")
# 2, 3, 5, 8, 13, 21, 34 - Fibonacci!

Count of subsets with given sum

def count_subsets_with_sum(arr, target):
    """
    Count subsets that sum to target.
    Time: O(n * target), Space: O(target)
    """
    dp = [0] * (target + 1)
    dp[0] = 1  # Empty subset sums to 0

    for num in arr:
        for s in range(target, num - 1, -1):
            dp[s] += dp[s - num]

    return dp[target]


print(count_subsets_with_sum([1, 2, 3, 4, 5], 5))  # 3: {5}, {2,3}, {1,4}

Unique paths with obstacles

def unique_paths_with_obstacles(grid):
    """
    Count paths from top-left to bottom-right with obstacles.
    """
    m, n = len(grid), len(grid[0])
    if grid[0][0] == 1 or grid[m-1][n-1] == 1:
        return 0

    dp = [0] * n
    dp[0] = 1

    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                dp[j] = 0
            elif j > 0:
                dp[j] += dp[j - 1]

    return dp[n - 1]


grid = [
    [0, 0, 0],
    [0, 1, 0],
    [0, 0, 0]
]
print(f"Paths with obstacles: {unique_paths_with_obstacles(grid)}")  # 2

Complexity summary

Technique	Time	Space	Use Case
nPr/nCr direct	O(r)	O(1)	Single query
Pascal’s triangle	O(n^2)	O(n^2)	Many C(n,r) queries
Precomputed factorials	O(n) precomp, O(1) query	O(n)	Competitive programming
Catalan (formula)	O(n)	O(1)	Single Catalan number
Catalan (DP)	O(n^2)	O(n)	All Catalan numbers up to n
Inclusion-exclusion	O(2^k) for k sets	O(k)	Union/intersection counting
Stars and bars	O(k)	O(1)	Distribution problems

Practice problems

Problem	Technique	Difficulty
Unique Paths (LC 62)	Combinations	Medium
Unique Paths II (LC 63)	DP with obstacles	Medium
Unique BSTs (LC 96)	Catalan numbers	Medium
Generate Parentheses (LC 22)	Catalan + backtracking	Medium
Pascal’s Triangle (LC 118)	Build triangle	Easy
Pascal’s Triangle II (LC 119)	Single row	Easy
Find Duplicate (LC 287)	Pigeonhole	Medium
Count Binary Strings	Fibonacci variant	Easy
Derangements	Inclusion-exclusion	Medium
nCr mod p	Modular arithmetic	Medium
Count Subsets with Sum	DP counting	Medium
Grid Paths below Diagonal	Catalan	Hard

Key takeaways

1. Permutations (order matters): nPr = n! / (n-r)!. Combinations (order doesn’t matter): nCr = n! / (r!(n-r)!).
2. Pascal’s triangle provides an O(n^2) way to precompute all combinations and reveals powerful identities.
3. Catalan numbers appear in balanced parentheses, BST counting, grid paths below diagonal, and many other problems. Recognize the pattern: splitting into left/right subproblems.
4. Inclusion-exclusion handles overcounting in union problems. Derangements are a classic application.
5. Modular arithmetic with Fermat’s little theorem enables computing huge combinatorial values modulo a prime. Precomputing factorials gives O(1) per query.
6. The pigeonhole principle proves existence of duplicates and is exploited by Floyd’s cycle detection.