Advanced counting: selections with repetition, the binomial theorem and recurrence relations

Last week we counted selections without repetition. This week we allow repetition, see the binomial theorem, and learn to turn a problem into a recurrence relation. It is a final exam topic. Next week (solving linear recurrences) is the continuation. Golden rules:

1. The four-box table: does order matter, is there repetition? Choose one of the four formulas.
2. Combination with repetition = stars and bars. $r$ stars, $n - 1$ bars.
3. When finding a binomial coefficient, raise the numbers inside and the sign to the power as well.
4. When building a recurrence, look at the last step and always write the initial conditions.

The four-formula table

You are choosing $r$ items from $n$ types:

Example (order matters, repetition allowed): a word of length 5 from 26 letters, where letters may repeat: $26^5 = 11881376$.

Combinations with repetition: stars and bars

Example. A bakery has 4 kinds of pastry, and you will buy 6. You can take as many of each kind as you like, order does not matter. How many different purchases?

Write a purchase with 6 stars and 3 bars that separate the kinds:

**|*||***    ->  type1: 2, type2: 1, type3: 0, type4: 3
|******||    ->  type1: 0, type2: 6, type3: 0, type4: 0

Each purchase corresponds to choosing the positions of the 3 bars in a string of 9 characters (a one-to-one correspondence, a bijection):

$C(6 + 4 - 1, 3) = C(9, 3) = C(9, 6) = 84.$

Counting solutions of an equation

The nonnegative integer solutions of $x_1 + x_2 + x_3 = 11$: 11 stars, 2 bars, $C(13, 2) = 78$.

If each $x_i \ge 1$ is required: first put 1 in each box, leaving 8. $y_1 + y_2 + y_3 = 8$, $C(10, 2) = 45$.

The same model: distributing 8 identical balls into 4 different boxes is $C(8 + 3, 3) = C(11, 3) = 165$ ways.

One more example: distribute 10 identical candies to 3 children so that each child gets at least 2. First give each child 2 ($3 \cdot 2 = 6$ candies gone), and the remaining 4 candies are free: $y_1 + y_2 + y_3 = 4$, $C(4 + 2, 2) = C(6, 2) = 15$ ways. Every question with lower bounds finishes in these two steps: first hand out the mandatory share, then count the rest with stars and bars.

PITFALL · identical or distinct objects? Stars and bars works only for identical objects (the same balls, the same kind of pastry). If you throw 8 distinct balls into 4 boxes, each ball chooses one of the 4 boxes: $4^8$.

Words with repeated letters

If among $n$ objects $n_1$ are of one kind, $n_2$ of another kind, …, the number of distinct arrangements is

$\frac{n!}{n_1!\, n_2! \cdots n_k!}.$

BANANA: 6 letters, A three times, N twice, B once. $\frac{6!}{3!\,2!\,1!} = \frac{720}{12} = 60$. Why do we divide? Swapping the three A’s among themselves ($3!$) gives the same word, so we remove those repeats (the division rule).

The binomial theorem

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

Intuition: in the product $(x+y)(x+y)\cdots(x+y)$ you pick either $x$ or $y$ from each parenthesis. How many times the term $x^{n-j}y^j$ appears = the number of ways to choose the $j$ parentheses from which you pick $y$ = $\binom{n}{j}$.

Example: $(x + y)^4 = x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4$. The coefficients are 1, 4, 6, 4, 1.

Worked example. The coefficient of $x^3y^4$ in the expansion of $(2x - y)^7$.

General term: C(7, j) (2x)^(7-j) (-y)^j
For x^3 y^4, j = 4
C(7, 4) * 2^3 * (-1)^4 = 35 * 8 * 1 = 280

Two important results:

$\sum_{k=0}^{n}\binom{n}{k} = 2^n \quad (x = y = 1), \qquad \sum_{k=0}^{n}(-1)^k\binom{n}{k} = 0 \quad (x = 1,\ y = -1,\ n \ge 1).$

Example: $\binom{5}{0} + \dots + \binom{5}{5} = 1 + 5 + 10 + 10 + 5 + 1 = 32 = 2^5$.

Pascal’s identity and combinatorial proofs

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

Combinatorial proof: show that both sides count the same thing.

Proof. Let S be a set with n + 1 elements and fix one element a in S.
The left side counts the k-element subsets of S.
Such a subset either contains a or does not.
- If it contains a, choose the other k - 1 elements from the
  remaining n elements: C(n, k-1) ways.
- If it does not contain a, choose all k elements from the
  remaining n elements: C(n, k) ways.
By the sum rule the total is C(n, k-1) + C(n, k). ∎

Check: $\binom{6}{2} = 15$, $\binom{5}{1} + \binom{5}{2} = 5 + 10 = 15$. In Pascal’s triangle each number is the sum of the two numbers above it.

Generating permutations: lexicographic order

The permutation that comes after $a_1 a_2 \dots a_n$ in lexicographic order:

1. Going from right to left, find the first $j$ with $a_j < a_{j+1}$.
2. Among the elements to the right of $a_j$, find the smallest one greater than $a_j$ and swap it with $a_j$.
3. Arrange the part to the right of position $j$ in increasing order.

362541
From the right: 4 > 1, 5 > 4, 2 < 5  ->  a_j = 2
To the right of 2: 5 4 1, the smallest greater than 2 = 4
Swap: 364521
Sort the right of 4 increasing: 1 2 5  ->  364125

Recurrence relations

A recurrence relation expresses the term $a_n$ of a sequence in terms of earlier terms. Without initial conditions the sequence is not determined.

Example 1 (interest). 1000 TL at 5% annual interest: $P_n = 1.05\,P_{n-1}$, $P_0 = 1000$. After three years, $P_3 = 1000 \cdot 1.05^3 = 1157.625$.

Example 2 (Tower of Hanoi). To move $n$ disks: move the top $n-1$ disks to the spare peg ($H_{n-1}$), move the largest (1), move the $n-1$ disks on top of it ($H_{n-1}$):

$H_n = 2H_{n-1} + 1, \qquad H_1 = 1.$

By iteration $1, 3, 7, 15, 31, 63$: the guess is $H_n = 2^n - 1$. Its proof by induction (the template of week 3):

Claim. H_n = 2^n - 1 for all integers n >= 1.
Basis step. n = 1: H_1 = 1 and 2^1 - 1 = 1. True.
Inductive step. Assume H_k = 2^k - 1 for some k >= 1 (IH).
Then H_(k+1) = 2 H_k + 1 = 2(2^k - 1) + 1 = 2^(k+1) - 2 + 1 = 2^(k+1) - 1.
So the claim holds for k + 1.
By mathematical induction, H_n = 2^n - 1 for all n >= 1. ∎

Example 3 (bit strings). $a_n$: the number of bit strings of length $n$ that do not contain two consecutive 0s. Look at the last bit:

• Last bit 1: the part before it is any valid string of length $n-1$, $a_{n-1}$.
• Last bit 0: the bit before it must be 1, and the part before that is a valid string of length $n-2$, $a_{n-2}$.

$a_n = a_{n-1} + a_{n-2}, \qquad a_1 = 2,\ a_2 = 3.$

The values are $2, 3, 5, 8, 13, 21$: the Fibonacci sequence, shifted.

TIP · the “look at the last step” recipe. When building a recurrence, split into cases by the last element of the sequence (the last bit, the last disk moved, the last digit). In each case the remaining part is the same problem, only shorter. Add up the cases.

Common mistakes