07 Advanced Counting Methods

Recognizing the Structure of a Counting Problem

Advanced counting becomes manageable when the same objects can be described through complementary viewpoints: selecting a subset, expanding a power, correcting overlaps, or building larger objects from smaller ones. The first step is to identify what is being counted and whether order, repetition, overlap, or local restrictions matter.

A useful decision process is:

1. Select a fixed number of distinct objects with order irrelevant: use a binomial coefficient.

2. Expand a power or extract one coefficient: use the binomial theorem.

3. Count objects satisfying at least one of several overlapping properties, or avoiding all listed restrictions: use inclusion-exclusion.

4. Construct objects by extending smaller valid objects: derive a recurrence relation.

5. Distribute identical units among distinguishable categories: consider stars-and-bars.

The central habit is to describe the objects in a way that prevents omission and overcounting.

Takeaway: Choose the method from the structure of the objects, not merely from the size of the numbers.

Selecting Objects and Distributing Repetitions

When choosing an unordered collection of $k$ objects from $n$ distinct objects, the number of choices is

The factorials account for all arrangements while the denominator removes the ordering of the selected and unselected objects. For example, a committee of three chosen from eight people has

possible memberships.

Two identities make computation and reasoning easier:

• Symmetry: $\binom{n}{k}=\binom{n}{n-k}$. Choosing what is included is equivalent to choosing what is left out.

• Pascal's identity: $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$. Separate selections according to whether a distinguished object is included.

Summing every possible subset size gives

because each of the $n$ elements is independently included or excluded.

When repetition is allowed, the situation changes. The number of ways to select $k$ objects from $n$ types is

For instance, the nonnegative integer solutions of $x_1+x_2+x_3=7$ number

Takeaway: Use ordinary binomial coefficients for distinct objects without order, and stars-and-bars when identical units may be repeated across distinguishable types.

Expanding Powers and Extracting Coefficients

The binomial theorem organizes the expansion of a power:

The coefficient appears because a term containing $k$ copies of $y$ is formed by choosing which $k$ of the $n$ factors contribute $y$; every remaining factor contributes $x$.

For example,

Coefficient extraction is often faster than full expansion. The coefficient of $x^5y^3$ in $(x+y)^8$ is

Two substitutions reveal important counting identities:

• Setting $x=y=1$ gives $2^n=\sum_{k=0}^{n}\binom{n}{k}$.

• Setting $x=1$ and $y=-1$ gives $\sum_{k=0}^{n}(-1)^k\binom{n}{k}=0$ for $n\ge 1$.

The second identity reflects cancellation between even-sized and odd-sized selections and is closely connected to inclusion-exclusion.

Takeaway: Match the requested monomial to the number of factors contributing one of its variables; the corresponding binomial coefficient is its coefficient.

Correcting Overlaps with Inclusion-Exclusion

The principle of inclusion-exclusion corrects the overcounting caused by overlaps. For two finite sets,

The intersection is subtracted because its elements were counted twice. For three sets, add the three individual counts, subtract the three pairwise intersections, and add the triple intersection.

In general,

To count objects that avoid every restriction, let $A_i$ be the objects violating restriction $i$. Then subtract their union from the whole set:

For example, among the integers from $1$ through $100$, the counts divisible by $2$, $3$, or $5$ are $50$, $33$, and $20$. Their pairwise intersection counts are $16$, $10$, and $6$, and the triple intersection count is $3$. Therefore,

A derangement is a permutation in which no object remains in its original position. If $D_n$ counts derangements of $n$ objects, inclusion-exclusion gives

Takeaway: List overlaps by intersection size and alternate signs: add singles, subtract pairs, add triples, and continue.

Building and Solving Recurrences

A recurrence relation is effective when valid objects can be partitioned into disjoint cases based on a first step, final step, or distinguished component. The cases must be exhaustive and disjoint, and the recurrence must be accompanied by initial conditions.

For binary strings of length $n$ with no consecutive $1$s, inspect the final digit. Strings ending in $0$ contribute $a_{n-1}$; strings ending in $1$ must have a preceding $0$, leaving $a_{n-2}$ possibilities. Thus,

For tilings of a $2\times n$ board with $2\times1$ dominoes, the leftmost portion is either one vertical domino or two horizontal dominoes. This gives

Some recurrences can be unrolled directly. If

then

For a second-order homogeneous recurrence, try $a_n=r^n$. The resulting characteristic equation determines the possible exponential terms. If the roots are distinct, the general form is

with constants fixed by the initial conditions. For the Fibonacci recurrence, the roots are

which leads to

For a nonhomogeneous recurrence such as $a_n=3a_{n-1}+2$, solve the associated homogeneous recurrence, find a particular solution, combine them, and then apply the initial condition. A constant particular solution satisfies $p=3p+2$, so $p=-1$, giving the general form $a_n=C3^n-1$.

Takeaway: First find a sound case split; only then perform the algebra needed to solve the resulting recurrence.