Chapter 4: Permutations and Combinations

Foundational Principles: The Fundamental Rules of Counting

Before tackling complex capacity constraints and allocations, every combinatorial problem relies on two foundational principles: the Multiplication Principle (Rule of Product) and the Addition Principle (Rule of Sum). Understanding when to multiply and when to add forms the bedrock of discrete mathematics.

Common Applications of the Multiplication Principle

---

Permutations and Combinations of Sets

Combinatorics begins by clarifying two fundamental conditions of choice: whether the order of selection matters and whether selection occurs with or without replacement. Given a set of four distinct objects $\{A, B, C, D\}$, choosing two objects in order without replacement produces $12$ ordered pairs such as $AB$ and $BA$. Choosing an unordered pair without replacement produces $6$ unique subsets such as $\{A, B\}$.

Why Divide by $r!$? When order is ignored, every $r$-element subset generates exactly $r!$ distinct ordered sequences. Dividing the total ordered count $P(n,r)$ by $r!$ collapses permutations into equivalence classes of size $r!$, where each class corresponds to a single unique subset.

Why the Permutation and Combination Formulas Work

Counting ordered selections

To build an ordered selection of $r$ different objects from $n$, fill its positions one at a time. There are $n$ choices for the first position, $n-1$ for the second, and so on. After $r-1$ objects have been used, there are $n-r+1$ choices for the last position. By the multiplication principle,

Using $n! = n(n-1)\cdots 1$ and the convention $0! = 1$, split the factors of $n!$ after the first $r$ factors:

When $r=0$, there is one way to choose no objects—the empty selection—so $P(n,0)=1$, which agrees with the formula. When $r=n$, this gives $P(n,n)=n!$, the number of ways to arrange all $n$ objects.

Counting unordered selections

We can make an ordered selection in two steps: first choose which $r$ objects to use, then arrange those chosen objects. There are $\binom{n}{r}$ ways to do the first step and $r!$ ways to do the second. Every ordered selection comes from exactly one such choice-and-arrangement pair, so

In short: permutations count the chosen objects and their order; combinations count only which objects were chosen.

---

The Core Distinction: Selection With vs. Without Replacement

To master counting problems, we must explicitly distinguish between sampling without replacement and sampling with replacement:

• Without Replacement: Once an object is chosen from the pool, it is removed and cannot be selected again. The pool size shrinks by $1$ after each draw ($n, n-1, n-2, \dots$). This models assignments where no element can occupy two positions simultaneously (e.g., elected officer roles, drawing cards from a deck).
• With Replacement: After an object is chosen, it is inspected and returned to the pool. The pool size remains constant ($n$) for every single selection. This allows the exact same item to be selected multiple times (e.g., rolling dice, generating passcode digits, assigning independent treatment plans).

---

Combinations via Binary String Encoding (Choose vs. Reject)

A powerful intuitive model for understanding combinations comes from encoding subset selections as binary string decisions. Suppose we have a set of $n = 5$ named individuals: John, Mary, David, Sarah, and James ($N = \{1, 2, 3, 4, 5\}$), and we wish to choose an unordered committee of $r = 3$ people.

Instead of picking individuals one by one, set up $5$ ordered slots representing the $5$ candidates in fixed order. For each slot, assign either a "C" (Choose) or an "R" (Reject) label:

Every possible committee of size $r = 3$ maps bijectively to a 5-letter word consisting of exactly $3$ copies of symbol C and $2$ copies of symbol R. The number of distinct arrangements of this multiset word is given by the multinomial coefficient:

Symmetry Identity ($\binom{n}{r} = \binom{n}{n-r}$): This binary string perspective makes complementary symmetry glaringly obvious. Selecting $r$ elements to include (choosing $r$ "C"s) forces $n-r$ elements to be excluded (choosing $n-r$ "R"s). Swapping the role of "Choose" and "Reject" leaves the denominator $r! (n-r)!$ completely unchanged:

We can count all subsets in two ways. First, each of the $n$ elements has two independent choices: include it or leave it out. By the multiplication principle, this gives $2 \times 2 \times \cdots \times 2 = 2^n$ subsets. Alternatively, group the subsets by their size: there are $\binom{n}{r}$ subsets containing exactly $r$ elements. Since every subset has exactly one size from $0$ through $n$, adding these groups counts every subset exactly once:

---

Two Perspectives on Selection and Arrangement

When solving problems that involve both selecting elements and ordering them without replacement, there are two equivalent conceptual workflows:

---

Constrained Permutations: The Block Strategy

When arranging items with grouping requirements (e.g., keeping related items adjacent), use the Block Strategy: treat each required cluster of adjacent items as a single macro-element ("block"), arrange the blocks, and then multiply by the internal permutations within each block.

---

Permutations and Combinations of Multisets

A multiset is a collection where objects are allowed to repeat with specific multiplicities. In the multiset $\{A, A, B\}$, the two copies of $A$ are completely indistinguishable. Its distinct linear arrangements are $AAB$, $ABA$, and $BAA$—yielding 3 unique outcomes rather than $3! = 6$.

---

Strings Over Finite Alphabets

An alphabet $\Sigma$ is a finite set of symbols. A string (or word) of length $n$ over $\Sigma$ is an ordered sequence $(w_1, w_2, \dots, w_n)$ where $w_i \in \Sigma$. If $|\Sigma| = q$, the product rule implies there are $|\Sigma^n| = q^n$ possible words of length $n$.

A bijection is a one-to-one correspondence between two sets: every element on either side matches exactly one element on the other. A bijection proves that the sets have the same size, so counting either set gives the count for both.

For a binary alphabet $\Sigma = \{0, 1\}$, the weight of a string is defined as the number of positions containing $1$. Mapping each binary string to the subset of index positions containing $1$ establishes a classic bijection between binary strings of length $n$ and subsets of $\{1, 2, \dots, n\}$.

---

Stars and Bars, with Upper and Lower Bounds

Suppose $N$ indistinguishable objects enter $k$ labeled bins ($N \ge 0, k \ge 1$), allowing empty bins. An allocation corresponds to a weak composition of $N$: an integer vector $(x_1, x_2, \dots, x_k)$ satisfying $\sum_{i=1}^k x_i = N$ with $x_i \ge 0$.

When each bin must receive at least $\ell_i$ objects, set $y_i = x_i - \ell_i$ and $M = N - \sum_i \ell_i$. If $M \ge 0$, the number of allocations is $\binom{M+k-1}{k-1}$; if $M < 0$, there are no valid allocations.

Representing the $N$ objects as stars (*) and separating the $k$ bins using $k-1$ bars (|) yields a sequence of length $N + k - 1$. Choosing the $k-1$ positions for the bars establishes the unconstrained formula:

Inclusion–exclusion principle: For two overlapping sets $A$ and $B$, $|A \cup B| = |A| + |B| - |A \cap B|$. For several properties, alternate adding the counts of single violations, subtracting pairwise overlaps, and continuing with higher-order intersections. This prevents outcomes satisfying multiple violations from being counted more than once.

Upper Bounds via Inclusion-Exclusion: When coordinates are restricted by upper bounds $0 \le y_i \le c_i$, we define a property $P_i$ as the condition that bin $i$ violates its upper bound ($y_i \ge c_i + 1$). Applying Inclusion-Exclusion subtracts invalid allocations:

In this formula, treat a term as zero whenever $M - \sum_{i \in S}(c_i+1) < 0$, since no allocations remain for that term.

---

Counting Functions: Injections, Surjections, and Bijections

A function $f: D \to B$ from a domain of size $|D| = n$ to a codomain of size $|B| = m$ assigns each input to one output. In balls-and-bins terminology, this represents distributing $n$ distinct balls into $m$ labeled bins.

Formula for Surjections: Subtracting functions missing at least $j$ specified codomain elements using Inclusion-Exclusion yields:

---

The Power of Bijective Proofs in Combinatorics

The core principle of a bijective proof is remarkably simple: If two sets can be perfectly paired up with no items left over, they must contain the exact same number of elements.

Applications of Bijective Proofs

---

Balls into Bins: Distinguishable and Indistinguishable Objects

One of the most fundamental frameworks in combinatorics is the distribution of $n$ objects (balls) into $k$ containers (bins). To solve any distribution problem correctly, you must first ask two crucial questions:

These choices give four combinations of object and bin distinguishability. Work through each case below, then use the summary matrix to compare their models and counts.

---

Case 1: Distinct Balls into Labeled Bins ($k^n$)

In this scenario, every single ball is unique (e.g., labeled $a, b, c$), and every bin has a distinct label (e.g., Bin $A$ and Bin $B$).

Why the Formula is $k^n$

Think about assigning the balls one by one:

• Ball $a$ can be placed into any of the $k$ bins ($k$ choices).
• Ball $b$ can be placed into any of the $k$ bins ($k$ choices).
• Ball $c$ can be placed into any of the $k$ bins ($k$ choices).

By the Multiplication Principle of counting, the total number of distinct assignments is:

$$\underbrace{k \times k \times \dots \times k}_{n \text{ factors}} = k^n$$

Mathematically, this corresponds to the number of functions $f: D \to B$ from a domain $D$ of size $n$ (the balls) to a codomain $B$ of size $k$ (the bins).

---

Case 2: Identical Balls into Labeled Bins ($\binom{n+k-1}{k-1}$)

Here, the $n$ balls are completely identical (no labels or colors to distinguish them), but the $k$ bins remain distinctly labeled ($A, B, C, \dots$).

Understanding Occupancy Vectors & Stars and Bars

Because the balls cannot be told apart, an outcome is uniquely determined by an occupancy vector $(x_1, x_2, \dots, x_k)$, where $x_i$ is the number of balls placed in Bin $i$. These non-negative integers must satisfy:

$$x_1 + x_2 + \dots + x_k = n \quad \text{where } x_i \ge 0$$

To count the number of solution vectors, we use the famous Stars and Bars method:

1. Represent the $n$ identical balls as $n$ stars ($\star$).
2. Use $k - 1$ vertical bars ($\mid$) as dividers to separate the stars into $k$ distinct bin regions.
3. Any arrangement of $n$ stars and $k - 1$ bars corresponds to a unique distribution vector.

The total length of the sequence is $n + (k - 1)$ positions. Choosing $k - 1$ positions for the bars yields the formula:

$$\binom{n + k - 1}{k - 1} \quad \text{or equivalently} \quad \binom{n + k - 1}{n}$$

---

Case 3: Distinct Balls into Unlabeled Bins (Set Partitions)

In this case, the $n$ balls are individually distinct ($a, b, c$), but the $k$ bins are unlabeled identical containers.

Understanding Stirling Numbers of the Second Kind

Dividing $n$ distinct elements into non-empty, unlabeled subsets is called a Set Partition. The number of ways to partition a set of $n$ distinct elements into exactly $j$ non-empty unlabeled subsets is given by the Stirling Number of the Second Kind, denoted $S(n, j)$ or $\left\{ \begin{matrix} n \\ j \end{matrix} \right\}$.

If we have up to $k$ available unlabeled bins (meaning some bins can remain empty), we sum $S(n, j)$ over all possible numbers of non-empty bins $j$ from $1$ to $k$:

$$\text{Total Outcomes} = \sum_{j=1}^{k} S(n, j)$$

---

Case 4: Identical Balls into Unlabeled Bins (Integer Partitions)

In this final scenario, neither the balls nor the bins can be distinguished. Every ball looks identical, and every bin looks identical.

Understanding Integer Partitions

An integer partition of $n$ is a way of writing $n$ as a sum of positive integers, where the order of summands does not matter:

$$n = x_1 + x_2 + \dots + x_j \quad \text{with } x_1 \ge x_2 \ge \dots \ge x_j \ge 1 \quad \text{and } j \le k$$

The total number of outcomes is $p_{\le k}(n)$, the number of partitions of the integer $n$ into at most $k$ positive summands.

---

These four models form a subset of the broader Twelvefold Way classification. The matrix summarizes their formulas and the results for $n = 3$ balls and $k = 2$ bins.

How to Choose the Right Paradigm in Exam Problems

When solving counting problems, use this 2-step decision flowchart:

---

How Many Allocations Satisfy All Capacity Constraints?

Now that we understand how basic choices combine sequentially and additively, let's explore what happens when distribution problems involve capacity limits and bounds.

Suppose five identical supply packs must be distributed among three named stations: $A$, $B$, and $C$. Station $A$ requires at least one pack and can hold at most three; station $B$ can hold at most two; station $C$ requires at least one and can hold at most four. How many valid allocations are possible?

An allocation is completely described by its occupancy vector $(x_A, x_B, x_C)$, representing the number of packs assigned to each station. We seek the number of integer solutions to the system:

The stations are distinct, so $(1, 2, 2)$ and $(2, 1, 2)$ represent different physical allocations. However, because the supply packs are identical, exchanging two packs at the same or different stations does not yield a new outcome. If the packs instead possessed unique serial numbers, the vector $(1, 2, 2)$ would describe $30$ distinct labeled assignments!

---

Method 1: Exhaustive Case Enumeration (Case Analysis)

When the number of objects is small, partitioning the problem into mutually exclusive cases based on one variable is the most direct approach.

---

Method 2: Variable Shift (Pre-allocation for Lower Bounds)

Instead of manually listing cases, how can we solve this algebraically? Lower bounds like $x_A \ge 1$ and $x_C \ge 1$ require minimum allocations before any remaining supply is distributed. We handle this using a variable shift (pre-allocation):

1. Pre-allocate minimum required items: Give $1$ pack to station $A$ and $1$ pack to station $C$ immediately.
2. Define shifted non-negative variables: $$x_A' = x_A - 1 \ge 0, \qquad x_B' = x_B \ge 0, \qquad x_C' = x_C - 1 \ge 0$$
3. Reduce the total supply pool: Subtract the $2$ pre-allocated packs from $5$: $$x_A' + x_B' + x_C' = 5 - 1 - 1 = 3$$
4. Transform upper bounds: $$0 \le x_A' \le 2, \qquad 0 \le x_B' \le 2, \qquad 0 \le x_C' \le 3$$

---

Method 3: Upper Bounds via Inclusion-Exclusion (PIE)

Now that we have the simplified problem $x_A' + x_B' + x_C' = 3$ with non-negative integers ($x_i' \ge 0$), we can use Stars and Bars to count the total unconstrained solutions, then subtract invalid allocations that violate the upper capacity limits.

---

Method 4: Labeled Items & Multinomial Coefficient Weighting

What if the 5 supply packs are distinct / labeled (e.g., Pack #1, Pack #2, ..., Pack #5) rather than identical? While there remain only 8 valid occupancy vectors for bin counts, each vector expands into multiple distinct physical pack assignments.

The number of ways to assign $5$ distinct labeled items into bins of sizes $x_A, x_B, x_C$ is given by the multinomial coefficient:

---

Finite Probability Applications

A sample space $\Omega$ is the set of all possible outcomes of an experiment. An event $E \subseteq \Omega$ is a subset of outcomes. When $\Omega$ is finite and all outcomes are equally likely, the probability of event $E$ is:

General Hypergeometric Distribution: Sampling $r$ objects without replacement from a population of $N$ objects containing $K$ marked items yields exactly $j$ marked items with probability:

---

Occupancy Problems: Multinomial Distributions

When $n$ distinct balls choose $k$ labeled bins independently with probabilities $p_1, p_2, \dots, p_k$ (where $\sum p_i = 1$), the resulting random occupancy vector $(X_1, X_2, \dots, X_k)$ follows the multinomial distribution:

For uniform choices ($p_i = 1/k$), every specific assignment of distinct balls has probability $1/k^n$. However, different occupancy vectors possess different numbers of distinct ball assignments ($\frac{n!}{n_1! \cdots n_k!}$), meaning occupancy vectors are not equally likely!

---

Counting Binary Strings and Constrained Words

Binary strings—sequences formed exclusively from bits 0 and 1—are the foundational language of computer science, data compression, digital logic design, and error-correcting codes. Understanding how to count these strings under various structural rules is a core skill in combinatorics.

---

Fixed Weight Selection: The Compressed-Position Bijection

Suppose we fix the number of 1s in our string. The number of 1s in a binary string is called its weight ($r$). How many valid binary strings of length $n$ contain exactly $r$ ones such that no two ones are adjacent?

Why Does Compression Work? Step-by-Step Mechanics

In an unrestricted selection of $r$ positions out of $n$, any subset works ($\binom{n}{r}$). But when 1s cannot touch, each 1 after the first absorbs at least one mandatory zero spacer to its left.

1. The 1st one ($i_1$) requires 0 forced spacers before it: $z_1 = i_1 - 0$.
2. The 2nd one ($i_2$) requires at least 1 forced zero spacer between $i_1$ and $i_2$: $z_2 = i_2 - 1$.
3. The 3rd one ($i_3$) requires at least 2 cumulative forced zero spacers: $z_3 = i_3 - 2$.
4. The $r$-th one ($i_r$) requires at least $r-1$ cumulative forced zero spacers: $z_r = i_r - (r - 1)$.

By subtracting these mandatory spacer counts, we "collapse" or "compress" the array down by $r - 1$ slots. The original array of size $n$ shrinks down to an effective domain size of $n - (r - 1) = n - r + 1$.

---

Counting All Weights: The Fibonacci Recurrence

What if we do not fix the weight $r$, but instead want to count all binary strings of length $n$ that contain no adjacent 1s? Let $a_n$ denote this total count.

We can construct any valid length-$n$ string by considering its ending symbol:

Because these two cases are mutually exclusive and cover all possibilities, we obtain the famous Fibonacci recurrence:

---

Choose the Right Model for Balls, Bins, and Words