Pascal's triangle — combinatorial interpretation: Exercises

Quick reminder of the tools we lean on (each earned in the parent note):

$(k n)$ = ==the number of ways to choose $k$ things from $n$ distinct things== $= \frac{n !}{k ! ( n - k )!}$ .
Pascal's rule: $(k n) = (k - 1 n - 1) + (k n - 1)$ .
Symmetry: $(k n) = (n - k n)$ .
Row sum: $k = 0 \sum n (k n) = 2^{n}$ .

For reference, here are the first rows:

Row 0:            1
Row 1:          1   1
Row 2:        1   2   1
Row 3:      1   3   3   1
Row 4:    1   4   6   4   1
Row 5:  1   5   10  10  5   1
Row 6: 1  6  15  20  15  6  1

Level 1 — Recognition

L1.1 Read a single entry

Problem. What number sits in row $5$ , position $2$ ? State what it counts.

Recall Solution

WHAT we do: read the triangle. Row $5$ is $1, 5, 10, 10, 5, 1$ . Positions are numbered starting at $k = 0$ , so position $2$ is the third number: $10$ . WHY / what it means: $(2 5) = 10$ is the number of ways to choose $2$ objects from $5$ distinct objects.

L1.2 Identify a coefficient

Problem. In the expansion of $(x + y)^{4}$ , what is the coefficient of $x^{2} y^{2}$ ?

Recall Solution

The Binomial Theorem says the coefficient of $x^{n - k} y^{k}$ in $(x + y)^{n}$ is $(k n)$ . Here $n = 4$ and the power of $y$ is $2$ , so $k = 2$ : the coefficient is $(2 4) = 6$ . Check against the triangle: row $4$ is $1, 4, 6, 4, 1$ — the middle entry is $6$ . ✓

Level 2 — Application

L2.1 Evaluate with the formula

Problem. Compute $(3 7)$ two ways: by the ordered-then-divide method, and by the formula.

Recall Solution

Ordered-then-divide. Pick 3 items in order from 7: $7 \cdot 6 \cdot 5 = 210$ ordered picks. Each set of 3 was counted $3! = 6$ times (its orderings), so $(3 7) = \frac{210}{6} = 35.$ Formula. $\frac{7 !}{3 ! 4 !} = \frac{5040}{6 \cdot 24} = \frac{5040}{144} = 35.$ ✓

L2.2 Extend a row with Pascal's rule

Problem. Given row $6 = 1, 6, 15, 20, 15, 6, 1$ , build row $7$ without any factorials.

Recall Solution

WHAT we do: each new entry is the sum of the two entries directly above it (Pascal's rule). The ends are always $1$ . $(0 7) = 1, (1 7) = 1 + 6 = 7, (2 7) = 6 + 15 = 21,$ $(3 7) = 15 + 20 = 35, (4 7) = 20 + 15 = 35, (5 7) = 15 + 6 = 21,$ $(6 7) = 6 + 1 = 7, (7 7) = 1.$ Row 7 $= 1, 7, 21, 35, 35, 21, 7, 1$ . WHY: any subset of the $7$ elements either contains element $7$ or it doesn't — those two disjoint cases are exactly the two parents above.

L2.3 A real choosing problem

Problem. A committee of $4$ is chosen from $9$ people. How many possible committees?

Recall Solution

A committee is an unordered group, so we want a combination: $(4 9)$ . $(4 9) = \frac{9 \cdot 8 \cdot 7 \cdot 6}{4 !} = \frac{3024}{24} = 126.$ WHY combination, not permutation: the committee ${A, B, C, D}$ is the same committee however we list the names, so order must not be counted.

Level 3 — Analysis

L3.1 Row sum in disguise

Problem. From a set of $8$ distinct books, how many ways can you pick any number of books (including picking none)? Answer without adding eight separate binomial coefficients.

Recall Solution

"Any number of books" means we want $(0 8) + (1 8) + \dots + (8 8)$ , the sum of all of row $8$ . By the row-sum identity this equals $\sum_{k = 0}^{8} (k 8) = 2^{8} = 256.$ WHY $2^{8}$ : decide independently for each book in or out — $2$ choices per book, $8$ books, so $2 \times 2 \times \dots \times 2 = 2^{8}$ total selections (see the figure).

Figure — Pascal's triangle — combinatorial interpretation

L3.2 Even vs odd subsets

Problem. Of the $256$ selections in L3.1, how many contain an even number of books (0, 2, 4, 6, or 8)?

Recall Solution

Set $x = 1, y = - 1$ in $(x + y)^{n} = \sum_{k} (k n) x^{n - k} y^{k}$ : $0 = (1 - 1)^{8} = \sum_{k = 0}^{8} (- 1)^{k} (k 8) = E (even- k sum) - O (odd- k sum) .$ So $E = O$ . And $E + O = 2^{8} = 256$ . Therefore $E = O = 128$ . Answer: $128$ even-sized selections. WHY it works: the $(- 1)^{k}$ flips the sign of every odd-sized subset; the total collapsing to $0$ forces even and odd counts to be equal.

L3.3 Symmetry to save work

Problem. Without computing both directly, explain why $(17 20) = (3 20)$ , then give the value.

Recall Solution

WHY they're equal: choosing which $17$ to take from $20$ is the same act as choosing which $3$ to leave — same set of choices, so same count. In symbols $(k n) = (n - k n)$ with $n = 20, k = 17$ . Value (via the easy side): $(3 20) = \frac{20 \cdot 19 \cdot 18}{3 !} = \frac{6840}{6} = 1140.$

Level 4 — Synthesis

L4.1 Hockey Stick sum

Problem. Evaluate $(2 2) + (2 3) + (2 4) + (2 5) + (2 6)$ and identify the single binomial coefficient it equals.

Recall Solution

This is a diagonal running down the "position-2" column, and the Hockey Stick Identity says a diagonal that starts at $(r r)$ and runs down to $(r n)$ sums to $(r + 1 n + 1)$ : $\sum_{i = r}^{n} (r i) = (r + 1 n + 1) .$ Here $r = 2$ , $n = 6$ , so the sum is $(3 7)$ . Numeric check: $1 + 3 + 6 + 10 + 15 = 35$ , and $(3 7) = 35$ . ✓ WHY (repeated Pascal's rule): each $(2 i)$ can be rewritten and the terms telescope; geometrically the diagonal ("stick") plus its bottom neighbour collapses into one entry (the "blade") — see the figure.

L4.2 Fibonacci from shallow diagonals

Problem. The shallow diagonals of Pascal's triangle sum to Fibonacci numbers. Verify this for the diagonal $(0 4) + (1 3) + (2 2)$ .

Recall Solution

A shallow diagonal steps up-and-right: keep $n + k$ -style pairs where the top index falls by $1$ and the bottom rises by $1$ . $(0 4) + (1 3) + (2 2) = 1 + 3 + 1 = 5.$ $5$ is the fifth Fibonacci number ( $1, 1, 2, 3, 5, 8, \dots$ ). ✓ WHY: Pascal's rule (each entry = sum of two above) is the same recursion as $F_{m} = F_{m - 1} + F_{m - 2}$ once you sum along these shallow lines. The figure shows the diagonal path.

L4.3 Committee with a fixed member

Problem. From $10$ people, a team of $4$ must be chosen, and Alice must be on the team. How many teams? Do it two ways and confirm they agree.

Recall Solution

Way 1 — direct. Alice is fixed, so we only choose the remaining $3$ from the other $9$ people: $(3 9) = \frac{9 \cdot 8 \cdot 7}{6} = 84.$ Way 2 — Pascal's rule made concrete. All teams of $4$ from $10$ : $(4 10) = 210$ . Split on Alice: teams with Alice $= (3 9)$ , teams without Alice $= (4 9) = 126$ . Check: $84 + 126 = 210 = (4 10)$ . ✓ This split is Pascal's rule $(4 10) = (3 9) + (4 9)$ with "element $10$ " playing the role of Alice. Answer: $84$ teams.

Level 5 — Mastery

L5.1 Vandermonde-style split

Problem. A group has $5$ women and $4$ men. How many ways to form a committee of $3$ ? Split the count by the number of women and show the pieces add to the direct answer $(3 9)$ .

Recall Solution

Direct: $(3 9) = 84$ . Split by number of women $w$ (multiplication + addition principles): $\sum_{w = 0}^{3} (w 5) (3 - w 4) .$

$w = 0$ : $(0 5) (3 4) = 1 \cdot 4 = 4$
$w = 1$ : $(1 5) (2 4) = 5 \cdot 6 = 30$
$w = 2$ : $(2 5) (1 4) = 10 \cdot 4 = 40$
$w = 3$ : $(3 5) (0 4) = 10 \cdot 1 = 10$ Total: $4 + 30 + 40 + 10 = 84 = (3 9)$ . ✓ WHY: for each fixed $w$ , choose women and men separately (multiply, by the Multiplication Principle); the cases $w = 0, 1, 2, 3$ are disjoint and exhaustive, so add them (Addition Principle). This is Vandermonde's identity $\sum_{w} (w m) (r - w p) = (r m + p)$ .

L5.2 Prove a row-sum weighting

Problem. Show that $k = 0 \sum n k (k n) = n 2^{n - 1}$ , and verify for $n = 4$ .

Recall Solution

Combinatorial proof. Count pairs $(subset S, a chosen leader inside S)$ of an $n$ -element set, in two ways.

Way A (subset first): choose a subset of size $k$ in $(k n)$ ways, then pick its leader in $k$ ways — sum over $k$ gives $\sum_{k} k (k n)$ .
Way B (leader first): choose the leader in $n$ ways, then each of the other $n - 1$ elements is independently in or out of $S$ : $2^{n - 1}$ ways. Total $n 2^{n - 1}$ . Same object counted two ways $\Rightarrow \sum_{k} k (k n) = n 2^{n - 1}$ . Verify $n = 4$ : $0 \cdot 1 + 1 \cdot 4 + 2 \cdot 6 + 3 \cdot 4 + 4 \cdot 1 = 0 + 4 + 12 + 12 + 4 = 32$ , and $4 \cdot 2^{3} = 4 \cdot 8 = 32$ . ✓

L5.3 Full synthesis

Problem. A pizza shop has $6$ toppings. A customer wants a pizza with at least $2$ toppings. How many such pizzas? Use the row sum and subtract the disallowed cases.

Recall Solution

Total selections (any number of toppings): $\sum_{k = 0}^{6} (k 6) = 2^{6} = 64$ (each topping in or out). Subtract the "fewer than 2" cases:

$0$ toppings (plain): $(0 6) = 1$
$1$ topping: $(1 6) = 6$ $64 - 1 - 6 = 57.$ Answer: $57$ pizzas with at least $2$ toppings. WHY subtract: it's far easier to count the two forbidden cases and remove them from the full $2^{6}$ than to add $(2 6) + (3 6) + (4 6) + (5 6) + (6 6)$ directly (though that also gives $15 + 20 + 15 + 6 + 1 = 57$ ✓).

Recall One-line self-test

Which identity turns "sum a diagonal" into a single entry? ::: The Hockey Stick Identity, $\sum_{i = r}^{n} (r i) = (r + 1 n + 1)$ . Why is a forced committee member not a choice? ::: She occupies a seat for free; you only choose the remaining seats from the remaining people. How do you count "at least 2" from a $2^{n}$ total? ::: Subtract the $0$ and $1$ cases: $2^{n} - (0 n) - (1 n)$ .

Connections

Pascal's triangle — combinatorial interpretation — the parent this page drills.
Combinations and Permutations — why we divide by $k!$ (L2.3).
Addition and Multiplication Principles — the engine of L5.1.
Hockey Stick Identity — L4.1.
Fibonacci numbers — L4.2 shallow diagonals.
Binomial Theorem — L1.2 and the even/odd trick in L3.2.
Factorials — the raw material of every $(k n)$ .