Counting, Permutations & the Binomial Theorem

Expanding a bracket and counting arrangements turn out to be the same question.

Multiply out (a+b)3 by hand and look at the coefficients.

You get a3 + 3a2b + 3ab2 + b3. The numbers are 1, 3, 3, 1.

the coefficients were counted, not calculated 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 this row (a+b)³ = 1a³ + 3a²b + 3ab² + 1b³ each number counts the ways of choosing — nothing else

Nobody calculated those. Each term comes from picking a or b from each of the three brackets.

There are three ways to pick exactly one b, which is why a2b arrives three times.

So the coefficient is a count of choices, not an arithmetic result. Pascal’s triangle is a counting table, and the binomial theorem is the sentence that says so.

Where the binomial coefficients come from the coefficient counts choices: how many of the n factors gave a b (a + b)⁴ a⁴ + 4a³b + 6a²b² + 4ab³ + b⁴ 1 C(4,0) 4 C(4,1) 6 C(4,2) 4 C(4,3) 1 C(4,4)

Multiply the choices

If a meal is one of 4 starters and one of 3 mains, there are 4 × 3 = 12 meals.

Every independent decision multiplies the count, because each option of the first pairs with all of the second.

That single principle is behind every formula in this unit.

And means times

Choosing this and then that multiplies. Choosing this or that adds. Getting that backwards is the commonest counting error.

Does the order matter?

Gold, silver and bronze from 8 runners: order matters, so it is a permutation, P(8,3) = 336.

A committee of 3 from 8 people: order does not matter, so it is a combination, C(8,3) = 56.

The combination is smaller by exactly 3! = 6, since each committee was counted once for every way of ordering it.

Ask before you calculate

Would swapping two of the chosen items give a different outcome? Yes means permutation, no means combination — and the two answers differ by a factor of r!.

Pascal’s triangle is a table of combinations

Row n of the triangle lists C(n,0), C(n,1), …, C(n,n).

Each entry is the sum of the two above it, because choosing r from n either includes the new item or does not.

That is a proof, not a pattern: the two cases above are exactly the two ways it can happen.

Symmetry for free

C(n,r) = C(n, n-r), because choosing 3 to take is the same as choosing 5 to leave. Use whichever is the smaller calculation.

The binomial theorem

(a+b)n = ∑r=0n C(n,r) an-r br — each term picks b from r of the brackets.

The powers always add to n, which is a useful check on any term you write.

So the coefficient of a2b3 in (a+b)5 is C(5,3) = 10, with no expanding required.

Finding one term

The term with br is C(n,r)an-rbr. You never have to expand the whole thing to answer a question about one term.

Counting and probability together

A probability is a count of favourable outcomes divided by a count of all outcomes.

So both halves of the fraction are counting problems, usually of the same kind.

The probability of 3 heads in 5 flips is C(5,3)25 = 1032.

Count both, consistently

If the top counts unordered selections, the bottom must too. Mixing ordered and unordered counts is what produces impossible probabilities above 1.

Worked examples

Permutation or combination

From 10 students, how many ways to pick a president, a secretary and a treasurer?

  1. Swapping two of the three chosen people gives different officers, so order matters. That makes it a permutation.
  2. P(10,3) = 10 × 9 × 8. Ten choices, then nine, then eight.
  3. = 720. A committee of three from ten would be 120, six times smaller.

720

One binomial term

Find the coefficient of x3 in (x+2)5.

  1. The general term is C(5,r)x5-r2r. From the binomial theorem.
  2. For x3 we need 5-r=3, so r=2. The powers add to 5.
  3. C(5,2) · 22 = 10 × 4 = 40. The 2 gets raised to a power too.

40

Counting into probability

A bag has 5 red and 3 blue marbles. Two are drawn at once. What is the probability both are red?

  1. Drawn at once means order does not matter, so count combinations. Same kind top and bottom.
  2. Both red: C(5,2) = 10. All pairs: C(8,2) = 28. Favourable over total.
  3. 1028 = 514. About 36%.

514

Words to know

Permutation
An arrangement where order matters. P(n,r) = n!(n-r)!.
Combination
A selection where order does not matter. C(n,r) = n!r!(n-r)!.
Factorial
n! is the product of every whole number from 1 to n. 0! = 1.
Binomial theorem
The rule expanding (a+b)n using combinations as coefficients.
Fundamental counting principle
If one choice has m options and the next has n, together they have mn.

Mistakes to watch for

Using a permutation where order does not matter. A committee of 3 from 8 is C(8,3)=56, not P(8,3)=336 — the permutation counts each committee six times, once per ordering.

Adding when the choices are independent. Four starters and three mains give 12 meals, not 7. "And" multiplies; only "or" adds.

Forgetting to raise the constant to its power. In (x+2)5 the term with x3 carries 22, so the coefficient is 40, not 10.

Mixing ordered and unordered counts in a probability. If the numerator counts unordered pairs, the denominator must too, or the fraction is meaningless.

Treating 0! as 0. It is 1, which is what makes C(n,n)=1 come out right — there is exactly one way to choose everything.

The triangle was known in China as Yang Hui’s triangle three hundred years before Pascal, and in Persia before that.

Every row sums to a power of two, because choosing any subset of n items can be done in 2n ways.

The shallow diagonals of Pascal’s triangle add up to the Fibonacci numbers, for reasons nobody would guess from either definition.

Browse all courses