4. Binomial expansions, Pascal paths, and Catalan numbers

The preceding notes developed combinations, multinomial coefficients, lattice paths, and stars and bars as counting models. A new problem rarely announces which model it needs, so we begin by comparing four similar-looking choices whose outcomes are very different.

Then, we will see how the coefficients appear in many surprising circumstances: in expansions of polynomials, in Pascal’s triangle, and recursive lattice-path counts. Finally, imposing restrictions on those paths leads to hard counting problem. A famous one is that of the Catalan numbers and the reflection principle that counts them. These numbers also appear in counting ways to parenthesise expressions.

After studying these notes, you will be able to do the following.

• Decide which kind of choice describes a problem by determining whether order matters and whether repetition is allowed.

• Model combinations with repetition as multiplicity vectors and count them.

• Explain the relationship among stars and bars, cumulative totals, weakly increasing sequences, and strictly increasing sequences.

• Translate lower bounds for integer solutions so that stars and bars applies.

• Use the binomial and multinomial theorems to extract coefficients from powers of polynomials.

• Verify Pascal’s recurrence algebraically and prove it combinatorially.

• Compute lattice-path counts recursively and count paths that pass through or avoid a specified point.

• Use tail reflection to derive the Catalan-number formula and relate Catalan paths to balanced-parenthesis strings.

4.1 A bakery problem: four kinds of choice

A bakery sells ten types of doughnuts. A manager wants to buy six doughnuts for six employees. Four different purchasing scenarios will help us compare the available models.

Problem 1 (Buying doughnuts for six employees)

Which standard kind of choice describes each scenario?

1. The manager decides which type of doughnut to buy for each employee and may choose the same type for several employees.

2. The manager again chooses one type for each employee, but decides not to buy the same type twice.

3. The manager selects six different types and lets the employees decide who receives which one.

4. The manager buys six doughnuts to bring to the employees. Several doughnuts may have the same type, and the manager does not assign them to particular employees.

4.1.1 Modeling the four scenarios

The important question is not only whether the manager purchases six doughnuts. We must ask what information one outcome retains.

1. In the first scenario, the employees play the role of six labeled positions. For each employee, the manager chooses one of ten types and may repeat the same type. An outcome is a length- string of doughnut types, or equivalently a function from the employees to the types. The number of choices is .

2. The employees are still labeled, so assigning glazed to Alice and chocolate to Bob is different from assigning chocolate to Alice and glazed to Bob. Repetition is now forbidden. This is a -permutation of the ten types, and the number of choices is .

3. The manager selects the six types before any employee receives one. Order and employee assignments are not part of the purchase, and the manager repeats no type. This is an ordinary combination, with possible selections.

4. Order and employee assignments are again irrelevant, but repetition is allowed. The manager might buy six glazed doughnuts, six different types, or anything in between. This is a combination with repetition, and the number of choices is .

The four scenarios occupy the four rows of the familiar choice table: In this table, is the number of available types and is the number of objects selected. The bakery story shows why the wording of the problem is not enough by itself: the mathematical model depends on what counts as a different outcome.

4.2 Combinations with repetition and cumulative totals

Let us return to the fourth bakery scenario. If is the number of doughnuts of type , then a nonnegative integer solution describes a purchase: More generally, selecting objects from types with repetition is the same problem as finding the nonnegative integer solutions of

4.2.1 The separator count

The stars-and-bars construction places stars in a row and uses separators to divide them among the types. There are positions altogether. Choosing the separator positions gives solutions. Choosing the star positions instead gives the equal expression Thus the six-doughnut purchase in the fourth scenario can be made in ways.

Can we explain this count using another combinatorial encoding? Yes. We can record the separator positions as cumulative totals.

4.2.2 Cumulative totals and weakly increasing sequences

A sequence is weakly increasing if each term is at least the preceding term: It is strictly increasing if each inequality is strict: Repeated values are allowed in a weakly increasing sequence but not in a strictly increasing sequence.

For a nonnegative solution of , we define Since every is nonnegative, The number records how many stars appear before separator . Two separators may have the same number of stars before them, which is why the sequence is only weakly increasing. The final total is forced, so we omit it from the encoding.

This construction is reversible. If numbers satisfy , then we recover Thus solutions of are in bijection with weakly increasing sequences of length selected from Such a sequence is a choice with repetition of elements from possible values. Applying the combination-with-repetition formula with these roles exchanged gives exactly as in the separator count.

Example 2 (Encoding the separators by cumulative totals)

The solution of gives In a stars-and-bars string, the three separators occur after , , and stars. Conversely, the differences recover .

4.2.3 An alternative proof of the combinations with repetitions formula

We already know that the number of nonnegative integer solutions of is . We obtained this answer by arranging stars and separators. Let us now obtain the same answer in a different way, using an ordinary combination.

An ordinary combination is a choice of distinct elements from a set. Thus our plan is to encode each solution as a subset. The cumulative totals from the preceding section almost do this, but they are only weakly increasing: two consecutive totals can be equal when some is zero. To make the totals strictly increasing, we first make every part positive.

Theorem 3 (Combinations with repetition, revisited)

The number of nonnegative integer solutions of is Equivalently, this is the number of ways to select objects from types when repetition is allowed.

Proof

We start with a nonnegative solution and define We have added one to each of the variables, so More importantly, every is positive. This guarantees that the partial sums increase at every step.

Next, we record the first partial sums: Since each is at least , these numbers satisfy The final inequality holds because at least must remain for . We have therefore obtained an ordinary -element subset

We must check that this encoding does not lose any information. For any -element subset of , we write its elements in increasing order: We recover the positive integers by taking consecutive differences: Every one of these numbers is positive. Moreover, their sum telescopes: Finally, we define . The resulting are nonnegative, and their sum is , so they form a solution of the original equation.

The two constructions undo one another. We have therefore established a bijection between the solutions of and the -element subsets of . The number of such subsets is

Example 4 (Following one solution through the bijection)

Let us follow the earlier solution of . Adding to each entry gives whose sum is . The first three partial sums are Thus the solution corresponds to the three-element subset of .

Starting with , consecutive differences recover which gives . Subtracting from each entry returns the original solution .

Remark 5 (From weakly increasing to strictly increasing)

There is a direct connection between this proof and the weakly increasing sequence from the preceding section. We had Since , the new partial sums satisfy Thus we turn a weakly increasing sequence into a strictly increasing one by adding to its first term, to its second term, and so on: Subtracting from the th term reverses the transformation. Therefore is equivalent to

4.2.4 Solutions with lower bounds

Stars and bars applies directly when every variable may be any nonnegative integer. If a variable must instead satisfy , reserve its required amount first. The part still available for distribution is then counted with nonnegative variables.

Theorem 6 (Integer solutions with lower bounds)

For integers , the number of integer solutions to is when . If that difference is negative, there are no solutions.

Proof

We set . Then , and the original equation becomes The substitution is reversible: from a solution in the , recover . Stars and bars applied to the transformed equation gives the formula.

Example 7 (Asymmetric lower bounds)

How many integer solutions satisfy

Solution: We define The new variables are nonnegative and satisfy Therefore the number of solutions is

Warning (Lower bounds and upper bounds behave differently)

The method we saw allows us to map an integer solution problem with a lower bound (for example ) to a problem of counting non-negative integer solutions. This method does not work if we have upper bound conditions, for example .

We can still solve the problem when there is an upper bound condition on only one variable, by using the subtraction principle. However, with several upper bounds, such as and will require us to use the inclusion–exclusion principle.

4.2.5 Summary

• The number of nonnegative integer solutions of is

• If the variables have lower bounds , we subtract the lower bounds first. The remaining total is .

• Cumulative totals encode a solution as a weakly increasing sequence. Adding to its th term converts it into a strictly increasing sequence, which is the same as an ordinary subset.

4.3 The binomial theorem

Let us consider the product We obtain every raw term in its expansion by choosing either or from each factor. To obtain , exactly of the factors must contribute ; all other factors contribute . The coefficient is therefore the number of ways to choose those factors.

Theorem 8 (Binomial theorem)

For every nonnegative integer ,

Proof

Label the factors by their positions. The subset of positions from which we choose determines a term. If that subset has size , the resulting term is . There are such subsets. Grouping the raw terms by gives the displayed expansion.

For example, row of the binomial coefficients gives

The same reasoning works when the two terms have numerical weights.

Example 9 (Extracting a weighted coefficient)

What is the coefficient of in ?

Solution: To obtain , we choose from exactly four of the seven factors and choose from the remaining three. The coefficient is The binomial coefficient chooses the contributing factors; the powers and record the numerical contribution from those choices.

Example 10 (Accounting for an outside power)

What is the coefficient of in ?

Solution: The outside factor already contributes , so we need from . We choose from six factors. The coefficient is

Two useful identities follow immediately from the binomial theorem. Setting gives which also counts all subsets of an -element set by their sizes. For , setting and gives Equivalently, the sum of the even-indexed entries in row equals the sum of the odd-indexed entries.

4.4 The multinomial theorem

When every factor offers choices rather than two, a multinomial coefficient counts the multiplicities of the choices.

Theorem 11 (Multinomial theorem)

For every integer and every nonnegative integer , where the sum ranges over all nonnegative integer solutions of .

Proof

We choose one term from each of the labeled factors. A raw term equals exactly when the resulting choice string contains copies of for every . The number of such strings is Grouping equal raw terms proves the formula.

Example 12 (A multinomial coefficient with weights)

What is the coefficient of in ?

Solution: The exponents sum to , so the requested term can occur. We choose the two factors contributing , the three contributing , and the one contributing . The coefficient is

Before we compute a multinomial coefficient, we check the total degree. For example, the coefficient of in is zero because the requested exponents sum to , while every term in the expansion has total degree .

Remark 13 (How many distinct monomials appear?)

A nonnegative solution of determines a monomial in . Stars and bars shows that the number of distinct monomials is .

4.5 Pascal’s recurrence and Pascal’s triangle

The factorial formula is not the only way to compute binomial coefficients. A local counting argument relates each interior entry to two entries in the preceding row.

Theorem 14 (Pascal’s recurrence)

If and , then The boundary values are .

Algebraic verification

Using the factorial formula and a common denominator,

Combinatorial proof

For an -element set with a distinguished element , we partition the -element subsets of into two classes.

If a subset does not contain , we choose all elements from the remaining elements, giving possibilities. If it contains , we choose its other elements from the remaining , giving possibilities. The two classes are disjoint and exhaustive, so the sum rule gives the recurrence.

Starting with the boundary entries and using the recurrence produces Pascal’s triangle: We obtain entry by adding the two entries immediately above it. The symmetry is visible in the triangle and corresponds to choosing the included elements or, equivalently, the omitted elements.

4.6 Recursive lattice-path counts

For nonnegative integers and , we write for the number of northeast lattice paths from to . If , a path reaches either from by a right step or from by an up step. These cases are disjoint, so Along the axes there is only one path, so . These are the same recurrence and boundary data as Pascal’s triangle. Therefore in agreement with the step-string argument from the preceding notes.

We can use the recurrence to fill an entire grid. We begin with along the coordinate axes. At every interior vertex, we add the labels at the vertex to its left and the vertex below it.

Figure 1 shows this computation near the point .

Figure 1: A recursive table of northeast-path counts. The highlighted point can be reached from in ways and from in ways, so its label is .

This table is a rotated portion of Pascal’s triangle. It also suggests a way to handle forbidden vertices when no direct formula is available: we assign a forbidden vertex the value zero, then continue filling the table by the same left-plus-below rule.

4.6.1 Paths through a specified point

For and , a path from to that passes through decomposes uniquely into a path from to followed by a path from to . The product rule gives The total number of paths to is , so the number avoiding is

Example 15 (Passing through or avoiding )

A path from to that passes through consists of a path with four right and seven up steps, followed by a path with six right and three up steps. Thus the number passing through the point is There are paths altogether, so the number avoiding is

Warning 16 (Feasibility of the specified point)

The product formula assumes that is coordinatewise between the start and endpoint. A northeast path from to cannot pass through a point with a negative coordinate, an -coordinate greater than , or a -coordinate greater than .

4.7 Catalan paths and the reflection principle

There are northeast paths from to . We now impose a global restriction: at every point of the path, require In other words, the path may touch the diagonal , but it may never go above it. A path satisfying this restriction is called a Catalan path or a Dyck path.

Definition 17 (Catalan numbers)

The th Catalan number is the number of northeast lattice paths from to that never go above the line . We include the empty path, so .

For , Figure 2 displays all five paths that obey the diagonal restriction.

Figure 2: The five Catalan paths for . The corresponding step strings and balanced-parenthesis strings are displayed below the paths.

To count the valid paths, we subtract the paths that cross the diagonal. The reflection principle gives a bijective count of those bad paths.

Figure 3 previews the transformation: reflection leaves the path unchanged until its first crossing and reflects the remaining tail.

Figure 3: Reflecting the tail after the first crossing changes a bad path to into a path to . The construction is reversible.

Theorem 18 (Catalan formula)

For every nonnegative integer ,

Proof

For , the one path is empty, and both displayed expressions equal . Now assume . A bad path has a first point at which it reaches the line . We keep the path unchanged up to that point and reflect the tail—the portion from the first crossing to the endpoint—across the line . The crossing point lies on the reflecting line and therefore stays fixed. On the tail, reflection exchanges right steps and up steps.

Reflection across sends a point to . In particular, it sends the original endpoint to . The resulting path therefore goes from to .

This map is reversible. Any northeast path from to must reach the line . We keep its prefix through the first point on that line and reflect its tail across the line. This produces a bad path to , and reflecting the same tail again recovers the original path. Thus bad paths to are in bijection with all paths to . There are such paths. Subtracting them from all paths gives the first formula. Finally, so the difference is .

The first Catalan numbers are For , the five Catalan step strings are

4.7.1 Balanced-parenthesis strings

We replace every right step by a left parenthesis and every up step by a right parenthesis. A path ends at exactly when the string contains parentheses of each kind. The condition says that every initial segment contains at least as many left parentheses as right parentheses. This is exactly the condition for a balanced-parenthesis string.

Hence also counts balanced strings of pairs of parentheses. For example, the five paths above correspond to Conversely, replacing each left parenthesis by and each right parenthesis by recovers a unique Catalan path. The two replacements undo one another, so this correspondence is a bijection. This is an important combinatorial lesson: a named sequence is usually useful because it counts many families of objects, not only because it has a closed formula.

Remark 19 (A recurrence to revisit later)

A first-return decomposition of a nonempty Catalan path gives A later note on combinatorial recurrences will develop this nonlinear recurrence. For now, the reflection argument supplies the closed formula.

Problem (Practice)

How many northeast paths from to never go above ? How many go above the diagonal at least once? Which count comes from subtraction, and which comes from the reflection bijection?

4.8 Summary of the counting connections

The main formulas in these notes arise from a small number of reversible encodings and counting rules:

In each case, the formula becomes easier to remember after identifying the objects behind it: shifted sequences, translated integer vectors, choices from labeled factors, subsets split by a distinguished element, concatenated paths, or reflected paths.

4.9 Further reading

The course resources page links to the books used as references for these notes. Applied Combinatorics, Sections 2.5–2.7, covers lattice paths and binomial and multinomial expansions. Counting Rocks!, Sections 4.1–4.3 and 4.5–4.6, covers Pascal’s recurrence, binomial identities, and multinomial counting. Discrete Mathematics: An Open Introduction, Sections 3.1–3.2, presents coefficient and lattice-path interpretations. Combinatorics Through Guided Discovery, Section 1.3.1, also discusses Catalan paths and the reflection principle.