Appendix H: Combinatorics Formula Sheet

A dense, exam-ready reference for the counting techniques of Part III (Chapters 15–19). Counting is the arithmetic of possibility: how many passwords, how many hash collisions, how many distinct orderings, how many subsets. Almost every "how big is the search space?" question in CS reduces to one of the formulas below. Keep this page open while you size a keyspace, bound a brute-force loop, or count the inputs a function must handle.

The whole subject rests on two rules — the product rule and the sum rule — plus the discipline to ask three questions about any selection: Does order matter? Is repetition allowed? Are we counting arrangements or just choices? Get those straight and the rest is bookkeeping.

💡 Intuition: Almost every formula here is "the product rule, then a correction for overcounting." Permutations multiply; combinations divide out the orderings we double-counted; inclusion–exclusion subtracts the overlaps we double-counted. When a formula looks mysterious, ask what did we count more than once, and by how much?

H.1 The two foundational rules (Chapter 15)

Product rule, formally. If a procedure is a sequence of $k$ steps with $n_i$ options at step $i$ (each independent of the earlier choices), the number of outcomes is

$$ n_1 \cdot n_2 \cdots n_k. $$

Example (keyspace sizing). An 8-character password over the 95 printable ASCII characters, with repeats allowed and position significant, has $95^8 \approx 6.6 \times 10^{15}$ possibilities — eight independent choices of 95 each. This is the product rule, and it is why one extra character multiplies the attacker's work by 95.

🔗 Connection: The product rule is exactly $\lvert A \times B \rvert = \lvert A \rvert \cdot \lvert B \rvert$ for Cartesian products (Chapter 8). Counting and set theory are the same idea wearing different notation.

H.2 Permutations and combinations (Chapter 16)

Both count selections of $k$ items from a set of $n$ distinct items without repetition. The only difference is whether order matters.

The link between them: $\binom{n}{k} = \dfrac{P(n,k)}{k!}$. A combination is a permutation with the $k!$ internal orderings divided out, because order does not matter.

Worked values (hand-derived).

$$ P(5,2) = 5 \cdot 4 = 20, \qquad \binom{5}{2} = \frac{5 \cdot 4}{2!} = \frac{20}{2} = 10. $$

A 5-card poker hand from 52 cards (order irrelevant): $\binom{52}{5} = 2{,}598{,}960$.

Identities you will reuse constantly:

⚠️ Common Pitfall: "$k$ at a time" reflexes toward permutations, but most real questions — committees, hands, subsets, edges of a graph — are unordered, so they use $\binom{n}{k}$. Ask "would swapping two chosen items give a different outcome?" If no, use combinations.

H.3 Inclusion–exclusion (Chapter 15/17)

To count a union of overlapping sets, add the pieces and subtract what you counted twice, then add back what you removed twice, alternating.

Two sets: $$ \lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert - \lvert A \cap B \rvert. $$

Three sets: $$ \lvert A \cup B \cup C \rvert = \lvert A \rvert + \lvert B \rvert + \lvert C \rvert - \lvert A \cap B \rvert - \lvert A \cap C \rvert - \lvert B \cap C \rvert + \lvert A \cap B \cap C \rvert. $$

General form (for sets $A_1, \dots, A_n$): $$ \left\lvert \bigcup_{i=1}^{n} A_i \right\rvert = \sum_{\emptyset \ne S \subseteq \{1,\dots,n\}} (-1)^{\lvert S \rvert + 1} \left\lvert \bigcap_{i \in S} A_i \right\rvert. $$

Use when counting how many objects have at least one of several properties, or (by complement) none of them — e.g., integers in a range divisible by 2, 3, or 5; strings containing at least one required character class.

H.4 The four cases: order × repetition (Chapters 16–17)

The central decision table. Selecting $k$ items from $n$ distinct types, the count depends on two yes/no questions. This is the "twelvefold-style" core; the right column names each case and gives a canonical CS reading.

Worked values (hand-derived). Choose $k = 3$ from $n = 4$ types:

$$ n^k = 4^3 = 64, \quad P(4,3) = 4\cdot 3 \cdot 2 = 24, \quad \binom{4}{3} = 4, \quad \binom{4+3-1}{3} = \binom{6}{3} = 20. $$

Permutations of a multiset (indistinguishable items)

When the $n$ items are not all distinct — say type $i$ appears $n_i$ times with $n_1 + \cdots + n_r = n$ — the number of distinct full arrangements is the multinomial coefficient:

$$ \binom{n}{n_1, n_2, \dots, n_r} = \frac{n!}{n_1!\,n_2! \cdots n_r!}. $$

Example. Distinct rearrangements of MISSISSIPPI (11 letters: M$\times$1, I$\times$4, S$\times$4, P$\times$2): $$ \frac{11!}{1!\,4!\,4!\,2!} = \frac{39{,}916{,}800}{1 \cdot 24 \cdot 24 \cdot 2} = 34{,}650. $$

🧩 Productive Struggle: Before reading on, classify each into one cell of the table above: (a) a 4-digit PIN; (b) a starting 5-player lineup from a 12-player roster; (c) the number of ways to distribute 10 identical cookies among 4 children. (Answers: (a) order yes / repeat yes $\to 10^4$; (b) order no / repeat no $\to \binom{12}{5}$; (c) order no / repeat yes $\to \binom{13}{3}$.)

H.5 The binomial theorem and Pascal's triangle (Chapter 16)

Binomial theorem. For any $n \ge 0$:

$$ (x + y)^{n} = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^{k}. $$

The coefficient of $x^{n-k} y^k$ is $\binom{n}{k}$: it counts the ways to pick the $k$ factors that contribute a $y$. Setting $x = y = 1$ recovers $\sum_k \binom{n}{k} = 2^n$; setting $x = 1, y = -1$ gives the alternating identity $\sum_k (-1)^k \binom{n}{k} = 0$ for $n \ge 1$.

Pascal's rule builds the coefficients without factorials — each entry is the sum of the two above it:

$$ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}. $$

Pascal's triangle (rows $n = 0$ through $5$; row $n$ holds $\binom{n}{0}, \dots, \binom{n}{n}$):

n=0:            1
n=1:           1  1
n=2:          1  2  1
n=3:         1  3  3  1
n=4:        1  4  6  4  1
n=5:       1  5 10 10  5  1

Reading row 5 across: $(x+y)^5 = x^5 + 5x^4y + 10x^3y^2 + 10x^2y^3 + 5xy^4 + y^5$. Each row sums to $2^n$ ($1, 2, 4, 8, 16, 32$).

🔗 Connection: Pascal's rule is the recurrence behind the standard dynamic-programming table for $\binom{n}{k}$ — fill the triangle bottom-up in $O(nk)$ time and you never overflow on intermediate factorials. It mirrors the "include $x$ or exclude $x$" case split used throughout counting proofs.

H.6 The pigeonhole principle (Chapter 17)

🚪 Threshold Concept: Pigeonhole proves something must exist without ever constructing it. It turns "there are more items than containers" into a guarantee — the workhorse behind hash collisions, lossless-compression limits, and many existence arguments.

Basic form. If $n$ items are placed into $m$ boxes and $n > m$, then some box contains at least two items.

Generalized form. If $n$ items go into $m$ boxes, some box contains at least

$$ \left\lceil \frac{n}{m} \right\rceil $$

items.

Example. Among any 13 people, at least $\lceil 13/12 \rceil = 2$ share a birth month.

⚠️ Common Pitfall: Pigeonhole tells you a collision exists, never which box or which pair. It is a pure existence result — pair it with a constructive search if you need the witness.

H.7 Stars and bars (Chapter 17)

The tool for distributing identical items into distinct bins — equivalently, counting non-negative integer solutions of an equation. Picture $k$ identical stars in a row and $n-1$ bars that split them into $n$ groups.

Non-negative solutions of $x_1 + x_2 + \cdots + x_n = k$ (bins may be empty):

$$ \binom{n + k - 1}{k} = \binom{n + k - 1}{\,n - 1\,}. $$

Positive solutions ($x_i \ge 1$, every bin non-empty): give each bin one item first, then distribute the remaining $k - n$ freely:

$$ \binom{k - 1}{\,n - 1\,}. $$

Example. Distribute $k = 10$ identical cookies among $n = 4$ children, any child may get zero: $\binom{10 + 4 - 1}{4 - 1} = \binom{13}{3} = 286$.

💡 Intuition: Stars and bars is exactly the "order no / repetition yes" cell of H.4 — choosing a multiset of size $k$ from $n$ types is deciding how many of each type, i.e., a non-negative solution of $x_1 + \cdots + x_n = k$.

H.8 Key recurrences and named sequences (Chapters 18–19)

Many counts are easiest to state as a recurrence — a self-referential rule plus base case(s) — then solved for a closed form (Chapter 19).

Hand-derived checks. Derangements of 4 items: $D_4 = 4!\left(1 - 1 + \tfrac12 - \tfrac16 + \tfrac{1}{24}\right) = 24 \cdot \tfrac{9}{24} = 9$. Catalan $C_3 = \tfrac{1}{4}\binom{6}{3} = \tfrac{20}{4} = 5$ — the five shapes of a binary tree with 3 nodes, and the five ways to fully parenthesize 4 factors.

🔗 Connection: The Fibonacci closed form (Chapter 19) is the Part III payoff for the book's Fibonacci thread: a recurrence that looks $O(n)$ collapses to an $O(\log n)$ matrix-power algorithm. Recurrences are not just counting tools — they are the cost equations of recursive code (Chapter 18).

H.9 A counting decision procedure

When a problem lands on your desk, walk this checklist:

1. Is it a sequence of independent steps?        → PRODUCT RULE (multiply)
2. Is it disjoint cases?                          → SUM RULE (add)
   ...with overlap?                               → INCLUSION–EXCLUSION
3. Selecting k of n? Ask two questions:
      order matters?  repetition allowed?         → pick the cell in H.4
        yes / yes → n^k        yes / no → P(n,k)
        no  / no  → C(n,k)     no  / yes → C(n+k-1, k)
   ...items not all distinct?                     → MULTINOMIAL  n!/(n1!...nr!)
4. Distributing identical items into bins?        → STARS AND BARS
5. "Must two share a box?"                        → PIGEONHOLE (existence)
6. Defined in terms of smaller cases?             → set up a RECURRENCE, then solve

⚠️ Common Pitfall — double counting. The single most frequent counting error is counting the same outcome more than once. After you compute, ask: did I treat two identical arrangements as different (overcount — divide it out), or two different cases as the same (undercount — split them)? When unsure, count a tiny instance (say $n = 3$) by brute-force listing and check it against your formula. Verifying a count on small cases is the combinatorial version of a unit test — a habit worth keeping.

Toolkit cross-reference

The Discrete Math Toolkit implements this appendix in combinatorics.py (built in Chapters 15–17): perm_count(n, k) returns $P(n,k)$, comb_count(n, k) returns $\binom{n}{k}$, and permutations/ combinations enumerate the actual selections. Use the closed forms here to predict a count, then let the code confirm it on small inputs — proof and computation, checking each other.