Skip to content
Tutorials Center
My learning

Topics

Lesson 182 of 225 ยท Math and Bit Manipulation

Combinatorics and Counting

Count without listing: product and sum rules, permutations, combinations, Pascal's triangle, Catalan numbers and inclusion-exclusion, with math.comb and perm.

How many ways can you arrange 8 books on a shelf? How many 5-card hands are there in a deck? How many ways can you place parentheses in an expression? Questions like these ask for a count, and the whole point of combinatorics is that you can usually get the count without writing out every possibility.

That matters in algorithms for two reasons. First, counting tells you how big a search space is, so you know whether brute force and backtracking can work. Second, many problems ask for the count itself, often modulo a large prime. This lesson builds the toolkit: the two basic rules, permutations, combinations, Pascal's triangle, Catalan numbers, and inclusion-exclusion, each checked against actual enumeration.

The two basic rules

Sum rule. If a task can be done in a ways or in b ways (never both), there are a + b ways in total.

Product rule. If a task has two steps, with a choices for the first and b for the second (regardless of the first), there are a * b ways.

TEXT
Outfit: 3 shirts, 2 pairs of trousers, 4 pairs of shoes
product rule: 3 * 2 * 4 = 24 outfits

Pick one drink from 5 teas OR 3 coffees: 5 + 3 = 8 choices
Python Check the product rule by listing

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Factorials and permutations

A permutation is an arrangement where order matters. Arranging n different items in a row: n choices for the first place, n - 1 for the second, and so on:

TEXT
n! = n * (n-1) * ... * 2 * 1       0! = 1
3! = 6:  abc acb bac bca cab cba

Choosing and arranging only k of n items gives the number of k-permutations:

TEXT
P(n, k) = n * (n-1) * ... * (n-k+1) = n! / (n-k)!
P(5, 2) = 5 * 4 = 20

Factorials grow explosively, which is why you rarely enumerate permutations beyond n = 10 or so (10! is 3,628,800).

Python Permutations: formula vs enumeration

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Repeated items

If some items are identical, many arrangements coincide. Divide by the factorial of each repeat count. The word MISSISSIPPI has 11 letters with Mร—1, Iร—4, Sร—4, Pร—2:

TEXT
11! / (1! * 4! * 4! * 2!) = 34650
Python Arrangements of a word with repeated letters

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Combinations

A combination picks k items from n where order does not matter. Start from P(n, k) and divide away the k! orderings of the chosen items:

TEXT
C(n, k) = n! / (k! * (n-k)!)         also written "n choose k"
C(5, 2) = 20 / 2 = 10

Useful facts:

  • C(n, 0) = C(n, n) = 1
  • Symmetry: C(n, k) = C(n, n - k), so choosing who is in equals choosing who is out.
  • Sum of a row: C(n, 0) + ... + C(n, n) = 2**n (every subset has some size).
Python Combinations with math.comb

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Pascal's triangle

Why compute C(n, k) from factorials when it also satisfies a simple addition rule? To choose k from n, consider one special item: either it is chosen (pick k-1 from the other n-1) or it is not (pick k from the other n-1).

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

Written in rows, this is Pascal's triangle: each number is the sum of the two above it.

TEXT
row 0:           1
row 1:          1 1
row 2:         1 2 1
row 3:        1 3 3 1
row 4:       1 4 6 4 1
row 5:      1 5 10 10 5 1

This addition rule is exactly the dynamic programming table for counting paths and subsets, and it uses no division, which matters for modular arithmetic.

Python Build Pascal's triangle

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Combinations modulo a prime

For large n, n! is huge. Under a prime modulus, precompute factorials and inverse factorials once, then every C(n, k) is two multiplications. This uses the modular inverse from the previous lesson.

Python C(n, k) modulo a prime with factorial tables

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Counting grid paths

A robot moves only right or down on a grid with r rows and c columns. Every route has r - 1 downs and c - 1 rights in some order, so the count is C(r + c - 2, r - 1). That equals the grid DP answer with no table.

Python Grid paths: DP vs formula

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Catalan numbers

Some counts show up in many disguises. The Catalan numbers go 1, 1, 2, 5, 14, 42, 132, ... and count:

  • balanced strings of n pairs of parentheses (for n = 3 there are 5: ((())), (()()), (())(), ()(()), ()()()),
  • binary trees with n nodes (see binary trees),
  • ways to triangulate a convex (n+2)-gon,
  • paths on a grid that never cross the diagonal.

The recurrence splits on the first matching pair, with i pairs inside it:

TEXT
C(0) = 1
C(n) = sum over i = 0..n-1 of C(i) * C(n-1-i)
closed form: C(n) = comb(2n, n) / (n + 1)
Python Catalan numbers three ways

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Inclusion-exclusion

How many integers from 1 to 100 are divisible by 2 or 3? Adding the counts for 2 and 3 counts numbers divisible by both (multiples of 6) twice. Fix it by subtracting the overlap:

TEXT
|A or B| = |A| + |B| - |A and B|
|A or B or C| = |A|+|B|+|C| - |A&B| - |A&C| - |B&C| + |A&B&C|

The signs alternate: add singles, subtract pairs, add triples, and so on.

TEXT
multiples of 2 or 3 up to 100:
50 + 33 - 16 = 67
Python Inclusion-exclusion over a set of divisors

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last example is a classic: derangements count permutations with no fixed point (every guest gets someone else's hat), using inclusion-exclusion over "guest k gets their own hat".

Common mistakes

  • Mixing up order. If order matters use permutations; if not, use combinations. Ask: "is ab different from ba here?"
  • Forgetting repeated items and overcounting arrangements.
  • Computing math.factorial(n) // ... for huge n when you only need C(n, k) modulo a prime; use factorial tables.
  • Float division. Use // after multiplying out, or math.comb, to keep exact integers.
  • Double counting in the sum rule. Add only when the cases cannot overlap; otherwise use inclusion-exclusion.
  • Enumerating when counting is enough. Listing n! objects for n = 15 is infeasible; the formula answers instantly.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. How many ways can 4 different books be arranged in a row?

    4 choices for the first place, 3 for the second, 2 for the third and 1 for the last: 4! = 24.
  2. 2. What is C(6, 2)?

    6! / (2! * 4!) = (6 * 5) / 2 = 15. P(6, 2) = 30 counts ordered pairs, and each unordered pair appears twice.
  3. 3. Which rule is the foundation of Pascal's triangle?

    Either a chosen special item is in the group (pick k-1 from the rest) or it is not (pick k from the rest).
  4. 4. How many balanced strings of 4 pairs of parentheses exist?

    The Catalan numbers run 1, 1, 2, 5, 14, so n = 4 gives 14.
  5. 5. How many integers in 1..100 are divisible by 2 or 3?

    50 multiples of 2 plus 33 multiples of 3 count the 16 multiples of 6 twice, so subtract 16: 67.

Summary

  • Sum rule adds disjoint cases; product rule multiplies independent steps.
  • Permutations count ordered arrangements: n!, and P(n, k) = n! / (n-k)!. Divide by repeat factorials for identical items.
  • Combinations count unordered choices: C(n, k) = n! / (k! (n-k)!), symmetric, and a row of Pascal's triangle sums to 2**n.
  • C(n, k) = C(n-1, k-1) + C(n-1, k) builds Pascal's triangle with additions only; under a prime modulus use factorial and inverse-factorial tables.
  • Catalan numbers (1, 1, 2, 5, 14, 42, ...) count balanced parentheses, binary trees and triangulations.
  • Inclusion-exclusion fixes overlaps by alternating add and subtract.
  • Use math.factorial, math.perm and math.comb, and count instead of listing whenever you can.

Next: Randomized Algorithms