Permutations, Combinations, Sequences & Series

Weightage: Roughly 12 marks of the Business Mathematics section. Almost every error in counting problems comes from one question left unasked — does the order matter?

The fundamental principle of counting

Everything in counting rests on two rules.

The multiplication rule. If one operation can be performed in $m$ ways and, for each of these, a second can be performed in $n$ ways, then the two together can be performed in $m\times n$ ways. This applies when the operations happen together or in succession — the word to look for is and.

The addition rule. If one operation can be performed in $m$ ways and an alternative operation in $n$ ways, and the two cannot happen together, then one or the other can be performed in $m+n$ ways. This applies to mutually exclusive alternatives — the word to look for is or.

A journey from A to B by one of 3 routes and then from B to C by one of 4 routes can be made in $3\times 4=12$ ways. But a journey from A to C either by air in 3 ways or by rail in 4 ways can be made in $3+4=7$ ways.

Misreading and for or is the single largest source of error in this chapter, ahead of any confusion about formulas.

Factorial notation

$n!=n\times (n-1)\times (n-2)\times \cdots \times 3\times 2\times 1$

with the convention $0!=1$. That convention is not arbitrary: it is what makes the permutation and combination formulas work at their boundaries, since there is exactly one way to arrange nothing.

Factorials grow extremely fast, so questions are almost always designed so that terms cancel. Never compute a large factorial in full — write out the cancellation instead.

Permutations

A permutation is an arrangement in which order matters.

The number of permutations of $n$ distinct objects taken $r$ at a time:

${}^n{P}_r=\frac{n!}{(n-r)!}$

The reasoning is the multiplication rule applied directly. The first position can be filled in $n$ ways, the second in $n-1$ ways since one object is used, the third in $n-2$ ways, and so on for $r$ positions. The product $n(n-1)(n-2)\cdots (n-r+1)$ is exactly $n!/(n-r)!$.

Two consequences: ${}^n{P}_n=n!$, the number of ways of arranging all $n$ objects; and ${}^n{P}_0=1$.

Variations

Permutations with repetition allowed. Where an object may be used more than once, each of the $r$ positions can be filled in $n$ ways independently, giving $n^r$. A four-digit code from ten digits with repetition allowed has $10^4$ possibilities.

Permutations of objects not all distinct. Where $n$ objects include $p$ alike of one kind, $q$ alike of another and $s$ alike of a third:

$\frac{n!}{p!q!s!}$

The division corrects for arrangements that are indistinguishable. The word STATISTICS has 10 letters with S appearing 3 times, T 3 times and I 2 times, so the number of distinct arrangements is $10!/(3!3!2!)$.

Circular permutations. Arranging $n$ objects around a circle gives $(n-1)!$ arrangements, not $n!$. In a circle there is no fixed starting point, so every arrangement can be rotated into $n$ positions that are all the same arrangement — dividing $n!$ by $n$ gives $(n-1)!$.

Where clockwise and anticlockwise arrangements are not distinguished, as with a necklace of beads that can be flipped over, the count halves again to $(n-1)!/2$.

Combinations

A combination is a selection in which order does not matter.

${}^n{C}_r=\frac{n!}{r!(n-r)!}$

The relationship to permutations makes the definition transparent:

${}^n{P}_r={}^n{C}_r\times r!$

To arrange $r$ objects out of $n$, first select them, which can be done in ${}^n{C}_r$ ways, and then arrange the selected ones among themselves, which can be done in $r!$ ways. Dividing the permutation count by $r!$ removes the ordering and leaves the selection count.

Properties

${}^n{C}_r={}^n{C}_{n-r}$

Choosing $r$ objects to include is the same as choosing $n-r$ objects to exclude. This is worth using in computation: ${}^{20}{C}_{18}$ equals ${}^{20}{C}_2=190$, which is far quicker to evaluate.

${}^n{C}_r+{}^n{C}_{r-1}={}^{n+1}{C}_r$

${}^n{C}_0={}^n{C}_n=1,{}^n{C}_1=n$

${\text{If }}^n{C}_x={}^n{C}_y\text{ then either }x=y\text{ or }x+y=n$

The last is a standard question type and the second possibility is the one candidates forget.

Deciding which to use

Ask whether rearranging the chosen objects produces a different outcome.

• Selecting a committee of 3 from 10 people — a committee of A, B, C is the same committee however it is listed, so order does not matter. Combination.
• Electing a president, secretary and treasurer from 10 people — A as president and B as secretary differs from B as president and A as secretary, so order matters. Permutation.
• Forming a 4-digit number from given digits — 1234 differs from 4321. Permutation.
• Drawing 5 cards from a pack — the hand is the same whatever order the cards arrive in. Combination.

Words signalling combination: select, choose, committee, group, team, sample, hand. Words signalling permutation: arrange, order, rank, word, number, seat, code.

Arithmetic progression

A sequence in which each term differs from the previous by a constant common difference $d$.

$a,a+d,a+2d,a+3d,\dots$

$\text{nth term:}{t}_n=a+(n-1)d$

$\text{Sum of n terms:}{S}_n=\frac{n}{2}[2a+(n-1)d]=\frac{n}{2}(a+l)$

where $l$ is the last term. The second form is often faster when the last term is known, and it makes the structure clear: the sum is the number of terms times the average of the first and last.

The derivation is worth knowing. Writing the sum forwards and backwards and adding pairs vertically gives $n$ pairs each summing to $(a+l)$, so $2S_n=n(a+l)$.

Useful results: the sum of the first $n$ natural numbers is $n(n+1)/2$; three terms in AP are conveniently written $a-d$, $a$, $a+d$, which makes their sum $3a$ and simplifies most problems.

Geometric progression

A sequence in which each term is a constant multiple of the previous, the common ratio $r$.

$a,ar,a{r}^2,a{r}^3,\dots$

$\text{nth term:}{t}_n=a{r}^{n-1}$

$\text{Sum of n terms:}{S}_n=\frac{a(r^n-1)}{r-1}(r\ne 1),S_n=\frac{a(1-r^n)}{1-r}$

The two forms are algebraically identical; use whichever avoids a negative denominator. For $r>1$ the first is cleaner, and for $r<1$ the second.

Infinite geometric series

Where $|r|<1$, the terms shrink towards zero and the series converges:

$S_{\infty }=\frac{a}{1-r}$

The condition $|r|<1$ is essential. If $|r|\ge 1$ the terms do not shrink and the sum grows without limit.

This is the same mathematics that gives the present value of a perpetuity in the previous chapter: the payments form an infinite geometric series with common ratio $1/(1+i)$, which is less than 1, and summing it gives $A/i$.

Geometric mean. Between $a$ and $b$, the geometric mean is $\sqrt{ab}$, which is the mean proportional from the ratio chapter. Where three quantities are in GP, the middle one is the geometric mean of the other two.

Applications

Counting appears in business contexts as the number of ways of forming committees with conditions, of arranging items, or of selecting samples. Progressions appear in depreciation, where written down values form a GP with ratio $(1-d)$; in instalment schedules, where equal instalments form an AP if principal repayments are equal; and in compound interest itself, where the amounts at successive periods form a GP with ratio $(1+i)$.

How this chapter is examined

Expect questions on arrangements of letters of a word with repeated letters; circular arrangements, sometimes with a restriction such as two persons sitting together; committee selection with a condition such as at least two women; the value of $n$ or $r$ from an equation in ${}^n{C}_r$; the nth term or sum of an AP or GP; and the sum of an infinite GP.

Two habits prevent most errors. First, ask explicitly whether order matters before choosing a formula. Second, where a restriction is imposed — two people must sit together, or a particular item must be included — handle the restriction first and count the remaining freedom afterwards. Treating a restricted pair as a single unit, and then multiplying by the arrangements within that unit, is the standard technique.