1.10 Counting principles and the extended binomial theorem

Many questions in mathematics begin with "how many ways…?" How many four-digit PIN codes are there? How many different committees can be chosen from a class? How many tickets would cover every possible lottery draw? Listing every possibility works only for very small cases, so counting relies on a few general principles and two formulas, for permutations (where order matters) and combinations (where it does not).

Counting gives exact probabilities whenever outcomes are equally likely, and it explains the coefficients of the binomial theorem. The second half of the subtopic extends that theorem from whole-number powers to powers such as $-1$ and $\frac{1}{2}$, where the expansion becomes an infinite series that is valid only for some values of $x$.

The counting principles

The product principle

A four-digit PIN code is made by choosing a first digit, then a second, then a third, then a fourth. There are 10 choices for each digit, and every choice for the first digit can be followed by every choice for the second, and so on. Multiplying the numbers of choices gives the total.

The principle applies even when the choices available at a later stage depend on earlier ones, as long as the number of choices does not. If the digits of a PIN must all be different, the first digit has 10 choices, the second only 9 (any digit except the first), the third 8 and the fourth 7. A row of boxes, one per position, keeps the reasoning clear.

The addition principle

Sometimes a task can be done in one of several separate ways that cannot happen at the same time. The counts for the separate cases are then added.

A short way to decide which principle to use is to read the description of the task. Successive choices that all happen ("a letter and then a digit") are multiplied; alternative cases where exactly one happens ("this format or that format") are added.

Permutations: arrangements where order matters

Arranging all the objects

Arranging $n$ different objects in a row is a sequence of $n$ choices: $n$ choices for the first position, $n - 1$ for the second, and so on down to 1 for the last. By the product principle, the number of arrangements is

Six different books can therefore be arranged on a shelf in $6! = 720$ ways. The factorial notation was introduced in 1.9.

Arranging some of the objects

Often only $r$ of the $n$ objects are arranged, such as the gold, silver and bronze medallists chosen from 8 finalists. Each ordered arrangement of this kind is a permutation.

The product $n(n - 1)\cdots(n - r + 1)$ has exactly $r$ factors, one for each position. Writing it as $\frac{n!}{(n - r)!}$

Arrangements with repeated objects

When some of the objects are identical, swapping them does not produce a new arrangement. The letters of BANANA give fewer than $6! = 720$ different words, because the three As can be swapped among themselves in $3!$ ways and the two Ns in $2!$ ways without any visible change. Each distinct word has therefore been counted $3! \times 2!$ times.

Arrangements with restrictions

Restrictions change the counting, but the same principles still apply. Three types of restriction appear regularly, and each has its own standard method.

Objects in fixed positions

Fill the restricted positions first, then arrange the remaining objects in the remaining positions. Doing the restricted positions first ensures that the number of choices for each one is known.

Objects kept together

To keep certain objects next to each other, tie them into a single block. Arrange the block with the other objects, then multiply by the number of ways of arranging the objects inside the block.

Objects kept apart

There are two methods for keeping objects apart. The complement method subtracts the arrangements where they are together from the total; it works neatly when only two objects must be kept apart. The gap method arranges the other objects first and then places the restricted objects in the gaps between them, so that no two of them can be adjacent.

Arrangements in a circle (extension)

When objects are arranged around a circle, only their positions relative to each other matter, so rotating the whole arrangement gives the same arrangement. Fixing one object in place and arranging the other $n - 1$ around it gives $(n - 1)!$ circular arrangements of $n$ different objects. Five people can sit at a round table in $4! = 24$

Combinations: selections where order does not matter

Combinations and the binomial coefficient

A committee of 3 chosen from 10 people is the same committee whichever order its members were chosen in. A selection of this kind, where order does not matter, is a combination.

Each combination of $r$ objects can be arranged in $r!$ orders, and each of these orders is a different permutation. So every combination corresponds to exactly $r!$ permutations:

This is the counting argument behind the binomial coefficients of 1.9. The number of committees of 3 from 10 people is $\binom{10}{3} = \frac{10 \times 9 \times 8}{3!} = 120$

Lottery odds

In a lottery where 6 numbers are drawn from the numbers 1 to 49, a ticket wins the top prize if its 6 numbers match those drawn, in any order. The number of possible draws is the number of combinations of 6 from 49.

Selections with conditions

Selection questions often specify how many objects must come from each group. Choose from each group separately and multiply (product principle). When a condition allows several cases, count each case and add (addition principle).

"At least" and the complement

A condition such as "at least one woman" includes several cases: one woman, two, three or four. Counting each case and adding works, but it is usually quicker to count the opposite condition and subtract from the total. The opposite of "at least one" is "none".

Selecting, then arranging

Some problems combine both ideas: a group is selected (combination) and then given roles or positions (permutation). Counting in two stages, and checking with a second method where possible, keeps the work reliable.

Counting and probability

When all outcomes are equally likely, a probability is a count of favourable outcomes divided by a count of all outcomes, and both counts can come from combinations. The full theory of probability is developed in 4.5.

The extended binomial theorem

From whole-number powers to rational powers

For $n \in \mathbb{N}$, the binomial theorem of 1.9 can be written using

so that

When $n$ is a natural number, one of the factors $n, n - 1, n - 2, \ldots$ eventually equals 0, every later coefficient is 0, and the expansion stops after $n + 1$ terms. The formula still makes sense when $n$

Why the expansion has a condition

An infinite series has a sum only when its terms shrink fast enough, which links the extended binomial theorem to the convergent series of 1.8. The case $n = -1$ shows this clearly. The coefficients are $1$, $-1$, $\frac{(-1)(-2)}{2!} = 1$

This is a geometric series with first term 1 and common ratio $-x$. Its sum to infinity is $\frac{1}{1 - (-x)} = \frac{1}{1 + x}$

The same condition holds for every non-natural $n$: the expansion of $(1 + x)^n$ is valid for $|x| < 1$. When the bracket is $(1 + kx)$

Expanding with a negative index

The coefficients of $(1 + x)^{-2}$ follow a simple pattern, $1, -2, 3, -4, \ldots$, but most expansions are not so tidy. When the bracket contains a multiple of $x$, or a negative sign, it is safest to expand $(1 + u)^n$

Expanding with a fractional index

A fractional index gives roots: $(1 + x)^{\frac{1}{2}} = \sqrt{1 + x}$

Expansions of the form (a + bx) to the power n

When the first term of the bracket is not 1, take it out as a factor first, so that the bracket has the form $(1 + \text{small})$. Then expand and multiply through by $a^n$.

Choosing a form for an approximation

To approximate a value such as $\sqrt{17}$, write the number as a perfect power plus a small amount, so that the expansion uses a small value of $\frac{b}{a}$

which is close to the true value $\sqrt{17} = 4.123106\ldots$. Writing $17 = 1 + 16$

Products and quotients

The extended binomial theorem combines with other brackets in the same way as in 1.9. A quotient such as $\frac{1 + 2x}{(1 - x)^2}$ is the product $(1 + 2x)(1 - x)^{-2}$

Partial fractions (1.11) give another way to expand quotients like this one: splitting a fraction into simpler parts first and expanding each part separately.

Exam-style questions on counting and the binomial series

Counting questions can appear on either paper, and they reward clear reasoning more than heavy arithmetic. Questions on the extended binomial theorem usually combine an expansion, its interval of validity and an approximation.

The second example is typical of a series question. The final part depends on choosing a value of $x$ that is inside the interval of validity.

Self-check

• To do:

  I can decide whether to multiply (product principle) or add (addition principle) when counting.

• To do:

  I can count arrangements of different objects and of objects with repeats, using $n!$ and $\frac{n!}{p!q!}$.

• To do:

  I can count arrangements with objects in fixed positions, kept together, or kept apart using gaps or the complement.