Combinations — nCr, Pascal's triangle: Exercises

Before we start, recall the two workhorses we will lean on the whole way. A combination $(r n)$ counts how many ways to choose $r$ things from $n$ when the order does not matter. Its formula is:

Level 1 — Recognition

The goal here is only to decide which idea applies and read a value off, not heavy arithmetic.

State whether each situation is a combination (order irrelevant) or a permutation (order matters): (a) choosing 3 toppings for a pizza from 8; (b) awarding gold, silver, bronze to 3 of 8 runners; (c) dealing a 5-card poker hand.

Recall Solution

WHAT we ask each time: "does swapping two chosen items change the outcome?" (a) Toppings on a pizza — mushroom-then-onion is the same pizza as onion-then-mushroom ⇒ order irrelevant ⇒ combination, $(3 8)$ . (b) Gold/silver/bronze are distinct prizes — swapping two runners changes who won gold ⇒ order matters ⇒ permutation, $^{8} P_{3}$ . (See Permutations — nPr.) (c) A poker hand is a set of cards; rearranging them in your hand is the same hand ⇒ combination, $(5 52)$ .

L1.2

Read these straight off the definition (no long multiplication): $(0 6)$ , $(6 6)$ , $(1 6)$ , $(8 9)$ .

Recall Solution

$(0 6) = 1$ : exactly one way to choose nothing (the empty set). Uses $0! = 1$ .
$(6 6) = 1$ : exactly one way to choose everybody.
$(1 6) = 6$ : choosing one item from six — six choices.
$(8 9) = (1 9) = 9$ by symmetry (choosing 8 to keep = choosing 1 to drop).

L1.3

In row $n = 5$ of Pascal's triangle, which entry is $(2 5)$ , and what is it? Use the picture below.

Figure — Combinations — nCr, Pascal's triangle

Recall Solution

Rows are numbered $n = 0, 1, 2, \dots$ from the top; positions are $r = 0, 1, 2, \dots$ from the left. So $(2 5)$ is row 5, position 2, the highlighted coral cell. Its value is $10$ . Check: $(2 5) = \frac{5 \cdot 4}{2 \cdot 1} = 10$ . ✓

Level 2 — Application

Now plug in and compute, using the falling-factor shortcut: write only the top $r$ falling factors of $^{n} P_{r}$ and divide by $r!$ . Never expand a full factorial.

L2.1

Compute $(4 9)$ .

Recall Solution

WHAT: take $r = 4$ falling factors on top, divide by $4!$ . $(4 9) = \frac{9 \cdot 8 \cdot 7 \cdot 6}{4 !} = \frac{3024}{24} = 126.$ WHY the shortcut: $(4 9) = \frac{9 !}{4 ! 5 !}$ , and the $5!$ cancels the tail $5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$ of $9!$ , leaving exactly $9 \cdot 8 \cdot 7 \cdot 6$ on top.

L2.2

A committee of 4 is chosen from 12 people. How many committees are possible?

Recall Solution

Order in a committee is irrelevant ⇒ combination. $(4 12) = \frac{12 \cdot 11 \cdot 10 \cdot 9}{24} = \frac{11880}{24} = 495.$

L2.3

Compute $(47 50)$ the smart way.

Recall Solution

$47$ is large; convert to the smaller $r$ via symmetry: $(47 50) = (3 50)$ . $(3 50) = \frac{50 \cdot 49 \cdot 48}{6} = \frac{117600}{6} = 19600.$ WHY: choosing 47 to keep is the same decision as choosing 3 to discard, and 3 factors beat 47 factors.

Level 3 — Analysis

These need a case-split or a complement. Decide the structure before computing.

L3.1

From 6 men and 5 women, form a committee of 4 containing exactly 2 men.

Recall Solution

WHAT: the committee is built in two independent stages — pick the men, then the women.

Choose 2 men from 6: $(2 6) = \frac{6 \cdot 5}{2} = 15$ .
Choose the remaining 2 members (women) from 5: $(2 5) = \frac{5 \cdot 4}{2} = 10$ . WHY multiply: each choice of men can pair with each choice of women independently ⇒ multiply. $15 \times 10 = 150.$

L3.2

From a standard deck, how many 5-card hands contain at least one ace? (There are 4 aces, 48 non-aces.)

Recall Solution

WHY use the complement: "at least one ace" splits into 1, 2, 3, or 4 aces — four cases. The opposite, "no ace," is a single count. Subtract it from the total.

Total hands: $(5 52) = 2598960$ .
No-ace hands (all 5 from the 48 non-aces): $(5 48) = \frac{48 \cdot 47 \cdot 46 \cdot 45 \cdot 44}{120} = 1712304$ . $At least one ace = 2598960 - 1712304 = 886 656.$

L3.3

How many 4-person groups from 10 people include both Amit and Bina?

Recall Solution

WHAT: force Amit and Bina in, then fill the rest. If both are already chosen, we need $4 - 2 = 2$ more from the remaining $10 - 2 = 8$ people. $(2 8) = \frac{8 \cdot 7}{2} = 28.$

Level 4 — Synthesis

Combine several tools: complements, case-splits, and Pascal / binomial identities.

L4.1

A team of 5 is chosen from 7 boys and 4 girls with at least 2 girls. How many ways?

Recall Solution

WHY case-split (not complement): "at least 2 girls" with only 4 girls means girls $= 2, 3, 4$ — three tidy cases, and the complement ("0 or 1 girl") is also two cases, so either way is fine. Split by girl-count:

2 girls, 3 boys: $(2 4) (3 7) = 6 \times 35 = 210$ .
3 girls, 2 boys: $(3 4) (2 7) = 4 \times 21 = 84$ .
4 girls, 1 boy: $(4 4) (1 7) = 1 \times 7 = 7$ . These are disjoint and exhaustive ⇒ add: $210 + 84 + 7 = 301.$

L4.2

Using the row-sum identity $\sum_{r = 0}^{n} (r n) = 2^{n}$ , find the number of non-empty subsets of a 6-element set.

Recall Solution

WHY $2^{n}$ : every element is independently either IN or OUT of a subset — 2 choices each, $n$ elements ⇒ $2^{n}$ total subsets. This equals the sum of all $(r n)$ because we can also count subsets by size $r$ and add over $r$ . (See Pascal's Triangle patterns.) Total subsets: $2^{6} = 64$ . Remove the one empty subset: $64 - 1 = 63.$

L4.3

Verify Pascal's rule numerically for $(3 6)$ : show $(3 6) = (2 5) + (3 5)$ .

Recall Solution

$(3 6) = \frac{6 \cdot 5 \cdot 4}{6} = 20.$ Right-hand side: $(2 5) = 10$ and $(3 5) = (2 5) = 10$ , so $10 + 10 = 20$ . ✓ WHY it works (story): fix one person, say Ravi. Committees of 3 from 6 either contain Ravi (then 2 more from the other 5 ⇒ $(2 5)$ ) or not (3 from the other 5 ⇒ $(3 5)$ ). Disjoint and exhaustive ⇒ add.

Level 5 — Mastery

Prove and reason with the identities themselves.

L5.1

Prove the symmetry $(r n) = (n - r n)$ from the formula, and explain it in one sentence of counting.

Recall Solution

Algebra: replace $r$ by $n - r$ in the formula: $(n - r n) = \frac{n !}{( n - r )! ( n - ( n - r ) ) !} = \frac{n !}{( n - r )! r !} = (r n) .$ The denominator is just the same two factorials swapped, so the values are equal. Counting sentence: every choice of $r$ items to keep is the same decision as choosing the $n - r$ items to leave out — one action, two names.

L5.2

Prove the hockey-stick identity for a small case: $(2 2) + (2 3) + (2 4) + (2 5) = (3 6) .$ Confirm numerically and explain via Pascal's rule.

Recall Solution

Numeric check: $1 + 3 + 6 + 10 = 20 = (3 6)$ . ✓ WHY (telescoping with Pascal): Pascal's rule says $(3 k) = (2 k - 1) + (3 k - 1)$ , i.e. $(2 k - 1) = (3 k) - (3 k - 1)$ . Summing $k = 3, 4, 5, 6$ makes the $(3 k - 1)$ terms cancel in a chain (telescope), leaving $(3 6) - (3 2) = (3 6) - 0 = (3 6)$ . Geometrically it is the "hockey stick": a diagonal run of entries in the triangle sums to the entry just below-and-left of its end.

L5.3

Show that $r = 0 \sum n (r n) = 2^{n}$ using the Binomial Theorem, and check for $n = 4$ .

Recall Solution

The Binomial Theorem says $(a + b)^{n} = \sum_{r = 0}^{n} (r n) a^{n - r} b^{r}$ . WHY set $a = b = 1$ : that makes every power equal to 1, so each term is just its coefficient $(r n)$ , and the left side becomes $2^{n}$ . Hence $2^{n} = (1 + 1)^{n} = \sum_{r = 0}^{n} (r n) .$ Check $n = 4$ : $1 + 4 + 6 + 4 + 1 = 16 = 2^{4}$ . ✓ (This is the row-sum used in L4.2 — see Probability — counting outcomes for why $2^{n}$ counts all yes/no outcomes.)

Recall Final self-check (all answers)

L2.1 $126$ · L2.2 $495$ · L2.3 $19600$ · L3.1 $150$ · L3.2 $886656$ · L3.3 $28$ · L4.1 $301$ · L4.2 $63$ · L4.3 $20 = 10 + 10$ · L5.2 $20$ · L5.3 $16$ .

Connections

Permutations — nPr — L1 distinguishes ordered vs unordered counts.
Factorials and 0! — powers every shortcut and the $(0 n) = 1$ edge case.
Binomial Theorem — L5.3 uses it to get row sums $2^{n}$ .
Probability — counting outcomes — subset counts feed probabilities.
Pascal's Triangle patterns — L1.3, L4.2, L5.2 use rows, row-sums, hockey-stick.

Exercises — Combinations — nCr, Pascal's triangle

Level 1 — Recognition

L1.1

L1.2

L1.3

Level 2 — Application

L2.1

L2.2

L2.3

Level 3 — Analysis

L3.1

L3.2

L3.3

Level 4 — Synthesis

L4.1

L4.2

L4.3

Level 5 — Mastery

L5.1

L5.2

L5.3

Connections