References: Rosen 8e §§6.1–6.5; Tucker, Applied Combinatorics, 6e ch. 5; Graham–Knuth–Patashnik, Concrete Mathematics ch. 5.
2 / 30
1.1 Sum rule (rule of disjoint cases)
Let $A$ and $B$ be disjoint finite sets. Then $|A \cup B| = |A| + |B|$. More generally, for pairwise disjoint $A_1, \dots, A_k$: $|A_1 \cup \dots \cup A_k| = |A_1| + \dots + |A_k|$.
Listing the elements of $A$ first, then those of $B$, gives a list of length $|A| + |B|$ with no repetitions (by disjointness). Hence $|A \cup B| = |A| + |B|$. The $k$-fold version follows by induction on $k$. $\square$
A student must choose either a math course (12 options) or a physics course (9 options); the lists are disjoint. Total choices: $12 + 9 = 21$.
Disjointness is essential. If $A$ and $B$ overlap, double counting occurs and one must use inclusion–exclusion (slide 27).
Rosen 8e §6.1; Tucker §5.1.
3 / 30
1.2 Product rule
If a task consists of two sub-tasks $T_1$ and $T_2$, where $T_1$ can be done in $m$ ways and, for each choice of $T_1$, $T_2$ can be done in $n$ ways, then the whole task can be done in $m \cdot n$ ways. By induction on the number of sub-tasks, the count for $k$ independent sub-tasks of sizes $n_1, n_2, \dots, n_k$ is $n_1 n_2 \cdots n_k$.
The set of joint outcomes is in bijection with the Cartesian product $S_1 \times S_2$, where $S_i$ is the set of choices for $T_i$. By the size of a Cartesian product (Relations & Functions §1.1), $|S_1 \times S_2| = |S_1| \cdot |S_2| = m n$. The general $k$-fold case follows by induction. $\square$
A lion hunts by chasing, trapping, or sneaking ($3$ ways) an antelope, a buffalo, or a giraffe ($3$ choices). By the product rule there are $3 \times 3 = 9$ possible hunting actions.
Number of $4$-letter lowercase passwords: $26 \times 26 \times 26 \times 26 = 26^4 = 456{,}976$.
Rosen 8e §6.1; Tucker §5.1.
4 / 30
1.3 Tree diagrams and combined rules
A tree diagram visualises a sequence of choices. Each internal node represents a decision point; its children are the available options. The number of leaves equals the number of distinct outcomes.
How many $3$-bit strings have no two consecutive $0$s?
At each position the choice depends on the previous bit. Drawing the tree gives leaves: $\{010, 011, 101, 110, 111\}$ plus the string $\{010\}$ and $\{010, 011, 100, 101, 110, 111\}$ — careful enumeration gives $5$ valid strings of length $3$. By the Zeckendorf-style recurrence $a_n = a_{n-1} + a_{n-2}$ with $a_1 = 2$, $a_2 = 3$: $a_3 = 5$.
A menu offers $3$ starters, $5$ mains, $2$ desserts. If a customer must choose either a starter+main, or a main+dessert (but not both pairs), the count is $(3 \cdot 5) + (5 \cdot 2) = 15 + 10 = 25$ — product rule inside each case, sum rule across the disjoint cases.
Rosen 8e §6.1.
5 / 30
2.1 Permutations of $n$ objects — factorials
A permutation of a finite set $S$ is an ordered arrangement of all its elements — equivalently, a bijection $S \to S$.
The number of permutations of $n$ distinct objects is $n! := n \cdot (n-1) \cdot (n-2) \cdots 2 \cdot 1$, with the convention $0! = 1$.
Build the permutation position by position. There are $n$ choices for the first position; $n - 1$ for the second (any object except the first); $n - 2$ for the third; …; $1$ for the last. By the product rule the total is $n \cdot (n-1) \cdots 1 = n!$. $\square$
Number of ways $9$ athletes can finish a race: $9! = 362{,}880$.
Convention $0! = 1$ matches the empty-product convention and makes the formula $P(n, k) = n! / (n - k)!$ (next slide) hold at $k = n$.
Rosen 8e §6.3 Theorem 1.
6 / 30
2.2 $k$-permutations $P(n, k)$
A $k$-permutation of an $n$-element set $S$ is an ordered selection of $k$ distinct elements of $S$, where $0 \leq k \leq n$. The number of such arrangements is denoted $P(n, k)$ or $A_n^k$ (the French "arrangements") or $n^{\underline{k}}$ (the falling factorial).
$\displaystyle P(n, k) \;=\; n (n-1)(n-2) \cdots (n - k + 1) \;=\; \frac{n!}{(n - k)!}.$
Fill the $k$ positions one at a time, repetitions forbidden: $n$ choices for position $1$, $n - 1$ for position $2$, …, $n - k + 1$ for position $k$. By the product rule, the count is the product $n(n-1)\cdots(n-k+1)$. Multiplying numerator and denominator by $(n - k)!$ gives $n!/(n-k)!$. $\square$
Number of possible top-three rankings among $9$ athletes: $P(9, 3) = 9 \cdot 8 \cdot 7 = 504$.
Rosen 8e §6.3 Theorem 2.
7 / 30
2.3 Permutations with repeated objects
Let $n$ objects be partitioned into $k$ classes of indistinguishable items of sizes $n_1, n_2, \dots, n_k$ with $n_1 + n_2 + \cdots + n_k = n$. The number of distinguishable orderings of these $n$ items is
$$\frac{n!}{n_1! \, n_2! \cdots n_k!}.$$
First treat all $n$ objects as distinct — $n!$ arrangements. Inside class $i$, the $n_i!$ orderings of identical objects look the same to us; dividing by $n_i!$ removes this overcounting. By repeating the argument for each class, we divide by $\prod_i n_i!$. $\square$
Number of distinct anagrams of "MISSISSIPPI" (letters: $1$ M, $4$ I, $4$ S, $2$ P):
$$\frac{11!}{1!\,4!\,4!\,2!} = \frac{39{,}916{,}800}{1 \cdot 24 \cdot 24 \cdot 2} = 34{,}650.$$
Circular permutations
The number of arrangements of $n$ distinct objects around a circle (rotation considered the same) is $(n - 1)!$. Reflections also considered equal: $(n-1)!/2$ for $n \geq 3$.
Rosen 8e §6.5 Theorem 3; Tucker §5.4.
8 / 30
3.1 Combinations $C(n, k) = \binom{n}{k}$
A $k$-combination of an $n$-element set is an unordered selection of $k$ elements — equivalently, a $k$-subset. Their count is the binomial coefficient:
$$C(n, k) \;=\; \binom{n}{k} \;=\; \frac{n!}{k!\,(n-k)!}, \quad 0 \leq k \leq n.$$
Every $k$-permutation is obtained from a $k$-combination by ordering its $k$ elements; each combination yields exactly $k!$ permutations. Hence
$P(n, k) = k! \cdot C(n, k)$, giving $C(n, k) = P(n, k) / k! = n! / \bigl(k! (n - k)!\bigr)$. $\square$
Number of teams of $5$ from a roster of $12$ players: $\binom{12}{5} = 792$.
Number of $4$-friend graduation parties chosen from $10$ friends: $\binom{10}{4} = 210$.
Symmetry. $\binom{n}{k} = \binom{n}{n-k}$ — choosing $k$ to keep is the same as choosing $n - k$ to discard.
Rosen 8e §6.3 Theorem 3.
9 / 30
3.2 Pascal's identity
For all integers $n \geq 1$ and $1 \leq k \leq n$:
$$\binom{n}{k} \;=\; \binom{n-1}{k-1} \;+\; \binom{n-1}{k}.$$
Combinatorial proof. Fix any element $a$ of an $n$-set $S$. Partition the $k$-subsets of $S$ into two classes:
Those containing $a$: choose the remaining $k - 1$ elements from $S \setminus \{a\}$ — $\binom{n-1}{k-1}$ subsets.
Those not containing $a$: choose all $k$ elements from $S \setminus \{a\}$ — $\binom{n-1}{k}$ subsets.
The two classes are disjoint and exhaust the $k$-subsets, so by the sum rule, $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$. $\square$
$\displaystyle \sum_{k=0}^{n} \binom{n}{k} = 2^n$ — the number of subsets of an $n$-set (proved by counting subsets two ways, or by setting $x = y = 1$ in the binomial theorem).
$\displaystyle \sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0$ for $n \geq 1$ — set $x = -1, y = 1$.
Hockey-stick identity: $\displaystyle \sum_{i=r}^{n} \binom{i}{r} = \binom{n+1}{r+1}$ — easy induction on $n$ using Pascal.
Rosen 8e §6.4.
11 / 30
4. Binomial theorem
For all $x, y$ and every integer $n \geq 0$:
$$(x + y)^n \;=\; \sum_{k=0}^{n} \binom{n}{k}\, x^{n-k}\, y^{k}.$$
Combinatorial proof. Expand $(x + y)^n = (x + y)(x + y) \cdots (x + y)$, $n$ factors. Distributing yields $2^n$ monomials of the form $z_1 z_2 \cdots z_n$, each $z_i \in \{x, y\}$. The monomial $x^{n-k} y^k$ corresponds to choosing $k$ factors that contribute $y$ — there are $\binom{n}{k}$ such choices. Collecting like terms gives the formula. $\square$
Inductive proof. Base $n = 0$: $(x+y)^0 = 1 = \binom{0}{0} x^0 y^0$. Step: assume the formula at $n$. Then
$(x+y)^{n+1} = (x+y)(x+y)^n = (x+y) \sum_k \binom{n}{k} x^{n-k}y^k = \sum_k \binom{n}{k}\bigl(x^{n-k+1} y^k + x^{n-k} y^{k+1}\bigr).$
Re-indexing the second sum and applying Pascal's identity (slide 10) gives $\sum_k \binom{n+1}{k} x^{n+1-k} y^k$. $\square$
Coefficient of $x^3 y^4$ in $(x + y)^7$ is $\binom{7}{4} = 35$. Coefficient of $x^5$ in $(2 + x)^9$ is $\binom{9}{5} \cdot 2^{4} = 126 \cdot 16 = 2016$.
Rosen 8e §6.4 Theorem 1.
12 / 30
5. Combinations with repetition (stars and bars)
The number of multisets of size $k$ drawn from an $n$-element alphabet — equivalently the number of solutions of $x_1 + x_2 + \cdots + x_n = k$ in non-negative integers — is
$$\binom{n + k - 1}{k} \;=\; \binom{n + k - 1}{n - 1}.$$
Bijection — stars and bars. Encode a non-negative integer solution by a string of $k$ stars and $n - 1$ bars: $x_i$ stars in segment $i$, separated by bars. Example with $n=3, k=4$: $(2,0,2) \mapsto \star\star\,|\,|\,\star\star$. Each such string has length $n + k - 1$; the count is the number of ways to choose the $k$ star positions (or the $n - 1$ bar positions) among $n + k - 1$ slots, giving $\binom{n+k-1}{k}$. $\square$
Number of ways to distribute $10$ identical candies among $4$ children: $\binom{4 + 10 - 1}{10} = \binom{13}{10} = 286$.
Number of ways to pick a dozen donuts from $5$ flavours: $\binom{5 + 12 - 1}{12} = \binom{16}{12} = 1820$.
Rosen 8e §6.5 Theorem 2; Tucker §5.6.
13 / 30
6. The four counting problems — summary
Order matters?
Repetition allowed?
Formula
Name
Yes
Yes
$n^k$
Strings (Cartesian product)
Yes
No
$P(n, k) = n!/(n-k)!$
$k$-permutation (arrangement)
No
No
$\binom{n}{k} = n!/(k!(n-k)!)$
$k$-combination
No
Yes
$\binom{n+k-1}{k}$
Multiset / stars-and-bars
Workflow. When facing a counting problem, ask two questions:
Does the order of the chosen items matter?
Can the same item be selected more than once?
Answering both immediately points to one of the four boxes above.
Rosen 8e §6.5 Table 1.
14 / 30
7.1 Worked example — sprint with 9 athletes
Consider $4$ Swiss, $5$ Ethiopian athletes ($9$ total) competing for the $200$ m sprint.
How many different rankings of all athletes? Permutation of $9$ distinct people: $9! = 362{,}880$.
How many different rankings if we only distinguish nationality (orderings within each country count separately)? Order Swiss among themselves and Ethiopians among themselves: $4! \cdot 5! = 24 \cdot 120 = 2{,}880$.
How many top-three winner rankings? $P(9, 3) = 9 \cdot 8 \cdot 7 = 504$.
How many teams of $5$ athletes (unordered)? $\binom{9}{5} = 126$.
Now add $3$ Brazilian athletes ($12$ total).
How many teams of $5$? $\binom{12}{5} = 792$.
How many rankings by national flag only (multiset permutation)? $\binom{12}{4, 5, 3} = \frac{12!}{4! \cdot 5! \cdot 3!} = 27{,}720$ (multinomial — see next slide).
How many teams of $5$ with exactly $2$ Swiss, $2$ Ethiopians, $1$ Brazilian? Independent choices: $\binom{4}{2} \binom{5}{2} \binom{3}{1} = 6 \cdot 10 \cdot 3 = 180$.
Adapted from Rosen 8e §6.3 Examples.
15 / 30
8.1 Multinomial coefficients
For non-negative integers $n_1, n_2, \dots, n_k$ with $n_1 + n_2 + \cdots + n_k = n$, the multinomial coefficient is
$$\binom{n}{n_1, n_2, \dots, n_k} \;:=\; \frac{n!}{n_1!\,n_2! \cdots n_k!}.$$
It counts the number of ways to split $n$ distinct objects into $k$ ordered groups of sizes $n_1, n_2, \dots, n_k$.
Pick the first group in $\binom{n}{n_1}$ ways. From the remaining $n - n_1$, pick the second group in $\binom{n - n_1}{n_2}$ ways. Continue. Multiplying with the product rule and simplifying:
$\binom{n}{n_1}\binom{n - n_1}{n_2} \cdots \binom{n - n_1 - \cdots - n_{k-1}}{n_k} = \frac{n!}{n_1!(n - n_1)!} \cdot \frac{(n - n_1)!}{n_2!(n - n_1 - n_2)!} \cdots = \frac{n!}{n_1!\,n_2! \cdots n_k!}.$ $\square$
For $k = 2$, $\binom{n}{n_1, n_2} = \binom{n}{n_1}$ — the multinomial reduces to the binomial.
For any $x_1, x_2, \dots, x_k$ and integer $n \geq 0$:
$$(x_1 + x_2 + \cdots + x_k)^n \;=\; \sum_{\substack{n_1 + n_2 + \cdots + n_k = n \\ n_i \geq 0}} \binom{n}{n_1, n_2, \dots, n_k}\, x_1^{n_1} x_2^{n_2} \cdots x_k^{n_k}.$$
Expand the product of $n$ factors $(x_1 + x_2 + \cdots + x_k)$. Each term comes from picking one $x_{i_j}$ from each factor. The product $x_1^{n_1} \cdots x_k^{n_k}$ arises whenever the multiset of choices contains $n_1$ copies of $x_1$, etc. The number of orderings producing this multiset of choices is the multinomial coefficient (slide 16). $\square$
Coefficient of $x^2 y^3 z$ in $(x + y + z)^6$:
$\binom{6}{2, 3, 1} = \frac{6!}{2!\,3!\,1!} = \frac{720}{2 \cdot 6 \cdot 1} = 60$.
Rosen 8e §6.4 Theorem 3.
17 / 30
9.1 Pigeonhole principle (basic form)
If $n$ pigeons are placed into $k$ pigeonholes and $n > k$, then at least one hole contains at least $2$ pigeons.
By contradiction. Suppose every hole has at most $1$ pigeon. Summing over the $k$ holes, the total number of pigeons is at most $k$. But we placed $n > k$ pigeons, contradiction. $\square$
Among any $13$ dogs, at least two were born in the same month (only $12$ months).
In a group of $367$ people, at least two share a birthday (only $366$ possible birthdays counting Feb 29).
Rosen 8e §6.2 Theorem 1.
18 / 30
9.2 Generalised pigeonhole principle
If $N$ pigeons are placed into $k$ holes, then at least one hole contains at least $\lceil N / k \rceil$ pigeons.
By contradiction. Suppose every hole has at most $\lceil N/k \rceil - 1$ pigeons. Then the total number of pigeons is at most $k \cdot (\lceil N/k \rceil - 1) < k \cdot (N/k) = N$. (Using $\lceil x \rceil - 1 < x$.) Contradiction. $\square$
A bank has $1{,}000{,}000$ clients, each with a $4$-letter lowercase password. There are $26^4 = 456{,}976$ possible passwords. By generalised pigeonhole,
$\lceil 1{,}000{,}000 / 456{,}976 \rceil = \lceil 2.188\dots \rceil = 3$,
so at least one password is shared by at least $3$ clients.
In any group of $100$ people, at least $\lceil 100/12 \rceil = 9$ share a birth month.
Rosen 8e §6.2 Theorem 2.
19 / 30
9.3 Pigeonhole — selected applications
Among any $11$ integers, some two have the same last digit.
There are only $10$ possible last digits ($0$ through $9$). By pigeonhole on $11$ pigeons / $10$ holes, two integers share a last digit. $\square$
In any sequence of $n^2 + 1$ distinct real numbers, there is a monotone (increasing or decreasing) subsequence of length $n + 1$. (Erdős–Szekeres, 1935.)
Sketch. Label each term with the pair $(i_k, d_k)$ where $i_k$ (resp. $d_k$) is the length of the longest increasing (resp. decreasing) subsequence ending at position $k$. If no subsequence of length $n+1$ exists, both coordinates lie in $\{1, \dots, n\}$, giving at most $n^2$ distinct labels — but we have $n^2 + 1$ terms, contradicting the fact that distinct positions force distinct labels (because distinct values either grow or shrink the relevant subsequence). $\square$
Each element $x$ of $\bigcup A_i$ belongs to a non-empty index set $I_x \subseteq \{1, \dots, n\}$. Its contribution to the right side is $\sum_{\varnothing \neq T \subseteq I_x} (-1)^{|T|+1}$. By the binomial identity $\sum_{k=0}^{m}(-1)^k \binom{m}{k} = 0$ for $m \geq 1$, this sum equals $1$. So each element is counted exactly once on the right, matching $|\bigcup A_i|$. $\square$
Combinatorial. The LHS counts $r$-subsets of $\{1, \dots, m + n\}$. Split this set into the first $m$ and last $n$ elements: any $r$-subset contains $k$ elements from the first part and $r - k$ from the second, for some $0 \leq k \leq r$. The number of such subsets is $\binom{m}{k} \binom{n}{r-k}$; summing over $k$ gives the RHS. $\square$
Hockey-stick identity. For $n \geq r \geq 0$:
$\displaystyle \sum_{i=r}^{n} \binom{i}{r} \;=\; \binom{n+1}{r+1}.$
Induction on $n$. Base $n = r$: $\binom{r}{r} = 1 = \binom{r+1}{r+1}$. Step: assume the identity at $n$. Then
$\sum_{i=r}^{n+1} \binom{i}{r} = \binom{n+1}{r+1} + \binom{n+1}{r} = \binom{n+2}{r+1}$ (Pascal's identity, slide 10). $\square$
Rosen 8e §6.4 Theorems 4 & 5.
22 / 30
12.1 Worked example — poker hands
A standard $52$-card deck has $4$ suits and $13$ ranks. A poker hand is $5$ cards from the deck.
Total hands: $\binom{52}{5} = 2{,}598{,}960$.
Royal flush (10–J–Q–K–A of one suit): $4$ hands.
Four of a kind: choose the rank ($13$), the four suits (only $1$ way: all of them), then the fifth card (any of the remaining $48$). Total: $13 \cdot 48 = 624$.
Full house (three of a rank + pair of another): $13 \cdot \binom{4}{3} \cdot 12 \cdot \binom{4}{2} = 13 \cdot 4 \cdot 12 \cdot 6 = 3{,}744$.
Flush (5 cards of one suit, not in sequence): $4 \cdot \binom{13}{5} - $ (straight flushes) $= 4 \cdot 1287 - 40 = 5{,}108$.
The remaining hand probabilities follow the same recipe — choose ranks, then suits, then any remaining "kicker" cards, using product and sum rules.
Tucker §5.3; Concrete Mathematics §5.
23 / 30
12.2 Worked example — derangements via inclusion–exclusion
A derangement of $\{1, \dots, n\}$ is a permutation $\sigma$ with $\sigma(i) \neq i$ for every $i$ — no fixed points. Their count is denoted $D_n$ (or $!n$, "subfactorial").
$\displaystyle D_n \;=\; n!\,\sum_{k=0}^{n}\frac{(-1)^k}{k!}.$ Equivalently, $D_n$ is the nearest integer to $n!/e$.
Let $A_i$ = "permutations fixing $i$". Then permutations with at least one fixed point form $\bigcup A_i$, and derangements are the complement. For $|T| = k$, $|A_{i_1} \cap \cdots \cap A_{i_k}| = (n - k)!$ (the other $n - k$ positions are free). By inclusion–exclusion,
$|A_1 \cup \cdots \cup A_n| = \sum_{k=1}^{n} (-1)^{k+1} \binom{n}{k}(n-k)!$.
Hence $D_n = n! - \sum_{k=1}^{n}(-1)^{k+1}\binom{n}{k}(n-k)! = n!\sum_{k=0}^{n}(-1)^k/k!$. $\square$
$D_1 = 0$, $D_2 = 1$, $D_3 = 2$, $D_4 = 9$, $D_5 = 44$, $D_6 = 265$, $D_7 = 1854$, $D_{10} = 1{,}334{,}961$. As $n \to \infty$, $D_n / n! \to 1/e \approx 0.3679$ — about $37\%$ of all permutations are derangements.
Rosen 8e §8.6; Tucker §8.2.
24 / 30
13. Python toolbox
Python — imports (run once)from math import factorial, comb, perm
from itertools import permutations, combinations, product
from itertools import combinations_with_replacement
from sympy import binomial, multinomial_coefficients, Sum, symbols, oo, Rational
Python — Monte-Carlo confirmationimport random
def trial(n, d=365):
bdays = [random.randint(1, d) for _ in range(n)]
return len(set(bdays)) < n # True iff there is a collision
def estimate(n, trials=100_000):
hits = sum(trial(n) for _ in range(trials))
return hits / trials
print(estimate(23)) # ≈ 0.507
Tucker §5.7; Concrete Mathematics §5.
26 / 30
15. Strategy — picking the right counting formula
You see…
Reach for…
"or" between disjoint cases
Sum rule (slide 3)
"then" / "and" / sequential choices
Product rule (slide 4)
Arrangements of all $n$ items
$n!$ (slide 6)
$k$ items chosen, order matters, no repetition
$P(n, k)$ (slide 7)
$k$ items chosen, order ignored, no repetition
$\binom{n}{k}$ (slide 9)
$k$ items chosen, order ignored, repetition allowed
$\binom{n+k-1}{k}$ (slide 13)
Split $n$ distinct items into ordered groups
Multinomial $\binom{n}{n_1,\dots,n_k}$ (slide 16)
Arrangements with repeated identical items
$n!/(n_1! \cdots n_k!)$ (slide 8)
"Must contain at least two of …"
Pigeonhole (slide 18) or generalised (slide 19)
"At least one of $A$, $B$, $C$"
Inclusion–exclusion (slide 21)
Coefficient of a monomial in $(x_1 + \dots + x_k)^n$
Multinomial theorem (slide 17)
Rosen 8e §6.5; Tucker chapter strategy.
27 / 30
16. Summary — what we proved
Sum and product rules — combinatorial counterparts of $|A \cup B| = |A| + |B|$ (disjoint) and $|A \times B| = |A|\,|B|$.
Permutations: $n!$ arrangements of $n$ distinct objects; $P(n, k) = n!/(n-k)!$ $k$-permutations; with repetition the multinomial division formula.
Combinations: $\binom{n}{k} = n!/(k!(n-k)!)$ derived from $P(n,k) = k! \binom{n}{k}$.
K. H. Rosen. Discrete Mathematics and Its Applications, 8th ed., McGraw-Hill, 2019 — §6.1 (basics of counting), §6.2 (pigeonhole), §6.3 (permutations and combinations), §6.4 (binomial coefficients), §6.5 (combinations with repetition), §8.5–8.6 (inclusion–exclusion, derangements).