Chapter 5 — Front Matter
Purpose and Overview
Chapter 4 introduced combinations and showed that \(\binom{n}{k}\) counts the number of ways to choose \(k\) objects from a set of \(n\) objects without regard to order. That was a counting idea. This chapter reveals something deeper: binomial coefficients are not only combinatorial tools. They appear naturally inside algebra, inside patterns, inside probability, and inside proofs. When you expand the expression \((x + y)^n\), the coefficients that emerge are exactly the numbers \(\binom{n}{0}, \binom{n}{1}, \binom{n}{2}, \ldots, \binom{n}{n}\). This is not a coincidence. It is a structural fact about how choices work.
This chapter builds the algebraic and combinatorial theory of binomial coefficients systematically. You will study Pascal's Triangle, its patterns, its symmetry, and its recursive structure. You will prove the central identities that connect these numbers. You will learn the Binomial Theorem, both as an algebraic fact and as a combinatorial statement. You will see how specific terms in an expansion can be extracted, how binomial coefficients appear in probability models, and how they bridge counting to algebra in ways that will carry forward into every later part of this textbook.
Opening Question
Suppose you need to expand the expression \((x + y)^6\). You could expand it by repeated multiplication, carefully distributing terms six times in succession. That would work, but it would take considerable effort and leave plenty of room for errors. Is there a pattern in how these expansions grow? Are the coefficients predictable? Can you find the coefficient of \(x^4 y^2\) in \((x + y)^6\) without expanding the whole expression? The answer is yes, and the reason connects directly to the counting ideas you studied in Chapter 4.
14Sections
10Objectives
9Key Terms
12+Worked Examples
Why This Chapter Matters
Binomial coefficients appear across mathematics, probability, computer science, and data science more frequently than almost any other family of numbers. They describe how many ways subsets can be chosen. They describe the probabilities of outcomes in repeated experiments. They appear in algebraic identities used in algorithm analysis. They are the foundation of Pascal's Triangle — one of the most studied arrays in mathematics — and they connect to recurrence relations, generating functions, combinatorial proof, and advanced discrete mathematics. Chapter 5 is a turning point in this textbook: it shows that counting and algebra describe the same structures from different perspectives.
Learning Objectives
- 1Construct Pascal's Triangle and identify its entries as binomial coefficients.
- 2Recognize and apply the symmetry property \(\binom{n}{k} = \binom{n}{n-k}\).
- 3State and prove Pascal's Identity algebraically and combinatorially.
- 4Compute and interpret row sums and alternating sums.
- 5State and apply the Binomial Theorem to expand \((x + y)^n\).
- 6Find specific terms in a binomial expansion without expanding the full expression.
- 7Interpret binomial coefficients as counts of choices within an expansion.
- 8Apply binomial coefficients to basic probability problems with repeated independent trials.
- 9Identify common mistakes in working with binomial coefficients and expansions.
- 10Recognize how binomial coefficients connect to recurrence relations, generating functions, and combinatorial proof.
Key Terms
Binomial coefficient
The number \(\binom{n}{k}\), equal to the number of ways to choose \(k\) objects from \(n\) distinct objects without repetition and without regard to order.
Pascal's Triangle
A triangular arrangement of numbers where each entry equals the sum of the two entries directly above it; row \(n\) contains \(\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}\).
Pascal's Identity
The recursive identity \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\), giving the structural rule of Pascal's Triangle.
Row sum
The sum of all entries in row \(n\) of Pascal's Triangle, equal to \(2^n\). Counts all subsets of an \(n\)-element set.
Alternating sum
The sum \(\sum_{k=0}^n (-1)^k \binom{n}{k}\), equal to \(0\) for \(n \geq 1\). Follows from the Binomial Theorem with \(x=1, y=-1\).
Binomial Theorem
The identity \((x+y)^n = \sum_{k=0}^n \binom{n}{k} x^{n-k} y^k\), expressing binomial expansion using binomial coefficients.
General term
The term \(T_{k+1} = \binom{n}{k} x^{n-k} y^k\) in the expansion of \((x+y)^n\), corresponding to choosing \(y\) exactly \(k\) times.
Binomial distribution
A probability model for \(n\) independent trials each with success probability \(p\); the probability of exactly \(k\) successes is \(\binom{n}{k}p^k(1-p)^{n-k}\).
Symmetry property
The identity \(\binom{n}{k} = \binom{n}{n-k}\): choosing \(k\) objects to include is equivalent to choosing \(n-k\) objects to exclude.
Sections 5.1 – 5.7
Pascal's Triangle, Symmetry, and the Core Identities
Why Binomial Coefficients Matter · Pascal's Triangle · Patterns · Symmetry · Pascal's Identity · Row Sums · Alternating Sums
Section 5.1
Why Binomial Coefficients Matter
Before proceeding to Pascal's Triangle and the Binomial Theorem, it is worth pausing to understand why binomial coefficients deserve a full chapter of their own. After all, Chapter 4 already defined them as combination numbers. What more is there to say?
The answer is that \(\binom{n}{k}\) turns out to be one of the most versatile objects in discrete mathematics. It is not just a formula. It is a number that appears in several different contexts and carries meaning in all of them. Understanding binomial coefficients well means understanding those connections.
| Connection | What It Means | Where It Appears |
|---|
| Algebra | The coefficient of \(x^{n-k}y^k\) in \((x+y)^n\) is exactly \(\binom{n}{k}\) | Binomial Theorem (Sec 5.8) |
| Pascal's Triangle | The recursive structure \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\) | Pascal's Identity (Sec 5.5) |
| Sets and counting | Total subsets of an \(n\)-element set equals \(2^n\), the row sum | Row Sums (Sec 5.6) |
| Probability | Counts ways to arrange \(k\) successes in \(n\) independent trials | Binomial Distribution (Sec 5.12) |
| Proof | Many identities have both algebraic and combinatorial proofs | Identities (Sec 5.5, Ch 9) |
Central Idea
These five connections make binomial coefficients worth studying in depth. They are a unifying thread in combinatorics — a single family of numbers that carries counting meaning, algebraic meaning, probabilistic meaning, and proof meaning simultaneously.
Section 5.2
Pascal's Triangle
Pascal's Triangle is a way of arranging all binomial coefficients in a triangular grid. Each row of the triangle corresponds to a value of \(n\), and the entries in that row are the binomial coefficients \(\binom{n}{0}, \binom{n}{1}, \binom{n}{2}, \ldots, \binom{n}{n}\). The defining property is that each interior entry equals the sum of the two entries directly above it — one to the left and one to the right. Entries on the left and right edges are always 1.
Row 01
Row 111
Row 2121
Row 31331
Row 414641
Row 515101051
Row 61615201561
Each highlighted entry equals the sum of the two entries directly above it
Verification — The Additive Property
The entry 6 in row 4 is \(\binom{4}{2} = 6 = \binom{3}{1} + \binom{3}{2} = 3 + 3\). ✓
The entry 10 in row 5 is \(\binom{5}{2} = 10 = \binom{4}{1} + \binom{4}{2} = 4 + 6\). ✓
The entry 20 in row 6 is \(\binom{6}{3} = 20 = \binom{5}{2} + \binom{5}{3} = 10 + 10\). ✓
Building Pascal's Triangle Without Formulas
Start with a 1 at the top. Place 1s along both edges. Fill each interior entry by adding the two entries directly above it. This works for any row without computing a single factorial — a practical advantage for small values of \(n\).
For large values of \(n\), the formula \(\binom{n}{k} = \dfrac{n!}{k!(n-k)!}\) is necessary. Computing row 30 by hand would be impractical without it.
Section 5.3
Patterns in Pascal's Triangle
| Pattern | Description | Example |
|---|
| Edge entries | Left and right edges are always 1: \(\binom{n}{0} = \binom{n}{n} = 1\) | Every row begins and ends with 1 |
| Natural numbers | Second column: \(\binom{n}{1} = n\) | Row 7, position 1: \(\binom{7}{1} = 7\) |
| Triangular numbers | Third column: \(\binom{n}{2} = \frac{n(n-1)}{2}\) | 1, 3, 6, 10, 15, 21, … |
| Hockey-Stick | Diagonal sum equals the entry below and one right | \(\binom{2}{2}+\binom{3}{2}+\binom{4}{2}+\binom{5}{2} = \binom{6}{3} = 20\) |
| Row sums | Sum of row \(n\) equals \(2^n\) | Row 5: \(1+5+10+10+5+1 = 32 = 2^5\) |
| Powers of 11 | Rows read as integers give \(11^n\) (for single-digit rows) | Row 3 → \(1331 = 11^3\) |
| Fibonacci diagonals | Shallow diagonal sums give Fibonacci numbers | 1, 1, 2, 3, 5, 8, 13, 21, … |
Hockey-Stick Identity — Preview
The Hockey-Stick Identity \(\displaystyle\binom{r}{r} + \binom{r+1}{r} + \binom{r+2}{r} + \cdots + \binom{n}{r} = \binom{n+1}{r+1}\) will be proved in Chapter 9 as a worked example of combinatorial identity proof. For now, verify it in the triangle: sum any diagonal and compare to the entry at the "handle" of the hockey stick.
Section 5.4
Symmetry of Binomial Coefficients
Symmetry Property
\[\binom{n}{k} = \binom{n}{n-k}\]
Choosing \(k\) objects to include from \(n\) gives the same count as choosing \(n-k\) objects to exclude.
Algebraic Proof
\(\displaystyle\binom{n}{n-k} = \frac{n!}{(n-k)!\,k!} = \frac{n!}{k!\,(n-k)!} = \binom{n}{k}\). The factorials in the denominator are the same; only their order is swapped. Division is commutative, so the values are equal.
∎
Combinatorial Proof
Every time you choose \(k\) objects to include in a selection, you simultaneously decide which \(n-k\) objects to exclude. There is a perfect one-to-one correspondence between selections of size \(k\) and selections of size \(n-k\). Choosing the included objects is equivalent to choosing the excluded objects. The two counts must therefore be equal.
∎
Practical Value of Symmetry
Instead of computing \(\binom{50}{47}\) — which would require \(47!\) in the denominator — use symmetry: \(\binom{50}{47} = \binom{50}{3} = \dfrac{50 \cdot 49 \cdot 48}{6} = 19600\). Always compute whichever version has the smaller lower index.
Example 5.4.1
Using symmetry to simplify computation
- ProblemCompute \(\binom{100}{97}\).
- ThinkApplying the formula directly requires computing \(97!\). Instead, apply symmetry to reduce the work.
- Represent\(\binom{100}{97} = \binom{100}{100-97} = \binom{100}{3}\).
- Count
\[\binom{100}{3} = \frac{100 \cdot 99 \cdot 98}{3!} = \frac{970200}{6} = 161700\]
- CheckThis counts the number of ways to choose 3 items from 100, which is equivalent to choosing which 97 items to include and which 3 to leave out. Symmetry confirmed.
- InterpretThere are 161,700 ways to choose 97 items from 100 — the same as the number of ways to choose which 3 items to exclude.
Answer: \(\binom{100}{97} = 161{,}700\)
Section 5.5
Pascal's Identity
Pascal's Identity
\[\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\]
For all integers \(n \geq 1\) and \(1 \leq k \leq n-1\), with boundary conditions \(\binom{n}{0} = \binom{n}{n} = 1\).
Algebraic Proof
Algebraic Proof of Pascal's Identity
We show \(\binom{n-1}{k-1} + \binom{n-1}{k} = \binom{n}{k}\).
\[\binom{n-1}{k-1} + \binom{n-1}{k} = \frac{(n-1)!}{(k-1)!(n-k)!} + \frac{(n-1)!}{k!(n-1-k)!}\]
Use the common denominator \(k!(n-k)!\), noting \(k! = k\cdot(k-1)!\) and \((n-k)! = (n-k)(n-k-1)!\):
\[\frac{k(n-1)!}{k!(n-k)!} + \frac{(n-k)(n-1)!}{k!(n-k)!} = \frac{(n-1)!(k+n-k)}{k!(n-k)!} = \frac{n!}{k!(n-k)!} = \binom{n}{k}\]
∎
Combinatorial Proof
Combinatorial Proof of Pascal's Identity
The left side counts the number of ways to choose \(k\) objects from the set \(\{1, 2, 3, \ldots, n\}\). Single out the element \(n\) as special. Every selection of \(k\) objects either includes \(n\) or does not — these cases are mutually exclusive and exhaustive.
Case 1 — Includes \(n\): The remaining \(k-1\) objects must be chosen from \(\{1, 2, \ldots, n-1\}\). There are \(\binom{n-1}{k-1}\) ways to do this.
Case 2 — Excludes \(n\): All \(k\) objects must be chosen from \(\{1, 2, \ldots, n-1\}\). There are \(\binom{n-1}{k}\) ways to do this.
Since every selection falls into exactly one case, the total is \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\).
∎
Key Technique — Singling Out One Element
The combinatorial proof uses the technique of singling out one special element of the set and splitting all selections into two mutually exclusive cases based on whether that element is included. This technique — element isolation — is one of the most common and powerful in combinatorial proof. You will see it again in Chapter 9.
Example 5.5.1
Applying Pascal's Identity
- ProblemCompute \(\binom{8}{3}\) without using the formula directly, given \(\binom{7}{2} = 21\) and \(\binom{7}{3} = 35\).
- ThinkPascal's Identity says \(\binom{8}{3} = \binom{7}{2} + \binom{7}{3}\).
- Count\(\binom{8}{3} = 21 + 35 = 56\).
- CheckUsing the formula: \(\dfrac{8 \cdot 7 \cdot 6}{6} = \dfrac{336}{6} = 56\). ✓
Answer: \(\binom{8}{3} = 56\)
Section 5.6
Row Sums
Row Sum Identity
\[\binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \cdots + \binom{n}{n} = 2^n\]
Combinatorial Proof
A set \(S\) with \(n\) elements has exactly \(\binom{n}{k}\) subsets of size \(k\). Summing over all \(k\) from 0 to \(n\) gives the total number of subsets of \(S\). Since each element can independently be included or excluded, there are \(2^n\) total subsets.
∎
Algebraic Proof — Binomial Theorem
The Binomial Theorem (Section 5.8) gives \((x+y)^n = \sum_{k=0}^n \binom{n}{k} x^{n-k}y^k\). Set \(x = y = 1\):
\[(1+1)^n = \sum_{k=0}^n \binom{n}{k} \cdot 1^{n-k} \cdot 1^k = \sum_{k=0}^n \binom{n}{k}\]
Since \(2^n = (1+1)^n\), the row sum equals \(2^n\).
∎
| Row \(n\) | Row entries | Row Sum | \(2^n\) |
|---|
| 0 | 1 | 1 | 1 |
| 1 | 1 1 | 2 | 2 |
| 2 | 1 2 1 | 4 | 4 |
| 3 | 1 3 3 1 | 8 | 8 |
| 4 | 1 4 6 4 1 | 16 | 16 |
| 5 | 1 5 10 10 5 1 | 32 | 32 |
| 6 | 1 6 15 20 15 6 1 | 64 | 64 |
Example 5.6.1
Row sums and subsets
- ProblemA set has 5 elements. How many subsets does it have in total? Verify using the row sum formula and by listing all subset sizes.
- Count
\[\binom{5}{0} + \binom{5}{1} + \binom{5}{2} + \binom{5}{3} + \binom{5}{4} + \binom{5}{5} = 1 + 5 + 10 + 10 + 5 + 1 = 32\]
Also: \(2^5 = 32\).
- CheckBoth methods agree. The 32 subsets include 1 empty subset, 5 singletons, 10 pairs, 10 triples, 5 four-element sets, and 1 full set.
- InterpretThe binomial coefficients in row 5 partition the 32 subsets by size. The row sum formula counts all of them at once.
Answer: A 5-element set has 32 total subsets.
Section 5.7
Alternating Sums
Alternating Sum Identity
\[\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0 \quad \text{for } n \geq 1\]
Equivalently: \(\binom{n}{0} - \binom{n}{1} + \binom{n}{2} - \binom{n}{3} + \cdots = 0\).
Proof via the Binomial Theorem
Apply the Binomial Theorem with \(x = 1\) and \(y = -1\):
\[(1 + (-1))^n = \sum_{k=0}^{n} \binom{n}{k}(1)^{n-k}(-1)^k = \sum_{k=0}^{n} (-1)^k \binom{n}{k}\]
Since \((1-1)^n = 0^n = 0\) for \(n \geq 1\), the alternating sum equals 0.
∎
Combinatorial Meaning
An alternating sum of zero means the number of even-size subsets of an \(n\)-element set equals the number of odd-size subsets (for \(n \geq 1\)). Each count is \(2^{n-1}\).
Verification — Row 4
\(\binom{4}{0} - \binom{4}{1} + \binom{4}{2} - \binom{4}{3} + \binom{4}{4} = 1 - 4 + 6 - 4 + 1 = 0\) ✓
Boundary Case: n = 0
When \(n = 0\), the only term is \(\binom{0}{0} = 1\), so the alternating sum is 1, not 0. The formula \(0^n = 0\) does not apply when \(n = 0\) (since \(0^0 = 1\) by convention). Always note this boundary case when applying the identity.
Sections 5.8 – 5.11
The Binomial Theorem and Algebraic Expansion
The Binomial Theorem · Expanding Binomials · Finding Specific Terms · Combinatorial Meanings
Section 5.8
The Binomial Theorem
The Binomial Theorem
For any non-negative integer \(n\) and any values \(x\) and \(y\):
\[(x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k\]
Writing out the terms explicitly:
\[(x + y)^n = \binom{n}{0}x^n + \binom{n}{1}x^{n-1}y + \binom{n}{2}x^{n-2}y^2 + \cdots + \binom{n}{n-1}xy^{n-1} + \binom{n}{n}y^n\]
Combinatorial Reasoning — Why the Theorem Is True
When expanding \((x + y)^n = (x+y)(x+y)\cdots(x+y)\) (\(n\) factors), each term in the product is formed by choosing either \(x\) or \(y\) from each factor, then multiplying those choices together.
If you choose \(y\) from exactly \(k\) of the \(n\) factors and \(x\) from the remaining \(n-k\) factors, you get the product \(x^{n-k}y^k\). The number of ways to make this choice is exactly \(\binom{n}{k}\) — you are choosing which \(k\) of the \(n\) factors contribute \(y\).
Summing over all \(k\) from 0 to \(n\) gives the complete expansion. The binomial coefficients are literally counting choices — they are not separate from the combinatorics, they arise directly from it.
∎
Example 5.8.1
Expanding a binomial using the theorem
- ProblemExpand \((x + y)^4\) using the Binomial Theorem.
- ThinkApply the formula with \(n = 4\). There will be five terms, corresponding to \(k = 0, 1, 2, 3, 4\).
- Count
| \(k\) | \(\binom{4}{k}\) | Term |
|---|
| 0 | 1 | \(x^4\) |
| 1 | 4 | \(4x^3y\) |
| 2 | 6 | \(6x^2y^2\) |
| 3 | 4 | \(4xy^3\) |
| 4 | 1 | \(y^4\) |
\[(x+y)^4 = x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4\]
- CheckCoefficients \(1, 4, 6, 4, 1\) are row 4 of Pascal's Triangle. Sum: \(1+4+6+4+1 = 16 = 2^4\). ✓
- InterpretThe coefficient of each term counts the number of ways to choose \(y\) from that many of the four factors. For \(x^2y^2\): choose which 2 of the 4 factors give \(y\) — that is \(\binom{4}{2} = 6\).
Answer: \((x+y)^4 = x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4\)
Example 5.8.2
Binomial with constants
- ProblemExpand \((2a + 3b)^3\).
- ThinkApply the theorem with \(x = 2a\), \(y = 3b\), \(n = 3\). Each term will involve powers of \(2a\) and \(3b\).
- Count
k=0: \(\binom{3}{0}(2a)^3(3b)^0 = 1 \cdot 8a^3 \cdot 1 = 8a^3\)
k=1: \(\binom{3}{1}(2a)^2(3b)^1 = 3 \cdot 4a^2 \cdot 3b = 36a^2b\)
k=2: \(\binom{3}{2}(2a)^1(3b)^2 = 3 \cdot 2a \cdot 9b^2 = 54ab^2\)
k=3: \(\binom{3}{3}(2a)^0(3b)^3 = 1 \cdot 1 \cdot 27b^3 = 27b^3\)
- CheckSet \(a = b = 1\): \(8 + 36 + 54 + 27 = 125 = 5^3 = (2+3)^3\). ✓
Answer: \((2a+3b)^3 = 8a^3 + 36a^2b + 54ab^2 + 27b^3\)
Section 5.9
Expanding Binomials
Expanding \((x - y)^n\). Write \((x-y)^n = (x + (-y))^n\) and apply the Binomial Theorem with \(y\) replaced by \(-y\):
\[(x - y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} (-y)^k = \sum_{k=0}^{n} (-1)^k \binom{n}{k} x^{n-k} y^k\]
The signs alternate: positive when \(k\) is even, negative when \(k\) is odd.
Example 5.9.1
Expanding a difference
- ProblemExpand \((a - b)^5\).
- ThinkUse row 5 of Pascal's Triangle \((1, 5, 10, 10, 5, 1)\) with alternating signs.
- Count\[(a-b)^5 = a^5 - 5a^4b + 10a^3b^2 - 10a^2b^3 + 5ab^4 - b^5\]
- CheckSet \(a = b = 1\): \((1-1)^5 = 0\); and \(1 - 5 + 10 - 10 + 5 - 1 = 0\). ✓
Answer: \(a^5 - 5a^4b + 10a^3b^2 - 10a^2b^3 + 5ab^4 - b^5\)
Example 5.9.2
Binomial with a fraction
- ProblemExpand \(\left(x + \dfrac{1}{x}\right)^4\).
- ThinkApply the theorem with \(y = 1/x\) and \(n = 4\). The general term is \(\binom{4}{k} x^{4-k} \cdot x^{-k} = \binom{4}{k} x^{4-2k}\).
- Count
| \(k\) | Coefficient | Power of \(x\) | Term |
|---|
| 0 | 1 | \(x^4\) | \(x^4\) |
| 1 | 4 | \(x^2\) | \(4x^2\) |
| 2 | 6 | \(x^0 = 1\) | \(6\) |
| 3 | 4 | \(x^{-2}\) | \(\dfrac{4}{x^2}\) |
| 4 | 1 | \(x^{-4}\) | \(\dfrac{1}{x^4}\) |
Answer: \(\left(x + \dfrac{1}{x}\right)^4 = x^4 + 4x^2 + 6 + \dfrac{4}{x^2} + \dfrac{1}{x^4}\)
Section 5.10
Finding Specific Terms
In many problems, you do not need the entire expansion. You only need a single term. The key is the general term formula.
General Term Formula
In the expansion of \((x + y)^n\), the term corresponding to index \(k\) is:
\(T_{k+1} = \binom{n}{k} x^{n-k} y^k\)
To find a specific term: identify the power of \(x\) or \(y\) you need, set up the exponent equation, and solve for \(k\).
Example 5.10.1
Finding a specific coefficient
- ProblemFind the coefficient of \(x^3 y^5\) in the expansion of \((x + y)^8\).
- ThinkThe power of \(y\) in the \(k\)-th term is \(k\). Set \(k = 5\) to get \(y^5\).
- Count\[T_6 = \binom{8}{5}x^{8-5}y^5 = \binom{8}{5}x^3y^5\]
\[\binom{8}{5} = \binom{8}{3} = \frac{8 \cdot 7 \cdot 6}{6} = 56\]
- CheckPowers: \(3 + 5 = 8 = n\). ✓ Symmetry used: \(\binom{8}{5} = \binom{8}{3}\). ✓
- InterpretThe coefficient 56 counts the number of ways to choose \(y\) from exactly 5 of the 8 factors in \((x+y)^8\).
Answer: The coefficient of \(x^3y^5\) is \(\mathbf{56}\).
Example 5.10.2
Finding a specific term with constants
- ProblemFind the term containing \(a^4\) in the expansion of \((2a - 3)^7\).
- ThinkGeneral term of \((2a+(-3))^7\) is \(\binom{7}{k}(2a)^{7-k}(-3)^k\). Set \(7-k = 4\) to get \(a^4\), so \(k = 3\).
- Count\[T_4 = \binom{7}{3}(2a)^4(-3)^3 = 35 \cdot 16a^4 \cdot (-27) = -15120\,a^4\]
- Check\(\binom{7}{3} = 35\), \(2^4 = 16\), \((-3)^3 = -27\), \(35 \times 16 = 560\), \(560 \times (-27) = -15120\). ✓
Answer: The term is \(-15120\,a^4\).
Example 5.10.3
Finding the constant term
- ProblemFind the constant term in the expansion of \(\left(3x - \dfrac{2}{x^2}\right)^9\).
- ThinkGeneral term: \(\binom{9}{k}(3x)^{9-k}\!\left(-\dfrac{2}{x^2}\right)^{\!k} = \binom{9}{k}\cdot 3^{9-k}\cdot(-2)^k \cdot x^{9-k-2k} = \binom{9}{k}\cdot 3^{9-k}\cdot(-2)^k \cdot x^{9-3k}\).
- RepresentFor the constant term, set the exponent of \(x\) to zero: \(9 - 3k = 0 \Rightarrow k = 3\).
- Count\[T_4 = \binom{9}{3}\cdot 3^6 \cdot (-2)^3 = 84 \cdot 729 \cdot (-8) = -489{,}888\]
- Check\(\binom{9}{3} = 84\); \(3^6 = 729\); \((-2)^3 = -8\); \(84 \times 729 = 61236\); \(61236 \times (-8) = -489888\). ✓
Answer: The constant term is \(-489{,}888\).
Section 5.11
Combinatorial Meanings of Coefficients
The Binomial Theorem is usually taught as an algebraic expansion rule, but its coefficients carry combinatorial meaning that deserves explicit attention. Each connection below deepens the relationship between counting and algebra.
| Interpretation | What \(\binom{n}{k}\) Counts |
|---|
| Choosing from factors | The number of ways to choose \(y\) exactly \(k\) times from the \(n\) factors of \((x+y)^n\) |
| Grid paths | The number of paths from the bottom-left to the top-right of an \(m \times n\) grid moving only right or up: \(\binom{m+n}{n}\) |
| Committee selection | The number of size-\(k\) committees chosen from \(n\) people; if each person is a factor \((x+y)\), the coefficient of \(y^k\) counts all size-\(k\) committees |
| Paths in Pascal's Triangle | The number of paths from the apex to entry \(\binom{n}{k}\), moving left-down or right-down at each step — explains Pascal's Identity geometrically |
Grid Path Formula
A path from the bottom-left to the top-right of an \(m \times n\) grid that moves only right (R) or up (U) consists of a sequence of \(m\) R-steps and \(n\) U-steps. The number of such paths is \(\binom{m+n}{n}\): choose which \(n\) of the \(m+n\) steps are upward moves. This interpretation appears again in Chapter 6 (Stars and Bars) and Chapter 11 (Generating Functions).
Sections 5.12 – 5.14
Probability, Common Mistakes, and the Road Ahead
Binomial Probability · Eight Common Mistakes · Preparing for Chapter 6
Section 5.12
Binomial Coefficients in Probability
Many real-world situations can be modeled as a sequence of independent trials in which each trial has exactly two outcomes: success or failure. The probability of success on each trial is some fixed value \(p\), and the probability of failure is \(1-p\). Such a sequence of \(n\) independent trials is called a binomial experiment.
Binomial Probability Formula
In a binomial experiment with \(n\) independent trials, each with success probability \(p\), the probability of obtaining exactly \(k\) successes is:
\[P(X = k) = \binom{n}{k}\, p^k\, (1-p)^{n-k}\]
Why the Formula Is Correct
A specific sequence of exactly \(k\) successes and \(n-k\) failures has probability \(p^k(1-p)^{n-k}\), because the trials are independent and probabilities multiply. The successes can occur in any \(k\) of the \(n\) trials. The number of sequences with exactly \(k\) successes is \(\binom{n}{k}\). Multiplying gives the total probability for exactly \(k\) successes.
∎
Example 5.12.1
Binomial probability — fair coin
- ProblemA fair coin is flipped 6 times. What is the probability of getting exactly 4 heads?
- ThinkBinomial experiment: \(n = 6\), \(p = 1/2\), \(k = 4\).
- Count
\[P(X = 4) = \binom{6}{4}\left(\frac{1}{2}\right)^4\left(\frac{1}{2}\right)^2 = \binom{6}{4} \cdot \frac{1}{64}\]
\[\binom{6}{4} = \binom{6}{2} = \frac{6 \cdot 5}{2} = 15\]
\[P(X = 4) = \frac{15}{64}\]
- CheckTotal probability over all outcomes: \(\sum_{k=0}^6 \binom{6}{k}(1/2)^6 = 2^6/2^6 = 1\). ✓
- InterpretThe probability of exactly 4 heads in 6 fair coin flips is \(\dfrac{15}{64} \approx 23.4\%\).
Answer: \(P(X = 4) = \dfrac{15}{64} \approx 0.234\)
Example 5.12.2
Binomial probability — unequal probabilities
- ProblemA basketball player makes 70% of free throw attempts. She shoots 5 free throws. What is the probability she makes exactly 3?
- ThinkBinomial experiment: \(n = 5\), \(p = 0.7\), \(k = 3\).
- Count
\[P(X = 3) = \binom{5}{3}(0.7)^3(0.3)^2 = 10 \times 0.343 \times 0.09 = 10 \times 0.03087 \approx 0.309\]
- InterpretThe probability of exactly 3 successful free throws is approximately 30.9%.
Answer: \(P(X = 3) \approx 0.309\)
MGU Library Connection
- Probability and Statistics, Chapter 5: Binomial random variables, expected value, variance, and the relationship between binomial and normal distributions
- Probability and Statistics, Chapter 6: Applications of the binomial distribution to quality control, genetics, and clinical trials
- MGU Dictionary: binomial experiment, success probability, binomial distribution, expected value
- Data Science Foundations: binomial sampling, simulation, and statistical inference
Section 5.13
Common Binomial Coefficient Mistakes
Mistake 1 — Confusing \(\binom{n}{k}\) with \(\dfrac{n}{k}\)
\(\binom{6}{2} = 3\)
Correct: \(\binom{6}{2} = \dfrac{6!}{2!\,4!} = \dfrac{6 \times 5}{2} = 15\). The notation \(\binom{n}{k}\) is not division — it is a three-step computation.
Always apply the formula or use the multiplicative shortcut \(\dfrac{n(n-1)\cdots(n-k+1)}{k!}\).
Mistake 2 — Forgetting that \(\binom{n}{0} = 1\) and \(\binom{n}{n} = 1\)
Skipping the first and last terms in a binomial expansion
Correct: The expansion of \((x+y)^n\) has exactly \(n+1\) terms, from \(k = 0\) to \(k = n\). The first term is \(x^n\) (coefficient 1) and the last is \(y^n\) (coefficient 1). Always include both.
Mistake 3 — Mishandling signs in \((x - y)^n\)
\((a-b)^3 = a^3 - 3a^2b + 3ab^2 + b^3\)
Correct: \((a-b)^3 = a^3 - 3a^2b + 3ab^2 - b^3\). The sign of term \(k\) is \((-1)^k\), so signs alternate. The last term is \(-b^3\) because \(k = 3\) is odd.
Write \((x-y)^n = (x+(-y))^n\) and track each power of \(-y\) carefully.
Mistake 4 — Misidentifying the index for "the \(r\)-th term"
For "the 4th term," setting \(k = 4\)
Correct: The \((k+1)\)-th term corresponds to index \(k\). So the 4th term is \(k = 3\): \(T_4 = \binom{n}{3}x^{n-3}y^3\).
The index \(k\) starts at 0, making the first term \(T_1\) correspond to \(k = 0\). When the problem says "4th term," subtract 1 to get \(k\).
Mistake 5 — Forgetting to raise constants to the appropriate power
In \((2a+3b)^4\), writing the \(k=2\) term as \(\binom{4}{2}a^2b^2 = 6a^2b^2\)
Correct: \(\binom{4}{2}(2a)^2(3b)^2 = 6 \cdot 4a^2 \cdot 9b^2 = 216a^2b^2\). Always raise the full expression — including constants — to its power.
Mistake 6 — Memorizing row sums without understanding the derivation
Students who memorize "row sum is \(2^n\)" but cannot adapt when asked for weighted or partial sums
Correct approach: Know that the row sum identity follows from substituting \(x = y = 1\) in the Binomial Theorem, and that the alternating sum follows from \(x = 1\), \(y = -1\). Understanding the derivation lets you handle other substitutions.
Mistake 7 — Applying symmetry incorrectly
\(\binom{n}{k} = \binom{k}{n-k}\)
Correct symmetry: \(\binom{n}{k} = \binom{n}{n-k}\). Both lower indices must sum to \(n\). The upper index stays fixed. The incorrect version changes the upper index, which is wrong.
Mistake 8 — Confusing Pascal's Identity with the sum rule
Writing \(\binom{n}{k} + \binom{n}{j} = \binom{m}{r}\) for arbitrary indices
Correct: Pascal's Identity is \(\binom{n-1}{k-1} + \binom{n-1}{k} = \binom{n}{k}\). The top index increases by exactly 1 on the right side. The two terms on the left always have the same top index \((n-1)\), not arbitrary values.
Section 5.14
Preparing for Counting with Repetition
Chapter 5 has built a thorough algebraic and combinatorial theory of binomial coefficients. The connections established here — between counting, Pascal's Triangle, algebraic expansion, probability, and proof — will appear in every subsequent chapter of this textbook.
Chapter 6 introduces a new problem type: counting selections when repetition is allowed. In Chapters 3 and 4, every object was counted at most once. But many real counting situations allow the same object to be chosen more than once. How many ways can you distribute identical objects into distinct containers? How many nonnegative integer solutions does the equation \(x_1 + x_2 + x_3 = 10\) have? These are distribution and repetition problems.
The main technique for Chapter 6 is called Stars and Bars. It translates these problems into counting the placements of dividers between groups of identical objects. The solution turns out to involve binomial coefficients again: the number of ways to choose \(k\) items from \(n\) types with repetition is \(\binom{n+k-1}{k}\). The theory you built in Chapter 5 carries directly forward.
Bridge to Chapter 6
Students who understand why \(\binom{n}{k}\) counts what it counts, and who can read Pascal's Triangle fluently, will find Stars and Bars much more accessible. The stars-and-bars formula \(\binom{n+k-1}{k}\) is itself a binomial coefficient, and the argument for why it is correct mirrors the combinatorial reasoning developed in Sections 5.5 and 5.11 of this chapter.
Chapter 5 — Back Matter
Chapter Summary
- Sec 5.1Binomial coefficients connect algebra, Pascal's Triangle, sets, probability, and proof. They are a unifying object in discrete mathematics.
- Sec 5.2Pascal's Triangle is a triangular array with \(\binom{n}{k}\) in row \(n\), position \(k\). Each entry is the sum of the two entries directly above. The triangle can be built row-by-row without formulas.
- Sec 5.3Patterns include: edge entries of 1, natural numbers in column 1, triangular numbers in column 2, the Hockey-Stick Identity, powers-of-2 row sums, and Fibonacci numbers along diagonals.
- Sec 5.4Symmetry: \(\binom{n}{k} = \binom{n}{n-k}\). Proved algebraically and by complement-selection argument. Rows of Pascal's Triangle are palindromes. Use symmetry to simplify large computations.
- Sec 5.5Pascal's Identity: \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\). Proved algebraically by combining fractions; proved combinatorially by singling out one element and splitting selections into two cases.
- Sec 5.6Row sum: \(\sum_{k=0}^n \binom{n}{k} = 2^n\). Proved by counting all subsets of an \(n\)-element set, and by setting \(x = y = 1\) in the Binomial Theorem.
- Sec 5.7Alternating sum: \(\sum_{k=0}^n (-1)^k \binom{n}{k} = 0\) for \(n \geq 1\). Follows from the Binomial Theorem with \(x = 1\), \(y = -1\). Means equal counts of even- and odd-size subsets.
- Sec 5.8Binomial Theorem: \((x+y)^n = \sum_{k=0}^n \binom{n}{k}x^{n-k}y^k\). The coefficient \(\binom{n}{k}\) counts the ways to choose \(y\) exactly \(k\) times from the \(n\) factors. This is the combinatorial reason the theorem holds.
- Sec 5.9Expanding \((x-y)^n\) produces alternating signs via \((-y)^k = (-1)^k y^k\). Handle fractions and other substitutions by identifying \(x\) and \(y\) carefully before applying the general term formula.
- Sec 5.10General term: \(T_{k+1} = \binom{n}{k}x^{n-k}y^k\). To find a specific term, match exponents to determine \(k\). The term index begins at \(k = 0\), making the first term \(T_1\).
- Sec 5.11Combinatorial meanings: \(\binom{n}{k}\) counts choices from factors, paths on grids (using \(\binom{m+n}{n}\)), committee selections, and paths in Pascal's Triangle.
- Sec 5.12Binomial probability: \(P(X=k) = \binom{n}{k}p^k(1-p)^{n-k}\). The binomial coefficient counts the number of sequences with exactly \(k\) successes; the probability factor accounts for each such sequence's likelihood.
- Sec 5.13Eight common mistakes: misreading \(\binom{n}{k}\) as division, dropping edge terms, sign errors in \((x-y)^n\), off-by-one term indexing, omitting constants from powers, over-memorizing identities, misapplying symmetry, and misusing Pascal's Identity.
- Sec 5.14Chapter 6 introduces repetition counting. Stars and Bars gives \(\binom{n+k-1}{k}\) — itself a binomial coefficient — for the number of ways to choose \(k\) items from \(n\) types with repetition.
Key Terms Review
| Term | Brief Description |
|---|
| Binomial coefficient \(\binom{n}{k}\) | Number of size-\(k\) selections from \(n\) objects; coefficient in binomial expansion |
| Pascal's Triangle | Triangular array of binomial coefficients; each entry equals the sum of the two above it |
| Symmetry property | \(\binom{n}{k} = \binom{n}{n-k}\) |
| Pascal's Identity | \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\) |
| Row sum | Sum of row \(n\) equals \(2^n\) |
| Alternating sum | \(\sum_{k=0}^n (-1)^k \binom{n}{k} = 0\) for \(n \geq 1\) |
| Binomial Theorem | \((x+y)^n = \sum_{k=0}^n \binom{n}{k} x^{n-k} y^k\) |
| General term | \(T_{k+1} = \binom{n}{k} x^{n-k} y^k\) |
| Binomial distribution | \(P(X=k) = \binom{n}{k}p^k(1-p)^{n-k}\) |
Concept Review Questions
- What does the entry in row 5, position 3 of Pascal's Triangle represent? What is its value?
- Explain in your own words why \(\binom{n}{k} = \binom{n}{n-k}\). Give a counting interpretation, not just an algebraic one.
- State Pascal's Identity. What does each term on the right side count?
- Why does the sum of all entries in row \(n\) of Pascal's Triangle equal \(2^n\)?
- What happens when you substitute \(x = 1\) and \(y = -1\) into the Binomial Theorem? What identity does this produce?
- In the Binomial Theorem, where does the coefficient \(\binom{n}{k}\) come from? Explain using the idea of choosing from \(n\) factors.
- Explain why the binomial probability formula \(\binom{n}{k}p^k(1-p)^{n-k}\) is a product of two parts: a binomial coefficient and a probability.
- How does the alternating sum identity connect to the subset-counting interpretation of row sums?
- What is the relationship between Pascal's Triangle and counting paths on a grid?
- How does Pascal's Identity follow from the combinatorial proof? What technique does that proof use?
- Write out rows 0 through 7 of Pascal's Triangle.
- Using Pascal's Triangle (not the formula), find \(\binom{7}{3}\) and \(\binom{7}{4}\). Verify they are equal.
- Add rows 0 through 6 of Pascal's Triangle. Do the row sums follow the pattern \(2^n\)?
- Find all entries in Pascal's Triangle that equal 10. In which rows and positions do they appear?
- Build Pascal's Triangle through row 10 using only the addition rule (no formulas). Compute the row sum of row 9 and verify it equals \(2^9 = 512\).
- Identify the alternating sum of row 6 and verify it equals 0.
- Show that the sum of entries at even positions in row 6 (positions 0, 2, 4, 6) equals the sum at odd positions. What common value do both equal?
Compute without Pascal's Triangle (use the formula or symmetry).
- \(\binom{10}{3}\)
- \(\binom{12}{5}\)
- \(\binom{15}{13}\)
- \(\binom{20}{1}\)
- \(\binom{50}{2}\)
- \(\binom{100}{98}\)
- \(\binom{30}{28}\)
- \(\binom{200}{197}\)
- Use Pascal's Identity to compute \(\binom{9}{4}\) given \(\binom{8}{3} = 56\) and \(\binom{8}{4} = 70\).
- Verify Pascal's Identity for \(n = 7\), \(k = 3\) by computing all three binomial coefficients directly.
- For how many values of \(k\) does \(\binom{12}{k} > 100\)? List those values.
- Find all values of \(n\) such that \(\binom{n}{2} = 45\).
Expand completely using the Binomial Theorem.
- \((x + y)^5\)
- \((a + b)^6\)
- \((x - y)^4\)
- \((1 + x)^7\)
- \((2x + 1)^4\)
- \((x - 2y)^5\)
- \((3a + b)^3\)
- \(\left(x + \dfrac{1}{2}\right)^4\)
Without expanding fully, find the indicated term.
- Coefficient of \(x^3\) in \((x+2)^6\)
- Coefficient of \(a^2b^4\) in \((a+b)^6\)
- Third term of \((x+y)^9\)
- Constant term of \(\left(x^2 - \dfrac{1}{x}\right)^6\)
- Coefficient of \(x^4\) in \((2x-3)^7\)
- Term with \(y^3\) in \((4-y)^5\)
- Verify the row sum identity for \(n = 5\) by direct computation: \(\sum_{k=0}^5 \binom{5}{k} = 2^5\).
- Verify the alternating sum identity for \(n = 5\): \(\sum_{k=0}^5 (-1)^k \binom{5}{k} = 0\).
- Verify the identity \(\sum_{k=0}^5 \binom{5}{k}^2 = \binom{10}{5}\) by direct computation. *(Vandermonde's Identity in a special case — preview of Chapter 9.)*
- Prove algebraically that \(\binom{n}{k} = \binom{n}{n-k}\).
- Give a combinatorial proof of the identity \(\binom{n}{1} = n\). Explain in words why both sides count the same thing.
- Give a combinatorial proof of \(\sum_{k=0}^n \binom{n}{k} = 2^n\) using the subset interpretation.
- (Proof preview) Explain why \(k\binom{n}{k} = n\binom{n-1}{k-1}\) should be true, then verify for \(n = 5\), \(k = 3\). Hint: think about choosing a committee of size \(k\) from \(n\) people, then singling out one member as chair.
- Quality testing. A batch of 10 items contains 3 defective ones. A quality inspector selects 4 items at random. How many ways can the sample contain exactly 1 defective item? Exactly 2 defective items?
- Sports. A basketball player makes 60% of her three-point attempts. She takes 8 three-point shots. Find the probability she makes exactly 5. Find the probability she makes at least 7.
- Binary codes. A binary string of length 8 is a sequence of 0s and 1s. How many binary strings of length 8 contain exactly five 1s? Explain the connection to binomial coefficients.
- Expansion and evaluation. Expand \((1.02)^6 = (1 + 0.02)^6\) approximately, keeping the first four terms. Compare to the exact value \(1.02^6 \approx 1.12616\).
- Grid paths. A grid has 4 columns and 3 rows. How many paths are there from the bottom-left corner to the top-right corner, moving only right or up? Interpret your answer as a binomial coefficient.
- Committee design. A school council has 10 members: 6 seniors and 4 juniors. A subcommittee of 4 members is to be formed. How many subcommittees contain exactly 2 seniors and 2 juniors? How many contain at least 3 seniors?
Error Analysis
Each problem contains an error. Identify it, explain what went wrong, and provide the correct solution.
Problem 1
Expand \((x-y)^3\).
Student answer: \(x^3 - 3x^2y + 3xy^2 + y^3\)
What is wrong with the final term?
Problem 2
Find the coefficient of \(x^4\) in \((x+3)^6\).
Student: "General term is \(\binom{6}{k}x^k \cdot 3^{6-k}\). Set \(k = 4\): \(\binom{6}{4} \cdot 3^2 = 15 \cdot 9 = 135\)."
The student set up the general term incorrectly. What is the correct setup and answer?
Problem 3
Compute \(\binom{10}{7}\).
Student: "\(\binom{10}{7} = \dfrac{10}{7} \approx 1.43\)"
Identify the fundamental misunderstanding and give the correct value.
Problem 4
Use Pascal's Identity to find \(\binom{9}{4}\).
Student: "\(\binom{9}{4} = \binom{8}{3} + \binom{8}{5}\)"
Is this correct? What does the correct identity say? Verify by computing all values.
Problem 5
Find the row sum of row 8.
Student answer: \(8 \cdot 2^7 = 1024\)
What is wrong? What is the correct answer?
Chapter 5 Checkpoint
Chapter 5 Checkpoint
Complete without assistance — assesses all key skills and concepts from Chapter 5
Part A — Short Computation
- Write the entry in row 8, position 3 of Pascal's Triangle using binomial coefficient notation. Compute its value.
- Use the symmetry property to simplify and compute \(\binom{200}{198}\).
- Expand \((x+y)^4\) completely using the Binomial Theorem.
- Find the coefficient of \(x^3y^4\) in \((x+y)^7\).
- Find the constant term in the expansion of \(\left(2x + \dfrac{3}{x}\right)^6\).
Part B — Reasoning and Explanation
- Give two different proofs of Pascal's Identity: one algebraic and one combinatorial.
- Explain in words why the sum of row \(n\) of Pascal's Triangle equals the number of subsets of an \(n\)-element set.
- A friend claims \(\binom{12}{9} = \binom{9}{3}\). Are they correct? Explain.
Part C — Application
- A student takes a 10-question true-false quiz and guesses randomly on every question. Each answer has a 50% chance of being correct.
- (a) What is the probability of getting exactly 7 correct?
- (b) What is the probability of getting at least 9 correct?
- A database query returns 8 items. An analyst wants to choose exactly 3 for detailed review. In how many ways can this be done? Write your answer as a binomial coefficient and evaluate it.
Part D — Proof and Extension
- Prove that \(\binom{2n}{2} = 2\binom{n}{2} + n^2\) by expanding both sides algebraically. Then give a combinatorial interpretation of each side.
- (Extension) Consider the identity \(\displaystyle\sum_{k=0}^{n}\binom{n}{k}^2 = \binom{2n}{n}\). Verify this for \(n = 4\). What might the right side count?
Answers may be placed in the answer key.
Looking Ahead
Chapter 6: Counting with Repetition and Distribution Problems
Chapter 5 developed the algebraic and combinatorial theory of binomial coefficients. Chapter 6 introduces a new counting context: what happens when repetition is allowed? Permutations and combinations assumed each object can appear at most once in a selection or arrangement. But many real situations allow repeated choices — choosing ice cream flavors when you can pick the same flavor twice, distributing identical balls into distinct boxes, or counting nonnegative integer solutions to an equation. The main technique is Stars and Bars, which translates repetition problems into separator-placement problems — and whose solution formula is, once again, a binomial coefficient.
MGU Library Connection
- Binomial Coefficient Reference — Appendix C of this textbook
- Pascal's Triangle Reference — Appendix G of this textbook
- Binomial Theorem Reference — Appendix H of this textbook
- Discrete Mathematics, Chapter 6: Counting and Combinatorics — reviews combinations and introduces generating functions
- Probability and Statistics, Chapter 5: Binomial random variables, expected value, and variance
- Chapter 9 of this textbook: Combinatorial Identities and Proof — proves Vandermonde's Identity, Hockey-Stick Identity, and others previewed here
- MGU Dictionary entries: binomial coefficient, Pascal's Triangle, Pascal's Identity, Binomial Theorem, binomial distribution