Which arrangement or distribution model do I need?
The decision path from a new problem's shape to one of Chapter 2's six models.
Reach for this whenever a problem asks to arrange, distribute, or select with possible repetition, and no single Discrete Mathematics I formula obviously fits. Work the questions in order: symmetry first, then repetition, then whether identical objects are being distributed, then whether a path-like restriction is present.
Step 1 — does the arrangement have circular or reflective symmetry?
Example
A rotation of the same order counts as identical -- divide out rotation alone.
Term
necklace
Example
Both rotation AND flipping count as identical -- divide out rotation, then flipping.
Step 2 — are repeated items being arranged in a row?
Example
Some items are identical copies, arranged in a fixed-length row.
Step 3 — are identical objects being distributed into bins?
Example
Order among the bins matters (they are labeled); the number of bins is fixed.
Example
The number of parts itself varies, and every part must be positive.
Check the full four-case taxonomy when it is unclear whether the objects or bins are identical or distinct.
Step 4 — is there a path-like restriction?
Example
No restriction beyond moving right or up.
Example
The path (or an equivalent structure, like balanced parentheses) may never cross a boundary.
Formulas this decision path leads to
The number of distinct ways to arrange n distinct items around a circle, where arrangements that differ only by rotation count as the same, is (n-1)!.
Show proof
Line the n items up in a row first: there are n! such arrangements. Bending any one row into a circle produces exactly n different rows that land on the same circular arrangement — one for each rotation of which item is "first." So every circular arrangement is counted n times among the n! linear ones, and dividing removes the overcount: \frac{n!}{n} = (n-1)!. Equivalently: fix one item's seat to remove rotational symmetry, then arrange the other n-1 items in the remaining seats in any order.
The number of distinct arrangements of n objects, where one kind of object repeats n_1 times, another kind repeats n_2 times, and so on through n_k groups of indistinguishable objects (with n_1 + n_2 + \cdots + n_k = n), is \frac{n!}{n_1!\, n_2! \cdots n_k!}.
Show proof
Start from n!, the count if every one of the n objects were secretly distinct (as if each carried its own invisible label). Within that count, every group of n_1 identical objects can be relabeled among themselves in n_1! ways without changing the arrangement anyone can actually see — so n! overcounts the first repeated group by a factor of n_1!. The same overcounting happens independently for the second group (factor n_2!), the third, and so on. Dividing n! by n_1!\, n_2! \cdots n_k! removes every one of those redundant relabelings at once, since the groups' internal shufflings are independent of each other.
The number of ways to distribute n identical items into k labeled bins (some bins may be empty) is \binom{n+k-1}{k-1}.
Show proof
Represent the n items as n stars in a row. Splitting them into k bins is the same as choosing where to place k-1 dividing bars among the stars — everything before the first bar goes in bin 1, everything between the first and second bar goes in bin 2, and so on. The row now has n stars and k-1 bars, n+k-1 symbols in total, and a distribution is completely determined by which k-1 of those n+k-1 positions hold bars. That is exactly \binom{n+k-1}{k-1} choices.
To count the solutions of x_1+x_2+\cdots+x_k=n in integers with each x_i \geq m_i for given minimums m_i, substitute y_i = x_i - m_i \geq 0 and count nonnegative solutions of y_1+y_2+\cdots+y_k = n-\sum_{i=1}^k m_i by ordinary stars and bars.
Show proof
The substitution y_i = x_i - m_i is a bijection between solutions with x_i \geq m_i and solutions with y_i \geq 0: adding m_i back to each y_i recovers a unique x_i, and every valid x_i \geq m_i comes from exactly one y_i \geq 0. Summing the shifted equation confirms the new total is n - \sum m_i, so the shifted count is the ordinary stars-and-bars count applied to that smaller total.
The number of ways to write a positive integer n as an ordered sum of positive integers (a composition of n) is 2^{n-1}.
Show proof
Picture n as a row of n dots with n-1 gaps between consecutive dots. A composition of n corresponds exactly to a choice of which gaps become dividers, splitting the row into parts — insert a divider or don't, independently, at each of the n-1 gaps. By the product rule there are 2^{n-1} such choices, and each yields a distinct ordered sequence of positive part sizes summing to n.
Formula
Lattice Path Count
The number of monotone lattice paths from (0,0) to (m,n) using only unit steps right and up is \binom{m+n}{m}.
Show proof
Every such path is a sequence of m+n steps, each either right (R) or up (U), containing exactly m R's and n U's. A path is completely determined by choosing which m of the m+n step positions are R's — the rest are forced to be U's. That is exactly \binom{m+n}{m} choices.
Formula
The Catalan Numbers
The nth Catalan number, counting the monotone lattice paths from (0,0) to (n,n) that never rise above the diagonal y=x, is C_n = \frac{1}{n+1}\binom{2n}{n}.
Show proof
Every unrestricted monotone path from (0,0) to (n,n) that crosses above the diagonal touches the line y=x+1 at some first step. Reflecting the portion of the path up to that first touch across y=x+1 gives a bijection between paths that cross the diagonal and unrestricted monotone paths from (-1,1) to (n,n), of which there are \binom{2n}{n-1}. Subtracting the crossing paths from all \binom{2n}{n} paths gives C_n = \binom{2n}{n} - \binom{2n}{n-1} = \binom{2n}{n}\left(1-\frac{n}{n+1}\right) = \frac{1}{n+1}\binom{2n}{n}.