Permutation and combination

Class 11 Mathematics, unit 6, book pages 162–174

Practise 83 MCQsTake the unit quizReview 19 cards

Counting without listing is the idea of this unit. It starts with the rule of product and factorial notation, then counts arrangements in which order matters (permutations of distinct objects, of objects some of which are alike, and in a circle) and selections in which order does not matter (combinations). The formula for is obtained from , and the unit finishes with the use of permutations in cryptography.

Learning outcomes (4)
  • Explain and solve problems that involve the fundamental counting principle.
  • Explain and solve problems that involve permutations.
  • Explain and solve problems that involve combinations.
  • Apply the concept of permutation and combination to real world problems such as (cryptography, estimating the odds of winning a lottery, calculating the number of possible DNA sequences or protein structures, choosing different set of songs for certain occasions).

Fundamental principle of countingOften examined

Counting is a basic tool, and counting correctly and quickly matters in daily life. In this unit we learn techniques for finding the number of elements of a set without listing them one by one. To see the general rule, take a coin and a die. A coin has two outcomes, head () and tail (). A die has six outcomes, .

When we toss the coin and roll the die together, the outcomes are the ordered pairs written in the table below.

All outcomes of tossing a coin and rolling a die: 2 rows (coin) by 6 columns (die).
Coin \ Die123456
H
T

Counting the pairs gives outcomes. But we can get this number without listing anything. The coin has outcomes and the die has outcomes, and every outcome of the coin can go with every outcome of the die. So the total number of outcomes is the product of the two numbers:

6.1Rule of productOften examined

The rule of product extends the coin-and-die idea to any two or three things that happen one after the other.

Rule of product (two events)
If can happen in ways and can happen in ways, then the pair can happen in (or ) ways.
Rule of product (three events)
If three objects , , can happen in , and ways respectively, then the triplet can happen in (or ) ways.

Multiply the number of ways of each stage. The rule goes on in the same way for any number of stages.

In this unit we develop formulae and techniques for counting objects without listing them. These formulae are then used to count the arrangements of objects, first when the order matters (permutations) and then when it does not (combinations).

6.2Factorial notation

Factorial notation was introduced by the French mathematician Christian Kramp in 1808. The factorial of an integer is written and is the product of all the positive integers from down to :

Factorials of the first few numbers:

The first six factorials (and ).
FactorialValue
(by definition)

Derivation Why and

Aim. Show that and use it to find the value of .

  1. Write as the product of all integers from down to . Everything after the first factor is .
  2. The rule is meant to hold for every including , so put .
  3. Simplify the left side, , and the right side.
Result

The value is a definition that makes the rule work for all . It is derived again from in Section 6.3.1.

Example 1
Simplify the following. (i) (ii) (iii)
  1. (i) Write as so that appears in the numerator, then cancel it.
  2. (ii) Make the two denominators the same. Since , multiply the top and bottom of the first fraction by . Since , multiply the top and bottom of the second fraction by . Both denominators become .
  3. Add the numerators over the common denominator and put in .
  4. (iii) Write as and cancel .
  5. Multiply and then by .
Example 2
Write the following in factorial form. (i) (ii)
  1. (i) A product of consecutive numbers counting down is a quotient of two factorials. The first three factors of the numerator are , which is with cut off. The factor is with cut off.
  2. The denominator is with cut off.
  3. Put the three pieces together. Dividing by means multiplying by .
  4. (ii) The numerator is with cut off. The denominator is with cut off.
  5. Divide the first by the second, which means multiplying by the reciprocal.

6.3PermutationOften examined

Permutation
The number of ways in which objects out of objects () can be arranged in a definite order is called a permutation.

The word to notice is order. Two arrangements that contain the same objects in a different order are counted as different permutations. The next two examples show how the rule of product counts them.

Example 3
A vehicle number plate consists of four digits. How many different number plates with distinct digits can be made from the digits ?
Figure 6.1: Filling the four places of a number plate from the digits 1 to 6 without repeating a digit. Each place has one choice fewer than the one before it (the numbers of choices are the accent).
  1. The plate has four places. The first digit can be any of the six digits .
  2. The second digit cannot be the one already used, so digits are left.
  3. The third digit has choices, and the fourth digit has the remaining choices.
  4. The stages follow one another, so multiply the numbers of choices (rule of product).
Example 4
A student has four books of different subjects and wishes to arrange them on a shelf. In how many ways can he arrange the books?
  1. Fill the places on the shelf one by one. For the first place he has choices.
  2. For the second place books are left, for the third place , and for the fourth place only .
  3. Multiply the choices (rule of product).

The same reasoning works for any number of books, so with distinct objects the total number of arrangements is .

Worked example: three-digit numbers greater than 400
How many three-digit numbers greater than can be formed from the digits if no digit is repeated?
Fill the restricted place first. The hundreds digit must be , or ; the other places then take whatever digits are left.
  1. A number is greater than only if its hundreds digit is , or . Fill this restricted place first.
  2. One digit is now used, and repetition is not allowed, so the tens place can take any of the other digits.
  3. Two digits are used, so remain for the units place.
  4. The three stages follow one another, so multiply (rule of product).
  5. Check. All three-digit numbers with distinct digits number . The digits are half of , so half of them, , start with , or . This agrees.

6.3.1Permutation of n distinct objects taken r at a timeOften examined

Here we generalise the counting of Examples 3 and 4. We have n distinct objects and want to arrange r of them in some order, where 0\le r\le n. The number of such arrangements is written ^{n}P_{r}.

Derivation Formula for ^{n}P_{r}

Aim. Find the number of permutations of n distinct objects taken r at a time, ^{n}P_{r} (read 'n-permutation-r'), where 0\le r\le n.

Assumptions.
  • The n objects are all different.
  • Each object is used at most once.
Filling r places in order from n distinct objects: each place has one choice fewer than the one before, and the rth place has n-r+1 choices.
  1. Imagine r empty places in a row. We must fill them in order with r of the n objects. The first place can be filled by any of the n objects.
    \text{1st place: } n\ \text{choices}
  2. One object is used, so the second place has n-1 choices; the third has n-2 choices, and so on.
    \text{2nd: } n-1,\qquad \text{3rd: } n-2
  3. When we reach the rth place, r-1 objects have been used, so the number of choices is n-(r-1)=n-r+1.
    r\text{th: } n-(r-1)=n-r+1
  4. Multiply the numbers of choices (rule of product).
    ^{n}P_{r}=n(n-1)(n-2)\cdots(n-r+1)
  5. To write this with factorials, multiply and divide by (n-r)(n-r-1)\cdots3\cdot2\cdot1=(n-r)!.
    ^{n}P_{r}=n(n-1)(n-2)\cdots(n-r+1)\times\dfrac{(n-r)(n-r-1)(n-r-2)\cdots3\cdot2\cdot1}{(n-r)(n-r-1)(n-r-2)\cdots3\cdot2\cdot1}
  6. In the numerator, the factors from n down to n-r+1 join the factors from n-r down to 1 to make all of n(n-1)\cdots2\cdot1=n!. The denominator is (n-r)!.
    ^{n}P_{r}=\dfrac{n(n-1)\cdots(n-r+1)(n-r)(n-r-1)\cdots3\cdot2\cdot1}{(n-r)(n-r-1)\cdots3\cdot2\cdot1}=\dfrac{n!}{(n-r)!}
Result^{n}P_{r}=\dfrac{n!}{(n-r)!},\qquad 0\le r\le n

It is the product of r factors, starting at n and going down by one each time. For example ^{8}P_{2}=8\times7.

Derivation Deduction: ^{n}P_{n}=n! and 0!=1

Aim. Find ^{n}P_{n}, the number of arrangements of all n objects, and use it to find 0!.

  1. Put r=n in the product form ^{n}P_{r}=n(n-1)(n-2)\cdots(n-r+1). The last factor is n-n+1=1.
    ^{n}P_{n}=n(n-1)(n-2)\cdots1=n!
  2. Now put r=n in the factorial form ^{n}P_{r}=\dfrac{n!}{(n-r)!}.
    ^{n}P_{n}=\dfrac{n!}{(n-n)!}=\dfrac{n!}{0!}
  3. The two results for ^{n}P_{n} must be equal.
    n!=\dfrac{n!}{0!}\;\Longrightarrow\;0!=\dfrac{n!}{n!}=1
Result^{n}P_{n}=n!,\qquad 0!=1

Arranging all n objects gives n! ways, and the factorial formula agrees with this only if 0!=1.

Example 5
In how many ways can 6 people out of 8 be seated in a row?
  1. Here the total number of people is n=8 and the number to be seated is r=6. Order matters (who sits where), so we need ^{8}P_{6}.
    ^{8}P_{6}=\dfrac{8!}{(8-6)!}=\dfrac{8!}{2!}
  2. Write 8!=8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2! and cancel 2!.
    =\dfrac{8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2!}{2!}=8\cdot7\cdot6\cdot5\cdot4\cdot3=20160
20160\ \text{ways}

6.3.2Permutation of n objects when some of them are alike (not distinct)Often examined

So far all the objects were different. Many problems, such as arranging the letters of a word, contain repeated objects. Swapping two alike objects does not make a new arrangement, so we must not count it.

Derivation Permutations when some objects are alike

Aim. Find the number of arrangements of n objects when n_1 of them are alike of one kind, n_2 alike of a second kind, and so on up to n_k alike of a kth kind.

Assumptions.
  • There are n objects in all, split into k kinds, with n_1+n_2+\cdots+n_k=n.
  1. Let n=n_1+n_2+n_3+\cdots+n_k, where the first kind has n_1 objects, the second kind n_2, and the kth kind n_k (an object that is not repeated is a kind with n_i=1). Let X be the number of different arrangements we want.
    n=n_1+n_2+\cdots+n_k
  2. Pretend for a moment that all the objects are distinct. Then the n_1 objects of the first kind can be arranged among themselves in n_1! ways, the second kind in n_2! ways, and the kth kind in n_k! ways.
    n_1!,\quad n_2!,\quad \ldots,\quad n_k!
  3. So each one of the X real arrangements turns into n_1!\,n_2!\cdots n_k! arrangements of distinct objects, by the rule of product.
    \text{number of arrangements when all are distinct}=X\cdot n_1!\,n_2!\cdots n_k!
  4. But n distinct objects can be arranged in n! ways. Equate the two counts.
    X\cdot n_1!\,n_2!\cdots n_k!=n!
  5. Divide both sides by n_1!\,n_2!\cdots n_k!.
    X=\dfrac{n!}{n_1!\,n_2!\cdots n_k!}
ResultX=\dfrac{n!}{n_1!\,n_2!\cdots n_k!}

Alike objects cannot be told apart, so swapping them gives nothing new. Dividing by n_i! for each kind removes those repeated counts. The book writes this result as ^{n}P_{n}=\dfrac{n!}{n_1!\,n_2!\cdots n_k!}.

Example 6
How many different arrangements of the letters of the word EVENING can be made using all the letters?
  1. Count the letters. EVENING has 7 letters: E, V, E, N, I, N, G.
    n=7
  2. Find which letters repeat. E appears 2 times, N appears 2 times, and V, I, G appear once each (and 1!=1).
    n_1=2\ (\text{E}),\qquad n_2=2\ (\text{N})
  3. Use the formula for alike objects.
    \dfrac{7!}{2!\,2!}=\dfrac{7\cdot6\cdot5\cdot4\cdot3\cdot2!}{2!\cdot2\cdot1}=\dfrac{7\cdot6\cdot5\cdot4\cdot3}{2}=1260
1260
Worked example: arranging the letters of MISSISSIPPI
Find the number of arrangements of all the letters of MISSISSIPPI. How many of them begin with M?
  1. Count the letters: M appears 1 time, I appears 4 times, S appears 4 times and P appears 2 times, so n=11.
    1+4+4+2=11
  2. Alike letters cannot be told apart, so divide 11! by the factorial of each repeated letter.
    \dfrac{11!}{4!\,4!\,2!}
  3. Cancel 4! against 11! first, to keep the numbers small: \dfrac{11!}{4!}=11\cdot10\cdot9\cdot8\cdot7\cdot6\cdot5=1\,663\,200. Then divide by 4!\,2!=24\times2=48.
    \dfrac{1\,663\,200}{48}=34\,650
  4. Beginning with M: fix M in the first place. The remaining 10 letters are I (four), S (four) and P (two).
    \dfrac{10!}{4!\,4!\,2!}=\dfrac{3\,628\,800}{1152}=3150
34\,650\ \text{arrangements};\quad 3150\ \text{begin with M}

6.3.3Circular permutationOften examined

Sometimes we have to count arrangements of objects about a circle. Look at the four arrangements abcd, bcda, cdab, dabc. They are different along a line, but on a circle they are the same.

Derivation Number of circular arrangements

Aim. Find the number of ways of arranging n distinct objects round a circle.

Figure 6.2: Objects a,b,c,d placed round a circle. Turning the circle gives abcd, bcda, cdab and dabc, which are all the same arrangement because the position of each object relative to the others does not change.
  1. Take four objects a,b,c,d. Along a line the arrangements abcd, bcda, cdab, dabc are four different arrangements.
    abcd,\quad bcda,\quad cdab,\quad dabc
  2. Round a circle the position of each object with reference to the others is the same in all four, so they are all one circular arrangement. Each circular arrangement is therefore counted 4 times among the 4! arrangements in a line.
    \text{circular arrangements}=\dfrac{4!}{4}=\dfrac{4\cdot3\cdot2\cdot1}{4}=6
  3. For n objects, each circular arrangement appears n times among the n! linear arrangements (one for each object you start reading from). Divide by n.
    \text{number of ways}=\dfrac{n!}{n}=\dfrac{n\,(n-1)!}{n}
  4. Cancel n.
    =(n-1)!
Result\text{Number of circular arrangements of } n \text{ objects}=(n-1)!

There is no first place on a circle, so only the positions relative to one another matter. The result is the same as fixing one object and arranging the other n-1 objects in a line.

Check point: OPTICAL
In how many different ways can the letters of the word OPTICAL be arranged so that the vowels always come together?
  1. OPTICAL has 7 different letters. The vowels are O, I, A (3 of them) and the consonants are P, T, C, L (4 of them).
    3\ \text{vowels},\quad 4\ \text{consonants}
  2. Because the vowels must stay together, glue them into one block. Now we arrange 4 consonants and 1 block, which is 5 objects in a line.
    5!=120
  3. Inside the block the three vowels can be arranged among themselves in 3! ways.
    3!=6
  4. Multiply (rule of product).
    5!\times3!=120\times6=720
720\ \text{ways}
Example 7
In how many ways can 8 people sit around a circular table for dinner?
  1. There are n=8 people, seated round a circle.
    n=8
  2. Use the formula for circular arrangements.
    (8-1)!=7!=7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1=5040
5040\ \text{ways}
Example 8
There are 5 men and 5 women at a party. Find the number of ways in which they can be seated at a round table if (i) anyone can occupy any seat, (ii) men and women have alternate seats.
  1. (i) The total number of persons is 5+5=10. There is no restriction, so they are just 10 objects round a circle.
    (10-1)!=9!=362880
  2. (ii) The seats alternate: man, woman, man, woman, and so on. First seat the 5 men round the table. This is a circular arrangement of 5 objects.
    (5-1)!=4!=24
  3. The 5 men leave exactly 5 gaps between them, and each gap takes one woman. The women can be placed in the gaps in 5! ways (this is a line of places now, because the men have fixed the positions).
    5!=120
  4. By the rule of product the total is the product. (Starting with the women instead gives the same seatings, so we do not count it again.)
    4!\times5!=24\times120=2880
\text{(i) }9!=362880,\quad\text{(ii) }4!\times5!=2880
Worked example: why turning the table gives nothing new
Five friends A,B,C,D,E sit at a round table. Show that the two seatings in the figure are the same arrangement, and count the arrangements.
Both seatings read A,B,C,D,E clockwise. In the right-hand seating everyone has moved one place, but each person still has the same neighbour on the left and on the right.
  1. Compare neighbours. In both seatings A has E on one side and B on the other, B has A and C, and so on. Nothing but the position of the whole group has changed, so it is one arrangement.
  2. In a straight line, 5 people can be arranged in 5!=120 ways. Round a table each arrangement appears 5 times, once for each of the 5 turns of the table.
    \dfrac{5!}{5}=4!=24
  3. The same count by fixing a person: seat A anywhere (this removes the turning), then arrange the other 4 in the remaining 4 seats in order.
    (5-1)!=4!=24
24\ \text{arrangements}

When the circle can be flipped over

Now suppose the objects are arranged in a circle but the circle can be flipped over, like a ring of beads or a bunch of keys. Look at four objects 1,2,3,4. Going 1,2,3,4 anticlockwise gives one arrangement. After flipping, the same order reads clockwise. The arrangements that were anticlockwise are now clockwise, but they are the same arrangement.

Flipping a circular arrangement over reverses the direction round the circle: the order 1,2,3,4 that went anticlockwise now goes clockwise. If flipping is allowed, the two are counted as the same arrangement.

So the arrangements pair up, an arrangement and its mirror image, and each pair is counted once. The number of circular arrangements of 4 objects drops from (4-1)! to half of it:

\dfrac{(4-1)!}{2}=\dfrac{3!}{2}=\dfrac{6}{2}=3

To check, fix 1 at the top and read clockwise. The six circular arrangements are 1234, 1243, 1324, 1342, 1423, 1432. Flipping turns 1234 into 1432, 1243 into 1342, and 1324 into 1423, so these form 3 pairs.

Use of permutation in cryptography

Permutations are used in cryptography, the art of hiding a message. We encrypt a message by rearranging it and decrypt it by putting it back. The book explains the idea with the word PAK.

Label the letters of the word PAK with numbers: P as 1, A as 2 and K as 3. The three letters can be arranged in 3!=6 ways, so there are 6 encrypted words.

The six arrangements of PAK, each written as the labels of its letters (P=1, A=2, K=3).
Encrypted wordLabels in that order
PAK(1,\ 2,\ 3)
PKA(1,\ 3,\ 2)
AKP(2,\ 3,\ 1)
APK(2,\ 1,\ 3)
KAP(3,\ 2,\ 1)
KPA(3,\ 1,\ 2)
Encrypting and decrypting PAK
  1. Suppose we want PAK to be encrypted as APK. Read off the labels of A, P, K in that order. The encrypted word is APK, that is the labels 2\ 1\ 3.
    \text{APK}\;\longleftrightarrow\;(2\ \ 1\ \ 3)
  2. To decrypt, put the labels back in their natural order 1\ 2\ 3 and read the letter with each label. Label 1 is P, label 2 is A and label 3 is K.
    1\ 2\ 3\;\Longrightarrow\;\text{PAK}

6.4CombinationsOften examined

In a permutation we arrange objects in some definite order. If the order of the objects in the arrangement is not important, the arrangement (really a selection) is called a combination.

Combination
A selection of r objects taken out of n distinct objects, in which the order of the objects does not matter. It is denoted by ^{n}C_{r} or \dbinom{n}{r}.

Take three objects a, b, c. The arrangements abc, acb, bac, bca, cab, cba are all different as permutations, so there are 6 of them. But in a combination order is not important, so all of them are the same, and we count them as a single combination.

Permutation and combination compared.
PermutationCombination
Order of the objectsmattersdoes not matter
Three objects a,b,c taken all at a time6 arrangements: abc, acb, bac, bca, cab, cba1 combination: abc
Notation^{n}P_{r}^{n}C_{r} or \dbinom{n}{r}
Worked example: a pair of students, chosen or ranked
From four students A,B,C,D find (i) the number of ways to choose a team of two for a quiz, (ii) the number of ways to choose a captain and a vice-captain.
The six lines joining four points are the six pairs. Every pair can be ordered in two ways, so there are twice as many ordered pairs as pairs.
  1. (i) In a team the order does not matter, so \{A,B\} and \{B,A\} are the same team. This is a combination. The figure lists them: AB, AC, AD, BC, BD, CD.
    {}^{4}C_{2}=\dfrac{4\cdot3}{2!}=6
  2. (ii) A captain and a vice-captain are different jobs, so AB and BA differ. This is a permutation.
    {}^{4}P_{2}=4\cdot3=12
  3. Connection: each of the 6 pairs gives 2!=2 orders, so 12=2!\times6. In general {}^{n}P_{r}=r!\;{}^{n}C_{r}.
\text{(i) }6,\quad\text{(ii) }12

6.4.1Proof of the formula for combinationsOften examined

The formula for ^{n}C_{r} is obtained from the formula for ^{n}P_{r} by removing the orders of the chosen objects.

Derivation Proof of the formula ^{n}C_{r}

Aim. Prove that ^{n}C_{r}=\dbinom{n}{r}=\dfrac{n!}{r!\,(n-r)!}.

  1. Let X be the total number of combinations of n distinct objects taken r at a time, 0\le r\le n. So X={}^{n}C_{r}.
    X={}^{n}C_{r}
  2. Take any one of these combinations. Its r objects can be arranged in some order in r! ways. In a combination all these r! ways are treated as the same one way.
    1\ \text{combination}\leftrightarrow r!\ \text{permutations}
  3. So X combinations give r!\,X permutations of r objects chosen from the n.
    r!\,X=\text{(number of permutations)}
  4. The total number of permutations of n objects taken r at a time is ^{n}P_{r}.
    X\,r!={}^{n}P_{r}
  5. Divide by r! and put ^{n}P_{r}=\dfrac{n!}{(n-r)!}.
    X=\dfrac{1}{r!}\,{}^{n}P_{r}=\dfrac{1}{r!}\cdot\dfrac{n!}{(n-r)!}
Result^{n}C_{r}=\dbinom{n}{r}=\dfrac{n!}{r!\,(n-r)!},\qquad r!\,{}^{n}C_{r}={}^{n}P_{r}

Choosing r objects is the same as arranging them and then ignoring the order, so ^{n}C_{r} is ^{n}P_{r} divided by the r! orders of the chosen objects.

Deductions

Derivation Deduction (i): \dbinom{n}{n}=\dbinom{n}{0}=1

Aim. Show that \dbinom{n}{n}=\dbinom{n}{0}=1.

  1. Put r=n in \dbinom{n}{r}=\dfrac{n!}{r!\,(n-r)!} and use 0!=1.
    \dbinom{n}{n}=\dfrac{n!}{n!\,(n-n)!}=\dfrac{n!}{n!\,0!}=\dfrac{1}{0!}=\dfrac11=1
  2. Put r=0.
    \dbinom{n}{0}=\dfrac{n!}{0!\,(n-0)!}=\dfrac{n!}{1\cdot n!}=\dfrac11=1
Result\dbinom{n}{n}=\dbinom{n}{0}=1

There is only one way to take all n objects and only one way to take none.

Derivation Deduction (ii): \dbinom{n}{r}=\dbinom{n}{n-r}

Aim. Show that \dbinom{n}{r}=\dbinom{n}{n-r}.

  1. Replace r by n-r in the formula.
    \dbinom{n}{n-r}=\dfrac{n!}{(n-r)!\,[\,n-(n-r)\,]!}
  2. Simplify the bracket: n-(n-r)=r.
    =\dfrac{n!}{(n-r)!\,r!}
  3. This is the formula for \dbinom{n}{r} with the factors written in the other order.
    =\dfrac{n!}{r!\,(n-r)!}=\dbinom{n}{r}
Result\dbinom{n}{n-r}=\dbinom{n}{r}

Choosing r objects to take is the same as choosing n-r objects to leave behind.

Derivation Deduction (iii): \dbinom{n}{1}=\dbinom{n}{n-1}=n

Aim. Show that \dbinom{n}{1}=\dbinom{n}{n-1}=n.

  1. Put r=1 and write n!=n\,(n-1)!.
    \dbinom{n}{1}=\dfrac{n!}{1!\,(n-1)!}=\dfrac{n\,(n-1)!}{(n-1)!}=n
  2. Put r=n-1. Here n-(n-1)=1.
    \dbinom{n}{n-1}=\dfrac{n!}{(n-1)!\,[\,n-(n-1)\,]!}=\dfrac{n\,(n-1)!}{(n-1)!\,1!}=n
Result\dbinom{n}{1}=\dbinom{n}{n-1}=n

There are n ways to pick one object out of n.

Derivation Deduction (iv): \dbinom{n}{r}+\dbinom{n}{r-1}=\dbinom{n+1}{r}

Aim. Show that \dbinom{n}{r}+\dbinom{n}{r-1}=\dbinom{n+1}{r}.

  1. Write the first term from the formula.
    \dbinom{n}{r}=\dfrac{n!}{r!\,(n-r)!}\qquad(1)
  2. Replace r by r-1 for the second term. Since n-(r-1)=n-r+1:
    \dbinom{n}{r-1}=\dfrac{n!}{(r-1)!\,(n-r+1)!}\qquad(2)
  3. Add (1) and (2).
    \dbinom{n}{r}+\dbinom{n}{r-1}=\dfrac{n!}{r!\,(n-r)!}+\dfrac{n!}{(r-1)!\,(n-r+1)!}
  4. Write r!=r\,(r-1)! in the first term and (n-r+1)!=(n-r+1)(n-r)! in the second, so that both have (r-1)!\,(n-r)! in common.
    =\dfrac{n!}{r\,(r-1)!\,(n-r)!}+\dfrac{n!}{(r-1)!\,(n-r+1)\,(n-r)!}
  5. Take out the common factor \dfrac{n!}{(r-1)!\,(n-r)!}.
    =\dfrac{n!}{(r-1)!\,(n-r)!}\left[\dfrac1r+\dfrac{1}{n-r+1}\right]
  6. Add the fractions in the bracket over the common denominator r(n-r+1). The numerator is (n-r+1)+r=n+1.
    =\dfrac{n!}{(r-1)!\,(n-r)!}\cdot\dfrac{n-r+1+r}{r\,(n-r+1)}=\dfrac{n!}{(r-1)!\,(n-r)!}\cdot\dfrac{n+1}{r\,(n-r+1)}
  7. Combine: n!\,(n+1)=(n+1)!, (r-1)!\,r=r! and (n-r)!\,(n-r+1)=(n-r+1)!.
    =\dfrac{n!\,(n+1)}{(r-1)!\,r\,(n-r)!\,(n-r+1)}=\dfrac{(n+1)!}{r!\,(n+1-r)!}
  8. This is the formula for \dbinom{n+1}{r}.
    =\dbinom{n+1}{r}
Result\dbinom{n}{r}+\dbinom{n}{r-1}=\dbinom{n+1}{r}

Adding two neighbouring combinations of n objects gives a combination of n+1 objects.

Example 9
10 students applied for 6 HEC scholarships. In how many ways can these 6 be chosen?
  1. Total number of students n=10, number to be chosen r=6.
    n=10,\quad r=6
  2. The order of the chosen students is not necessary, so this is a combination.
    ^{10}C_{6}=\dfrac{10!}{6!\,(10-6)!}=\dfrac{10!}{6!\,4!}
  3. Write 10!=10\cdot9\cdot8\cdot7\cdot6!, cancel 6!, and divide by 4!=24.
    =\dfrac{10\cdot9\cdot8\cdot7\cdot6!}{6!\cdot4\cdot3\cdot2\cdot1}=\dfrac{5040}{24}=210
210\ \text{ways}
Example 10
Find the value of n if ^{n}C_{2}=10.
  1. Write ^{n}C_{2} with the formula.
    \dfrac{n!}{2!\,(n-2)!}=10
  2. Write n!=n(n-1)(n-2)!, cancel (n-2)! and multiply both sides by 2.
    \dfrac{n(n-1)(n-2)!}{(n-2)!}=10\times2\;\Longrightarrow\;n(n-1)=20
  3. Expand and bring everything to one side.
    n^{2}-n-20=0
  4. Factorise: split -n as -5n+4n.
    n^{2}-5n+4n-20=0\;\Longrightarrow\;n(n-5)+4(n-5)=0\;\Longrightarrow\;(n-5)(n+4)=0
  5. Solve each factor.
    n=5\quad\text{or}\quad n=-4
  6. n is a number of objects, so it is positive. Reject n=-4.
    n=5
  7. Check: ^{5}C_{2}=\dfrac{5\cdot4}{2}=10.
n=5
Check point: the committee
There are 8 men and 10 women and you need to form a committee of 5 men and 6 women. In how many ways can the committee be formed?
  1. The 5 men are chosen from 8 men. Order does not matter in a committee.
    ^{8}C_{5}=\dfrac{8!}{5!\,3!}=\dfrac{8\cdot7\cdot6}{3\cdot2\cdot1}=56
  2. The 6 women are chosen from 10 women.
    ^{10}C_{6}=210\quad(\text{Example 9})
  3. The two choices are made one after the other, so multiply (rule of product).
    56\times210=11760
11760\ \text{ways}
Worked example: two people who refuse to work together
A team of 4 is chosen from 9 people. Two of them, A and B, refuse to be in the same team. In how many ways can the team be chosen?
  1. Count all teams, with no condition.
    {}^{9}C_{4}=\dfrac{9\cdot8\cdot7\cdot6}{4!}=\dfrac{3024}{24}=126
  2. Count the forbidden teams, those containing both A and B. They are already in, so choose the other 2 members from the remaining 7 people.
    {}^{7}C_{2}=\dfrac{7\cdot6}{2}=21
  3. Subtract the forbidden teams from all teams.
    126-21=105
  4. Check by counting directly: neither of them {}^{7}C_{4}=35; exactly one of them 2\times{}^{7}C_{3}=2\times35=70. The total agrees.
    35+70=105
105\ \text{ways}

Formula sheet

Rule of product
m\times n\times p\times\cdots
m,n,p,\ldots: the numbers of ways of the successive stages
Factorial
n!=n(n-1)(n-2)\cdots3\times2\times1,\qquad (n+1)!=(n+1)\,n!
n: a positive integer
Zero factorial
0!=1
A definition that agrees with (n+1)!=(n+1)\,n! and ^{n}P_{n}=n!
Permutations of n objects taken r at a time
^{n}P_{r}=\dfrac{n!}{(n-r)!}=n(n-1)(n-2)\cdots(n-r+1)
n: number of distinct objects; r: number taken, 0\le r\le n
All n objects arranged
^{n}P_{n}=n!
Case r=n
Permutations when some objects are alike
\dfrac{n!}{n_1!\,n_2!\cdots n_k!}
n=n_1+n_2+\cdots+n_k; n_i: number of objects in the ith alike group
Circular permutations
(n-1)!
n distinct objects arranged round a circle
Circular permutations when the circle can be flipped
\dfrac{(n-1)!}{2}
Clockwise and anticlockwise arrangements counted as the same (the book shows n=4: \dfrac{3!}{2}=3)
Combinations
^{n}C_{r}=\dbinom{n}{r}=\dfrac{n!}{r!\,(n-r)!}
n: number of distinct objects; r: number chosen, 0\le r\le n
Relation between ^{n}C_{r} and ^{n}P_{r}
^{n}C_{r}\times r!={}^{n}P_{r}
A combination followed by an arrangement of the r chosen objects
Special values
\dbinom{n}{n}=\dbinom{n}{0}=1,\qquad \dbinom{n}{1}=\dbinom{n}{n-1}=n
Symmetry
\dbinom{n}{r}=\dbinom{n}{n-r}
Choosing r to take is the same as choosing n-r to leave
Sum of consecutive combinations
\dbinom{n}{r}+\dbinom{n}{r-1}=\dbinom{n+1}{r}

Key terms

Fundamental principle of counting (rule of product)
If one thing can happen in m ways and another in n ways, the pair can happen in m\times n ways; for three things, m\times n\times p ways.
Factorial
n!=n(n-1)(n-2)\cdots3\times2\times1, the product of the positive integers from n down to 1, with 0!=1.
Permutation
The number of ways in which r objects out of n objects can be arranged in a definite order, written ^{n}P_{r}.
Circular permutation
An arrangement of objects round a circle, where only the positions relative to one another matter; n objects can be arranged in (n-1)! ways.
Combination
A selection of r objects out of n distinct objects in which order is not important, written ^{n}C_{r} or \dbinom{n}{r}.
Encryption and decryption
Encrypting a word means rearranging its labelled letters by a permutation; decrypting puts the labels back in their natural order.

Exercise 6.1p. 164

Factorial notation. Use n!=n\,(n-1)! to open a factorial just far enough to cancel with another one; 0!=1. In equations with factorials, cancel first, solve the resulting algebraic equation, and keep only a positive integer n.

1
Evaluate the following:
Solution
(i) 10!
  1. By definition 10! is the product of all whole numbers from 10 down to 1. Stop at 6!=720 (from the book's table of factorials) to save work.
    10!=10\cdot9\cdot8\cdot7\cdot6!
  2. Multiply the first four factors, then multiply by 720.
    10!=5040\times720=3628800
10!=3628800
(ii) \dfrac{12!}{7!\,3!\,2!}
  1. Write 12! down to 7! so that 7! cancels with the 7! in the denominator.
    \dfrac{12!}{7!\,3!\,2!}=\dfrac{12\cdot11\cdot10\cdot9\cdot8\cdot7!}{7!\,3!\,2!}
  2. Cancel 7! and put 3!=6, 2!=2 in the denominator.
    =\dfrac{12\cdot11\cdot10\cdot9\cdot8}{6\cdot2}=\dfrac{95040}{12}
  3. Divide.
    =7920
7920
(iii) \dfrac{4!-2!}{3!+5!}
  1. Evaluate each factorial separately first. A sum or difference of factorials cannot be combined into one factorial.
    4!=24,\quad2!=2,\quad3!=6,\quad5!=120
  2. Substitute and simplify the numerator and the denominator.
    \dfrac{4!-2!}{3!+5!}=\dfrac{24-2}{6+120}=\dfrac{22}{126}
  3. Divide the top and bottom by 2.
    =\dfrac{11}{63}
\dfrac{11}{63}
(iv) \dfrac{(n-1)!}{(n-2)!}
  1. Use (n-1)!=(n-1)\,(n-2)!, because a factorial equals its first factor times the factorial one step below.
    \dfrac{(n-1)!}{(n-2)!}=\dfrac{(n-1)\,(n-2)!}{(n-2)!}
  2. Cancel (n-2)!.
    =n-1
n-1
(v) \dfrac{8!}{(6!)^{2}}
  1. Write 8!=8\cdot7\cdot6! so that one 6! can cancel.
    \dfrac{8!}{(6!)^{2}}=\dfrac{8\cdot7\cdot6!}{6!\cdot6!}
  2. Cancel one 6! and use 6!=720.
    =\dfrac{56}{720}
  3. Divide the top and bottom by 8.
    =\dfrac{7}{90}
\dfrac{7}{90}

Book answer. (i) 3628800, (ii) 7920, (iii) 11/63, (iv) n − 1, (v) 7/90

2
Write the following in factorial form:
Solution
(i) 14\cdot13\cdot12\cdot11
  1. The product starts at 14 and stops at 11, so it is 14! with the tail 10! removed. Multiply and divide by 10! to complete the chain.
    14\cdot13\cdot12\cdot11=\dfrac{14\cdot13\cdot12\cdot11\cdot10!}{10!}
  2. The numerator is now 14!.
    =\dfrac{14!}{10!}
\dfrac{14!}{10!}
(ii) 1\cdot3\cdot5\cdot7\cdot9
  1. Only the odd numbers are present. Multiply and divide by the missing even numbers 2\cdot4\cdot6\cdot8 to get 9! on top.
    1\cdot3\cdot5\cdot7\cdot9=\dfrac{9!}{2\cdot4\cdot6\cdot8}
  2. Take 2 out of each factor of the denominator: 2\cdot4\cdot6\cdot8=2^{4}(1\cdot2\cdot3\cdot4)=16\cdot4!.
    =\dfrac{9!}{4!\times16}
\dfrac{9!}{4!\times16}
(iii) n(n^{2}-1)
  1. Factorise the difference of squares.
    n(n^{2}-1)=n(n-1)(n+1)
  2. Arrange the three consecutive factors in descending order.
    =(n+1)\,n\,(n-1)
  3. The chain starts at n+1 and stops at n-1, so divide (n+1)! by the unused tail (n-2)!.
    =\dfrac{(n+1)!}{(n-2)!}
\dfrac{(n+1)!}{(n-2)!}
(iv) \dfrac{(n-3)(n-2)(n-1)}{n(n-4)}
  1. In the numerator, the factors (n-1)(n-2)(n-3) are the top of (n-1)! down to (n-3). Multiply and divide by (n-4)! to complete it.
    (n-3)(n-2)(n-1)=\dfrac{(n-1)(n-2)(n-3)\,(n-4)!}{(n-4)!}=\dfrac{(n-1)!}{(n-4)!}
  2. Put this over the denominator n(n-4).
    \dfrac{(n-3)(n-2)(n-1)}{n(n-4)}=\dfrac{(n-1)!}{n(n-4)\,(n-4)!}
\dfrac{(n-1)!}{n(n-4)\,(n-4)!}

Book answer. (i) 14!/10!, (ii) 9!/(4!×16), (iii) (n+1)!/(n−2)!, (iv) (n−1)!/(n(n−4)(n−4)!)

3
Prove the following:
Solution
(i) \dfrac{1}{5!}+\dfrac{3}{6!}+\dfrac{1}{7!}=\dfrac{4}{315}
  1. Use 7! as the common denominator. Since 7!=7\cdot6\cdot5! and 7!=7\cdot6!, the fractions become:
    \dfrac1{5!}=\dfrac{42}{7!},\qquad\dfrac3{6!}=\dfrac{21}{7!}
  2. Add the three fractions.
    \text{LHS}=\dfrac{42+21+1}{7!}=\dfrac{64}{5040}
  3. Divide the top and bottom by 16.
    =\dfrac{4}{315}=\text{RHS}

Hence proved.

(ii) \dfrac{(n-1)!}{(n-3)!}=n^{2}-3n+2
  1. Expand (n-1)! down to (n-3)!.
    \dfrac{(n-1)!}{(n-3)!}=\dfrac{(n-1)(n-2)(n-3)!}{(n-3)!}
  2. Cancel (n-3)! and multiply out.
    =(n-1)(n-2)=n^{2}-3n+2=\text{RHS}

Hence proved.

4
Show that:
Solution
(i) \dfrac{(2n)!}{n!}=2^{n}\bigl(1\cdot3\cdot5\cdots(2n-1)\bigr)
  1. Split (2n)! into its odd factors and its even factors.
    (2n)!=\bigl[1\cdot3\cdot5\cdots(2n-1)\bigr]\bigl[2\cdot4\cdot6\cdots(2n)\bigr]
  2. Take a factor 2 out of each of the n even numbers. That gives 2^{n} and leaves 1\cdot2\cdot3\cdots n=n!.
    2\cdot4\cdot6\cdots(2n)=2^{n}(1\cdot2\cdot3\cdots n)=2^{n}\,n!
  3. Put this back and divide by n!.
    \dfrac{(2n)!}{n!}=\dfrac{2^{n}\,n!\,\bigl[1\cdot3\cdot5\cdots(2n-1)\bigr]}{n!}=2^{n}\bigl(1\cdot3\cdot5\cdots(2n-1)\bigr)

Hence shown.

(ii) \dfrac{(2n-1)!}{(n-1)!}=2^{n-1}\bigl(1\cdot3\cdot5\cdots(2n-1)\bigr)
  1. Split (2n-1)! into odd factors (up to 2n-1) and even factors (up to 2n-2).
    (2n-1)!=\bigl[1\cdot3\cdot5\cdots(2n-1)\bigr]\bigl[2\cdot4\cdot6\cdots(2n-2)\bigr]
  2. There are n-1 even factors. Take 2 out of each.
    2\cdot4\cdot6\cdots(2n-2)=2^{n-1}(1\cdot2\cdot3\cdots(n-1))=2^{n-1}(n-1)!
  3. Substitute and divide by (n-1)!.
    \dfrac{(2n-1)!}{(n-1)!}=2^{n-1}\bigl(1\cdot3\cdot5\cdots(2n-1)\bigr)

Hence shown.

5
Find the values of n in the following.
Solution
(i) \dfrac{n}{(n-4)!}=\dfrac{3\cdot3!}{(n-3)!}
  1. Here 3\cdot3!=3\cdot6=18. Also (n-3)!=(n-3)\,(n-4)!, so write both sides over (n-4)!.
    \dfrac{n}{(n-4)!}=\dfrac{18}{(n-3)(n-4)!}
  2. Multiply both sides by (n-4)!.
    n=\dfrac{18}{n-3}
  3. Cross-multiply to get a quadratic.
    n(n-3)=18\;\Rightarrow\;n^{2}-3n-18=0
  4. Factorise.
    (n-6)(n+3)=0\;\Rightarrow\;n=6\ \text{or}\ n=-3
  5. A factorial needs n-4\ge0, so n is a positive integer. Reject n=-3.
    n=6
  6. Check: \dfrac{6}{2!}=3 and \dfrac{3\cdot3!}{3!}=3.
n=6
(ii) \dfrac{n!}{(n-4)!}:\dfrac{(n-1)!}{(n-3)!}=36:2
  1. Expand each factorial ratio.
    \dfrac{n!}{(n-4)!}=n(n-1)(n-2)(n-3),\qquad\dfrac{(n-1)!}{(n-3)!}=(n-1)(n-2)
  2. A ratio a:b=36:2 means a/b=18.
    \dfrac{n(n-1)(n-2)(n-3)}{(n-1)(n-2)}=\dfrac{36}{2}
  3. Cancel the common factors (n-1)(n-2) (they are not zero for n\ge4).
    n(n-3)=18
  4. Solve as in part (i).
    n^{2}-3n-18=0\;\Rightarrow\;(n-6)(n+3)=0\;\Rightarrow\;n=6
  5. Check: \dfrac{6!}{2!}=360 and \dfrac{5!}{3!}=20; 360:20=18=36:2.
n=6

Book answer. (i) 6, (ii) 6

6
Prove the following for n\in\mathbb{N}:
Solution
(i) (n+1)\bigl[n!\,n+(n-1)!\,(2n-1)+(n-2)!\,(n-1)\bigr]=(n+2)!
  1. Express every factorial in the bracket through the smallest one, (n-2)!: (n-1)!=(n-1)(n-2)! and n!=n(n-1)(n-2)!.
    n!\,n=n^{2}(n-1)(n-2)!,\qquad(n-1)!(2n-1)=(n-1)(2n-1)(n-2)!
  2. Take (n-1)(n-2)! out of all three terms of the bracket.
    \text{bracket}=(n-1)(n-2)!\,\bigl[n^{2}+(2n-1)+1\bigr]
  3. Simplify inside the square bracket.
    n^{2}+2n=n(n+2)
  4. Rebuild the factorial: (n-1)(n-2)!=(n-1)! and n\,(n-1)!=n!.
    \text{bracket}=(n-1)!\,n(n+2)=n!\,(n+2)
  5. Multiply by the outside factor (n+1) and combine: (n+1)\,n!=(n+1)!, then (n+2)(n+1)!=(n+2)!.
    \text{LHS}=(n+1)\,n!\,(n+2)=(n+1)!\,(n+2)=(n+2)!=\text{RHS}

Hence proved.

(ii) \dfrac{n!}{r!\,(n-r)!}+\dfrac{n!}{(r-1)!\,(n-r+1)!}=\dfrac{(n+1)!}{r!\,(n-r+1)!}
  1. Bring both fractions to the common denominator r!\,(n-r+1)!. Use r!=r\,(r-1)! and (n-r+1)!=(n-r+1)\,(n-r)!.
    \dfrac{n!}{r!\,(n-r)!}=\dfrac{n!\,(n-r+1)}{r!\,(n-r+1)!},\qquad\dfrac{n!}{(r-1)!\,(n-r+1)!}=\dfrac{n!\;r}{r!\,(n-r+1)!}
  2. Add the numerators.
    \text{LHS}=\dfrac{n!\,\bigl[(n-r+1)+r\bigr]}{r!\,(n-r+1)!}=\dfrac{n!\,(n+1)}{r!\,(n-r+1)!}
  3. Use (n+1)\,n!=(n+1)!.
    =\dfrac{(n+1)!}{r!\,(n-r+1)!}=\text{RHS}

Hence proved. This identity is the factorial form of the rule {}^{n}C_{r}+{}^{n}C_{r-1}={}^{n+1}C_{r} met in Exercise 6.3.

(iii) \dfrac{n!}{r!}=n(n-1)(n-2)\cdots(r+1)
  1. Expand n! from the top and stop at r!. This needs r\le n.
    n!=n(n-1)(n-2)\cdots(r+1)\cdot r!
  2. Divide by r!.
    \dfrac{n!}{r!}=n(n-1)(n-2)\cdots(r+1)=\text{RHS}

Hence proved.

(iv) (n-r+1)\cdot\dfrac{n!}{(n-r+1)!}=\dfrac{n!}{(n-r)!}
  1. Expand the bottom factorial one step: (n-r+1)!=(n-r+1)\,(n-r)!.
    \text{LHS}=(n-r+1)\cdot\dfrac{n!}{(n-r+1)\,(n-r)!}
  2. Cancel the factor (n-r+1).
    =\dfrac{n!}{(n-r)!}=\text{RHS}

Hence proved.

(v) 33! is divisible by 2^{15}
  1. The even numbers in 33!=1\cdot2\cdot3\cdots33 are 2,4,6,\dots,32. There are 16 of them.
    \text{even factors}=2\cdot4\cdot6\cdots32
  2. Take a factor 2 out of each of the 16 even numbers.
    2\cdot4\cdots32=2^{16}(1\cdot2\cdot3\cdots16)=2^{16}\cdot16!
  3. So 33! equals 2^{16} times a whole number (the product of 16! and the odd numbers 1,3,\dots,33).
    33!=2^{16}\cdot16!\cdot(1\cdot3\cdot5\cdots33)
  4. Since 2^{16}=2^{15}\cdot2, the number 33! is divisible by 2^{15}.
    \dfrac{33!}{2^{15}}=2\cdot16!\cdot(1\cdot3\cdots33)\in\mathbb{Z}

Hence proved.

(vi) \dfrac{(2n)!}{[(n-1)!]^{2}}=\dfrac{n(n+1)(n+2)\cdots(2n-1)(2n)}{(n-1)!}
  1. Split the square in the denominator into two factors and divide (2n)! by one of them.
    \dfrac{(2n)!}{[(n-1)!]^{2}}=\dfrac{(2n)!}{(n-1)!}\cdot\dfrac1{(n-1)!}
  2. Expand (2n)! from the top down to n, so that (n-1)! is left to cancel.
    (2n)!=(2n)(2n-1)\cdots(n+1)\,n\,(n-1)!
  3. Cancel (n-1)! and write the product in increasing order.
    \dfrac{(2n)!}{(n-1)!}=n(n+1)(n+2)\cdots(2n-1)(2n)
  4. Put the remaining \dfrac1{(n-1)!} underneath.
    \dfrac{(2n)!}{[(n-1)!]^{2}}=\dfrac{n(n+1)(n+2)\cdots(2n-1)(2n)}{(n-1)!}=\text{RHS}

Hence proved.

Note. In part (vi) the book prints the numerator as "2n!". It must be read as (2n)!: with 2\cdot n! the identity is false (take n=2: 2\cdot2!/1=4, but the right side is 2\cdot3\cdot4/1=24). The proof above uses (2n)!.

7
Find n, if
Solution
(i) \dfrac{n!}{(n-2)!}=930,\ n\ge2
  1. Expand n!=n(n-1)(n-2)! and cancel (n-2)!.
    \dfrac{n(n-1)(n-2)!}{(n-2)!}=930\;\Rightarrow\;n(n-1)=930
  2. Form the quadratic equation.
    n^{2}-n-930=0
  3. Find two numbers with product -930 and sum -1: they are -31 and 30.
    (n-31)(n+30)=0\;\Rightarrow\;n=31\ \text{or}\ n=-30
  4. A factorial needs a positive integer n, so reject -30.
    n=31
  5. Check: 31\cdot30=930.
n=31
(ii) \dfrac{n!}{(n-5)!}=20\cdot\dfrac{n!}{(n-3)!},\ n\ge5
  1. Expand each side down to the common factorial (n-5)! on the left and (n-3)! on the right.
    n(n-1)(n-2)(n-3)(n-4)=20\,n(n-1)(n-2)
  2. Cancel the common factor n(n-1)(n-2) (non-zero because n\ge5).
    (n-3)(n-4)=20
  3. Expand and collect.
    n^{2}-7n+12=20\;\Rightarrow\;n^{2}-7n-8=0
  4. Factorise.
    (n-8)(n+1)=0\;\Rightarrow\;n=8\ \text{or}\ n=-1
  5. Since n\ge5, reject -1.
    n=8
n=8
(iii) (n+2)!=60\,(n-1)!
  1. Expand (n+2)! down to (n-1)!.
    (n+2)(n+1)\,n\,(n-1)!=60\,(n-1)!
  2. Cancel (n-1)!.
    n(n+1)(n+2)=60
  3. The product of three consecutive positive integers is 60. Since 3\cdot4\cdot5=60, the integer n=3 works; no other positive n does, because n(n+1)(n+2) increases with n.
    n=3
n=3
(iv) (n+2)!=132\cdot n!
  1. Expand (n+2)!=(n+2)(n+1)\,n! and cancel n!.
    (n+2)(n+1)=132
  2. Expand and collect.
    n^{2}+3n+2=132\;\Rightarrow\;n^{2}+3n-130=0
  3. Factorise (the numbers 13 and -10 have product -130 and sum 3).
    (n+13)(n-10)=0\;\Rightarrow\;n=10\ \text{or}\ n=-13
  4. Reject the negative value.
    n=10
n=10
(v) (n+2)!=56\cdot n!
  1. Expand and cancel n!.
    (n+2)(n+1)=56
  2. Expand and collect.
    n^{2}+3n-54=0
  3. Factorise.
    (n+9)(n-6)=0\;\Rightarrow\;n=6\ \text{or}\ n=-9
  4. Reject the negative value.
    n=6
n=6
(vi) \dfrac1{9!}+\dfrac1{10!}=\dfrac{n}{11!}
  1. Multiply the whole equation by 11!.
    \dfrac{11!}{9!}+\dfrac{11!}{10!}=n
  2. Use 11!=11\cdot10\cdot9! and 11!=11\cdot10!.
    11\cdot10+11=n
  3. Add.
    n=110+11=121
n=121
(vii) n!=990\,(n-3)!
  1. Expand n!=n(n-1)(n-2)(n-3)! and cancel (n-3)!.
    n(n-1)(n-2)=990
  2. Factorise 990=11\cdot10\cdot9, three consecutive integers.
    n(n-1)(n-2)=11\cdot10\cdot9
  3. Since the product of three consecutive integers increases with n, the match is n=11.
    n=11
n=11
(viii) (n+1)!=6\,(n-1)!
  1. Expand (n+1)!=(n+1)\,n\,(n-1)! and cancel (n-1)!.
    (n+1)\,n=6
  2. Form and factorise the quadratic.
    n^{2}+n-6=0\;\Rightarrow\;(n+3)(n-2)=0
  3. Reject n=-3.
    n=2
n=2
(ix) \dfrac{(n+2)!}{(2n-1)!}=\dfrac{(n+3)!}{(2n+1)!}\cdot\dfrac{72}{7}
  1. Collect the factorials on one side: divide both sides by \dfrac{(n+3)!}{(2n+1)!}.
    \dfrac{(n+2)!}{(n+3)!}\cdot\dfrac{(2n+1)!}{(2n-1)!}=\dfrac{72}{7}
  2. Expand each ratio: (n+3)!=(n+3)(n+2)! and (2n+1)!=(2n+1)(2n)(2n-1)!.
    \dfrac{1}{n+3}\cdot(2n+1)(2n)=\dfrac{72}{7}
  3. Cross-multiply.
    7\cdot2n(2n+1)=72(n+3)\;\Rightarrow\;28n^{2}+14n=72n+216
  4. Collect and divide by 2.
    14n^{2}-29n-108=0
  5. The discriminant is 29^{2}+4\cdot14\cdot108=841+6048=6889=83^{2}.
    n=\dfrac{29\pm83}{28}=4\ \text{or}\ -\dfrac{27}{14}
  6. Only a positive integer is allowed in a factorial, so n=4. Check: left side \dfrac{6!}{7!}=\dfrac17; right side \dfrac{7!}{9!}\cdot\dfrac{72}{7}=\dfrac1{72}\cdot\dfrac{72}{7}=\dfrac17.
n=4
(x) \dfrac{1}{2\,(n-2)!}:\dfrac{1}{4!\,(n-4)!}=2,\ n\ge4
  1. A ratio a:b=2 means a/b=2. Write the quotient as a product with the reciprocal.
    \dfrac{1}{2\,(n-2)!}\times\dfrac{4!\,(n-4)!}{1}=2
  2. Put 4!=24 and expand (n-2)!=(n-2)(n-3)(n-4)!, then cancel (n-4)!.
    \dfrac{24\,(n-4)!}{2\,(n-2)(n-3)(n-4)!}=2\;\Rightarrow\;\dfrac{12}{(n-2)(n-3)}=2
  3. Cross-multiply.
    (n-2)(n-3)=6\;\Rightarrow\;n^{2}-5n=0
  4. Factorise.
    n(n-5)=0\;\Rightarrow\;n=0\ \text{or}\ n=5
  5. The condition is n\ge4, so n=5.
n=5

Book answer. (i) 31, (ii) 8, (iii) 3, (iv) 10, (v) 6, (vi) 121, (vii) 11, (viii) 2, (ix) 4, (x) 5

Exercise 6.2p. 168–169

Permutations {}^{n}P_{r}=\dfrac{n!}{(n-r)!} with distinct objects, with alike objects (\dfrac{n!}{n_{1}!\,n_{2}!\cdots}), round a table ((n-1)!), and the use of permutations in cryptography. Handle the restricted place first, tie objects that must stay together into one block, and subtract the unwanted case for "never together".

12025 Annual I, Set D, Q.2 (ii) OR
Prove the following for n\in\mathbb{N}.
Solution
(i) {}^{n}P_{r}=\dfrac{n!}{(n-r)!}
  1. To arrange r objects out of n distinct objects, fill r places one after another. The first place can be filled in n ways.
    n
  2. One object is used, so the second place can be filled in n-1 ways, the third in n-2 ways, and so on. The rth place has n-(r-1)=n-r+1 choices.
    n,\ n-1,\ n-2,\ \dots,\ n-r+1
  3. By the rule of product, multiply the choices.
    {}^{n}P_{r}=n(n-1)(n-2)\cdots(n-r+1)
  4. Multiply and divide by (n-r)!=(n-r)(n-r-1)\cdots3\cdot2\cdot1. The numerator then becomes n!.
    {}^{n}P_{r}=\dfrac{n(n-1)\cdots(n-r+1)\,(n-r)(n-r-1)\cdots3\cdot2\cdot1}{(n-r)!}=\dfrac{n!}{(n-r)!}

Hence proved.

(ii) {}^{n}P_{n}={}^{n}P_{n-1}
  1. Use the formula with r=n. Recall 0!=1.
    {}^{n}P_{n}=\dfrac{n!}{(n-n)!}=\dfrac{n!}{0!}=n!
  2. Use the formula with r=n-1. Here n-(n-1)=1 and 1!=1.
    {}^{n}P_{n-1}=\dfrac{n!}{[n-(n-1)]!}=\dfrac{n!}{1!}=n!
  3. Both equal n!.
    {}^{n}P_{n}={}^{n}P_{n-1}

Hence proved. (If n-1 objects are arranged, the last object has only one place left, so it adds no new choice.)

(iii) {}^{n}P_{r}=n\cdot{}^{n-1}P_{r-1}
  1. Write the right side with the formula. For {}^{n-1}P_{r-1} replace n by n-1 and r by r-1.
    {}^{n-1}P_{r-1}=\dfrac{(n-1)!}{[(n-1)-(r-1)]!}=\dfrac{(n-1)!}{(n-r)!}
  2. Multiply by n and use n\,(n-1)!=n!.
    n\cdot{}^{n-1}P_{r-1}=\dfrac{n\,(n-1)!}{(n-r)!}=\dfrac{n!}{(n-r)!}
  3. This is {}^{n}P_{r}.
    =\,{}^{n}P_{r}

Hence proved.

(iv) {}^{n}P_{r}={}^{n-1}P_{r}+r\cdot{}^{n-1}P_{r-1}
  1. Write both terms of the right side with the formula.
    {}^{n-1}P_{r}=\dfrac{(n-1)!}{(n-1-r)!},\qquad r\cdot{}^{n-1}P_{r-1}=\dfrac{r\,(n-1)!}{(n-r)!}
  2. Make the denominators equal. Since (n-r)!=(n-r)\,(n-r-1)!, multiply the first fraction by \dfrac{n-r}{n-r}.
    {}^{n-1}P_{r}=\dfrac{(n-r)\,(n-1)!}{(n-r)!}
  3. Add and take out (n-1)!.
    \text{RHS}=\dfrac{(n-1)!\,\bigl[(n-r)+r\bigr]}{(n-r)!}=\dfrac{n\,(n-1)!}{(n-r)!}
  4. Use n\,(n-1)!=n!.
    =\dfrac{n!}{(n-r)!}={}^{n}P_{r}=\text{LHS}

Hence proved.

(v) {}^{n}P_{n}=2\cdot{}^{n}P_{n-2}
  1. Find {}^{n}P_{n}.
    {}^{n}P_{n}=n!
  2. Find {}^{n}P_{n-2}. Here n-(n-2)=2.
    {}^{n}P_{n-2}=\dfrac{n!}{2!}=\dfrac{n!}{2}
  3. Multiply by 2.
    2\cdot{}^{n}P_{n-2}=n!={}^{n}P_{n}

Hence proved.

22026 Annual I, Set B, Q.2 (iii) OR
Find n, if:
Solution
(i) {}^{n}P_{4}=20\,{}^{n}P_{2}
  1. Write both sides as products. {}^{n}P_{r} has r factors starting at n.
    n(n-1)(n-2)(n-3)=20\,n(n-1)
  2. Cancel n(n-1). It is not zero because n\ge4 is needed for {}^{n}P_{4}.
    (n-2)(n-3)=20
  3. Expand and collect.
    n^{2}-5n+6=20\;\Rightarrow\;n^{2}-5n-14=0
  4. Factorise.
    (n-7)(n+2)=0\;\Rightarrow\;n=7\ \text{or}\ n=-2
  5. n must be a positive integer, so reject -2. Check: {}^{7}P_{4}=840 and 20\cdot{}^{7}P_{2}=20\cdot42=840.
n=7
(ii) {}^{2n}P_{3}=100\,{}^{n}P_{2}
  1. Write both sides as products of consecutive factors.
    2n(2n-1)(2n-2)=100\,n(n-1)
  2. Take 2 out of the last factor on the left, 2n-2=2(n-1).
    2n(2n-1)\cdot2(n-1)=100\,n(n-1)
  3. Cancel n(n-1) and divide by 4 (n\ge2 so it is not zero).
    4(2n-1)=100\;\Rightarrow\;2n-1=25
  4. Solve.
    n=13
n=13
(iii) 16\,{}^{n}P_{3}=13\,{}^{n+1}P_{3}
  1. Write both sides as products.
    16\,n(n-1)(n-2)=13\,(n+1)\,n\,(n-1)
  2. Cancel n(n-1) (not zero since n\ge3).
    16(n-2)=13(n+1)
  3. Expand and collect like terms.
    16n-32=13n+13\;\Rightarrow\;3n=45
  4. Solve.
    n=15
n=15
(iv) {}^{n}P_{5}=20\,{}^{n}P_{3}
  1. Write both sides as products. The first three factors of {}^{n}P_{5} are those of {}^{n}P_{3}.
    n(n-1)(n-2)(n-3)(n-4)=20\,n(n-1)(n-2)
  2. Cancel n(n-1)(n-2).
    (n-3)(n-4)=20
  3. Expand and collect.
    n^{2}-7n+12=20\;\Rightarrow\;n^{2}-7n-8=0
  4. Factorise.
    (n-8)(n+1)=0\;\Rightarrow\;n=8\ \text{or}\ n=-1
  5. Reject the negative value.
    n=8
n=8
(v) 30\,{}^{n}P_{6}={}^{n+1}P_{7}
  1. Use the formula on both sides.
    30\,\dfrac{n!}{(n-6)!}=\dfrac{(n+1)!}{(n+1-7)!}=\dfrac{(n+1)!}{(n-6)!}
  2. The denominators are equal, so cancel (n-6)!.
    30\,n!=(n+1)!
  3. Use (n+1)!=(n+1)\,n! and cancel n!.
    30=n+1
  4. Solve.
    n=29
n=29
(vi) {}^{n}P_{5}:{}^{n-1}P_{4}=6:1
  1. By Question 1(iii), {}^{n}P_{r}=n\cdot{}^{n-1}P_{r-1}. With r=5, {}^{n}P_{5}=n\cdot{}^{n-1}P_{4}.
    \dfrac{{}^{n}P_{5}}{{}^{n-1}P_{4}}=\dfrac{n\cdot{}^{n-1}P_{4}}{{}^{n-1}P_{4}}=n
  2. The ratio 6:1 means the quotient is 6.
    n=6

Check: {}^{6}P_{5}=720 and {}^{5}P_{4}=120, and 720\div120=6.

n=6
(vii) {}^{n}P_{4}:{}^{n-1}P_{3}=9:1
  1. By Question 1(iii) with r=4, {}^{n}P_{4}=n\cdot{}^{n-1}P_{3}, so the quotient is n.
    \dfrac{{}^{n}P_{4}}{{}^{n-1}P_{3}}=n
  2. The ratio 9:1 means the quotient is 9.
    n=9

Check: {}^{9}P_{4}=3024 and {}^{8}P_{3}=336, and 3024\div336=9.

n=9
(viii) {}^{n-1}P_{3}:{}^{n+1}P_{3}=5:12
  1. Write both as products of three factors.
    {}^{n-1}P_{3}=(n-1)(n-2)(n-3),\qquad{}^{n+1}P_{3}=(n+1)\,n\,(n-1)
  2. Form the ratio and cancel (n-1).
    \dfrac{(n-2)(n-3)}{(n+1)\,n}=\dfrac{5}{12}
  3. Cross-multiply.
    12(n^{2}-5n+6)=5(n^{2}+n)\;\Rightarrow\;7n^{2}-65n+72=0
  4. The discriminant is 65^{2}-4\cdot7\cdot72=4225-2016=2209=47^{2}.
    n=\dfrac{65\pm47}{14}=8\ \text{or}\ \dfrac{9}{7}
  5. n must be a positive integer (and n-1\ge3), so n=8. Check: {}^{7}P_{3}=210, {}^{9}P_{3}=504, and \dfrac{210}{504}=\dfrac{5}{12}.
n=8
(ix) {}^{2n-1}P_{n}:{}^{2n+1}P_{n-1}=22:7
  1. Use the formula. For the first, (2n-1)-n=n-1. For the second, (2n+1)-(n-1)=n+2.
    {}^{2n-1}P_{n}=\dfrac{(2n-1)!}{(n-1)!},\qquad{}^{2n+1}P_{n-1}=\dfrac{(2n+1)!}{(n+2)!}
  2. Divide, and expand (2n+1)!=(2n+1)(2n)(2n-1)! and (n+2)!=(n+2)(n+1)\,n\,(n-1)!.
    \dfrac{(2n-1)!}{(n-1)!}\cdot\dfrac{(n+2)!}{(2n+1)!}=\dfrac{(n+2)(n+1)\,n}{(2n+1)(2n)}=\dfrac{(n+1)(n+2)}{2(2n+1)}
  3. Equate to \dfrac{22}{7} and cross-multiply.
    7(n^{2}+3n+2)=44(2n+1)\;\Rightarrow\;7n^{2}-67n-30=0
  4. The discriminant is 67^{2}+4\cdot7\cdot30=4489+840=5329=73^{2}.
    n=\dfrac{67\pm73}{14}=10\ \text{or}\ -\dfrac{3}{7}
  5. Only n=10 is a positive integer. Check: {}^{19}P_{10}:{}^{21}P_{9}=22:7.
n=10

Book answer. (i) 7, (ii) 13, (iii) 15, (iv) 8, (v) 29, (vi) 6, (vii) 9, (viii) 8, (ix) 10

32026 Annual I, Set D, Q.2 (x) OR
Find r, if:
Solution
(i) {}^{6}P_{r-1}={}^{5}P_{4}
  1. Evaluate the right side.
    {}^{5}P_{4}=5\cdot4\cdot3\cdot2=120
  2. Use the formula on the left: 6-(r-1)=7-r.
    {}^{6}P_{r-1}=\dfrac{6!}{(7-r)!}=\dfrac{720}{(7-r)!}
  3. Equate and solve for the factorial.
    \dfrac{720}{(7-r)!}=120\;\Rightarrow\;(7-r)!=6=3!
  4. So 7-r=3.
    r=4
r=4
(ii) {}^{10}P_{r}=2\,{}^{9}P_{r}
  1. Use the formula on both sides.
    \dfrac{10!}{(10-r)!}=2\cdot\dfrac{9!}{(9-r)!}
  2. Expand 10!=10\cdot9! and (10-r)!=(10-r)\,(9-r)!, then cancel 9! and (9-r)!.
    \dfrac{10}{10-r}=2
  3. Solve.
    10=20-2r\;\Rightarrow\;r=5
r=5
(iii) {}^{15}P_{r}=210
  1. {}^{15}P_{r} is a product of r factors starting at 15. Factorise 210=15\cdot14.
    15\cdot14=210
  2. The product has two factors, 15 and 14, so r=2. No other r works: {}^{15}P_{1}=15 and {}^{15}P_{3}=2730.
    {}^{15}P_{2}=210\;\Rightarrow\;r=2
r=2
(iv) {}^{10}P_{r}=3\,{}^{10}P_{r-1}
  1. Use the formula on both sides.
    \dfrac{10!}{(10-r)!}=3\cdot\dfrac{10!}{(11-r)!}
  2. Cancel 10! and use (11-r)!=(11-r)\,(10-r)!.
    \dfrac1{(10-r)!}=\dfrac{3}{(11-r)(10-r)!}\;\Rightarrow\;11-r=3
  3. Solve.
    r=8
r=8
(v) 4\,{}^{6}P_{r}={}^{6}P_{r+1}
  1. Use the formula on both sides.
    4\cdot\dfrac{6!}{(6-r)!}=\dfrac{6!}{(5-r)!}
  2. Cancel 6! and use (6-r)!=(6-r)\,(5-r)!.
    \dfrac{4}{(6-r)\,(5-r)!}=\dfrac1{(5-r)!}\;\Rightarrow\;4=6-r
  3. Solve.
    r=2
r=2
(vi) 2\,{}^{6}P_{r-1}={}^{5}P_{r}
  1. Use the formula on both sides. For {}^{6}P_{r-1} the denominator is [6-(r-1)]!=(7-r)!.
    2\cdot\dfrac{6!}{(7-r)!}=\dfrac{5!}{(5-r)!}
  2. Write 6!=6\cdot5!, cancel 5! and use (7-r)!=(7-r)(6-r)(5-r)!.
    \dfrac{12}{(7-r)(6-r)}=1
  3. Cross-multiply and expand.
    (7-r)(6-r)=12\;\Rightarrow\;r^{2}-13r+30=0
  4. Factorise.
    (r-3)(r-10)=0\;\Rightarrow\;r=3\ \text{or}\ r=10
  5. In {}^{5}P_{r} we need r\le5, so reject r=10. Check: 2\cdot{}^{6}P_{2}=60={}^{5}P_{3}.
r=3
(vii) {}^{54}P_{r+3}:{}^{56}P_{r+6}=1:30800
  1. Use the formula on both sides. 54-(r+3)=51-r and 56-(r+6)=50-r.
    {}^{54}P_{r+3}=\dfrac{54!}{(51-r)!},\qquad{}^{56}P_{r+6}=\dfrac{56!}{(50-r)!}
  2. Form the quotient and write 56!=56\cdot55\cdot54! and (51-r)!=(51-r)\,(50-r)!. Then 54! and (50-r)! cancel.
    \dfrac{54!}{(51-r)!}\cdot\dfrac{(50-r)!}{56!}=\dfrac{1}{56\cdot55\,(51-r)}=\dfrac{1}{3080\,(51-r)}
  3. Equate to \dfrac{1}{30800}.
    3080\,(51-r)=30800\;\Rightarrow\;51-r=10
  4. Solve.
    r=41
r=41

Book answer. (i) 4, (ii) 5, (iii) 2, (iv) 8, (v) 2, (vi) 3, (vii) 41

4
How many 3-digit even numbers can be formed from the digits 1,2,3,4,5,6, if the digits are not repeated?
Solution
  1. Start with the place that has a restriction. The number is even, so the units digit must be even: 2, 4 or 6.
    \text{units: }3\text{ choices}
  2. The tens place can use any of the remaining 5 digits (one is already used).
    \text{tens: }5\text{ choices}
  3. The hundreds place can use any of the remaining 4 digits.
    \text{hundreds: }4\text{ choices}
  4. Multiply by the rule of product.
    3\times5\times4=60

The same count in permutation notation: 3\times{}^{5}P_{2}=3\times20=60.

60

Book answer. 60

5
How many 7-digits mobile number can be made using the digits 0 to 9, if each number starts with 5 and no digit is repeated?
Solution
  1. The first digit is fixed as 5. There is only 1 way for it.
    \text{1st digit: }1\text{ way}
  2. The other 6 places are filled from the 9 remaining digits (0,1,2,3,4,6,7,8,9), with no repetition and no other restriction (a mobile number may have 0 in any place). This is an arrangement of 6 out of 9 distinct digits.
    {}^{9}P_{6}=\dfrac{9!}{3!}
  3. Multiply out the six factors starting at 9.
    {}^{9}P_{6}=9\cdot8\cdot7\cdot6\cdot5\cdot4=60480
60480

Book answer. 60480

6
How many 4-digit numbers can be formed with the digits 1,2,3,4,5,6 when the repetition of the digits is allowed?
Solution
  1. Each of the four places can be filled with any of the 6 digits, because a digit may be used again.
    6\text{ choices for each place}
  2. Multiply the choices of the four places (rule of product).
    6\times6\times6\times6=6^{4}=1296
1296

Book answer. 1296

7
How many numbers can be formed with the digits 1,1,2,2,3,3,4 so that the even digits always occupy the even places, using all the digits and no digit is repeated?
Solution
  1. There are 7 digits, so the number has 7 places. The even places are the 2nd, 4th and 6th: three places. The odd places are the 1st, 3rd, 5th and 7th: four places.
    \text{even places: }2,4,6\qquad\text{odd places: }1,3,5,7
  2. The even digits are 2,2,4, three digits, so they exactly fill the three even places. Two of them are alike, so the number of arrangements is the permutation of 3 objects with 2 alike.
    \dfrac{3!}{2!}=3
  3. The remaining digits 1,1,3,3 fill the four odd places. Two pairs are alike.
    \dfrac{4!}{2!\,2!}=6
  4. The two choices are independent, so multiply.
    3\times6=18

Hence 18 numbers can be formed.

18

Book answer. 18

Note. "No digit is repeated" cannot mean that no digit is used twice, since 1,1,2,2,3,3 appear twice in the list. It is taken to mean that every given digit is used exactly as many times as it is listed.

8
In how many ways can a party of 4 men and 5 women be seated at a round table so that no two women are adjacent?
Solution
  1. Seat the men first. Four people at a round table can be seated in (4-1)! ways.
    (4-1)!=3!=6
  2. The four men leave exactly four gaps between neighbouring men (Figure). If no two women are to be adjacent, each gap may hold at most one woman.
    \text{gaps}=4
  3. But there are 5 women and only 4 gaps. By the pigeonhole principle, two women would have to share a gap and sit side by side.
    5>4
  4. So the required seating is impossible.
    \text{number of ways}=0
Four men seated round a table leave four gaps. Women who may not sit side by side need a gap each, so at most four women can be seated.
0

Book answer. 576

Note. The book prints 576=4!\times4! but the data of the question (4 men, 5 women, no two women adjacent) allow no seating at all, as the gap count shows. We could not reproduce 576 from any reading of the question. If the numbers were 5 men and 4 women, the answer would be 4!\times{}^{5}P_{4}=2880; for 4 men and 4 women alternating it would be 3!\times4!=144.

9
How many different signals can be made with 2 blue, 3 yellow and 4 green flags using all at a time?
Solution
  1. Total number of flags: 2+3+4=9. Flags of the same colour are alike, so this is a permutation of 9 objects with 2, 3 and 4 alike.
    n=9,\quad n_{1}=2,\ n_{2}=3,\ n_{3}=4
  2. Use \dfrac{n!}{n_{1}!\,n_{2}!\,n_{3}!}.
    \dfrac{9!}{2!\,3!\,4!}=\dfrac{9\cdot8\cdot7\cdot6\cdot5\cdot4!}{2\cdot6\cdot4!}
  3. Cancel 4! and divide.
    =\dfrac{15120}{12}=1260
1260

Book answer. 1260

10
How many words can be formed from the letters of the word FRIDAY? How many of them will end with F?
Solution
  1. FRIDAY has 6 letters, all different, so all of them can be arranged in 6! ways.
    6!=720
  2. For words ending with F, fix F in the last place (one way). The other 5 letters fill the first five places in 5! ways.
    1\times5!=120

So 720 words can be formed, and 120 of them end with F.

720\ \text{words};\ 120\ \text{end with F}

Book answer. 720; 120

11
How many different permutations of the word STATESMAN can be formed using all letters at a time?
Solution
  1. Count the letters of STATESMAN: S, T, A, T, E, S, M, A, N. There are 9 letters.
    n=9
  2. Find the repeated letters. S appears 2 times, T appears 2 times, A appears 2 times. E, M and N appear once each.
    n_{1}=n_{2}=n_{3}=2
  3. Use the permutation of objects that are alike.
    \dfrac{9!}{2!\,2!\,2!}=\dfrac{362880}{8}=45360
45360

Book answer. 45360

12
Find the number of arrangement of letters of the word VOWEL in which vowels may occupy odd places?
Solution
  1. VOWEL has 5 different letters: the vowels O, E and the consonants V, W, L. The places are 1,2,3,4,5. The odd places are 1,3,5 and the even places are 2,4.
    \text{total arrangements}=5!=120
  2. "Vowels may occupy odd places" means that at least one vowel is in an odd place. Count the opposite case and subtract it: both vowels in the two even places.
    \text{both vowels in even places: }2!\times3!=12
  3. The two vowels fill places 2 and 4 in 2! ways and the three consonants fill the remaining three places in 3! ways.
    \text{required}=120-12=108
108

Book answer. 108

Note. The wording is ambiguous. The book answer 108 matches the reading "at least one vowel in an odd place" (120-12), which is the reading used above.

13
In how many ways can letters of word MACHINE be arranged so that all the vowels are never together?
Solution
  1. MACHINE has 7 different letters. The vowels are A, I, E (three) and the consonants are M, C, H, N (four). All arrangements:
    7!=5040
  2. Count the arrangements in which all three vowels are together. Tie the vowels into one block. The block and the 4 consonants make 5 objects, arranged in 5! ways.
    5!=120
  3. Inside the block, the three vowels can be rearranged in 3! ways.
    3!=6\;\Rightarrow\;\text{vowels together}=120\times6=720
  4. The required number is the total minus the arrangements with the vowels together.
    5040-720=4320
4320

Book answer. 4320

14
How many 3 letter words (with or without meaning) can be formed out of the letter of the word ENGLISH, if the repetition of the letter is not allowed.
Solution
  1. ENGLISH has 7 different letters: E, N, G, L, I, S, H.
    n=7
  2. A 3-letter word is an arrangement of 3 of these letters, with no repetition.
    {}^{7}P_{3}=7\times6\times5=210
210

Book answer. 210

15
Fatima wants to arrange 5 Mathematics, 3 English and 2 Urdu books on book shelf. If the books on the same subjects are together, find all possible arrangements.
Solution
  1. Tie each subject together as one block. There are 3 blocks (Mathematics, English, Urdu). They can be placed on the shelf in 3! ways.
    3!=6
  2. Inside each block the books can be rearranged: 5 Mathematics books in 5! ways, 3 English in 3! ways, 2 Urdu in 2! ways.
    5!=120,\quad3!=6,\quad2!=2
  3. Multiply (rule of product).
    3!\times5!\times3!\times2!=6\times120\times6\times2=8640
8640

Book answer. 8640

16
How many odd numbers can be formed by using the digits 1,2,3,4,5,6 when repetition of digits is not allowed.
Solution
  1. Use all six digits, so each number has 6 digits. It is odd, so its units digit is 1, 3 or 5.
    \text{units: }3\text{ choices}
  2. The other five places are filled with the remaining 5 digits in 5! ways.
    5!=120
  3. Multiply.
    3\times120=360
360

Book answer. 360

Note. The question does not say how many digits the numbers have. The book answer 360 corresponds to numbers that use all six digits.

17
How many 4-digit odd numbers can be formed using the digits 1,2,3,4 and 5 if no digit is repeated.
Solution
  1. The number is odd, so the units digit is 1, 3 or 5.
    \text{units: }3\text{ choices}
  2. The other three places are filled from the remaining 4 digits, in order and without repetition.
    {}^{4}P_{3}=4\times3\times2=24
  3. Multiply.
    3\times24=72
72

Book answer. 72

18
How many odd numbers less than 10{,}000 can be formed using the digits 0,2,3,5,6 without repeating the digits.
Solution
  1. A number less than 10000 has 1, 2, 3 or 4 digits. It is odd, so its units digit is 3 or 5 (two choices). A number cannot begin with 0 (unless it is a one-digit number). Count each length separately.
  2. One-digit numbers: only 3 and 5.
    2
  3. Two-digit numbers: units 2 ways; the tens digit comes from the other 4 digits but not 0, so 3 ways.
    2\times3=6
  4. Three-digit numbers: units 2 ways; hundreds digit from the remaining digits except 0: 3 ways; tens digit from the 3 digits left (now 0 is allowed): 3 ways.
    2\times3\times3=18
  5. Four-digit numbers: units 2 ways; thousands digit 3 ways; hundreds digit 3 ways; tens digit 2 ways.
    2\times3\times3\times2=36
  6. Add the four cases.
    2+6+18+36=62
62

Book answer. 94

Note. The book key gives 94. We checked the count by listing all such numbers by computer (62 numbers: 2 one-digit, 6 two-digit, 18 three-digit, 36 four-digit) and could not find a reading of the question that gives 94. The answer 62 is for odd numbers below 10000 with distinct digits from \{0,2,3,5,6\}.

19
The chief secretary of Sindh calls a meeting of 10 secretaries. In how many ways they be seated at a round table if three particular secretaries want to sit together?
Solution
  1. Tie the three particular secretaries into one block. The block and the other 7 secretaries make 8 objects.
    7+1=8
  2. Arrange 8 objects round a table in (8-1)! ways.
    (8-1)!=7!=5040
  3. Inside the block the three secretaries can be arranged in 3! ways.
    3!=6
  4. Multiply.
    7!\times3!=5040\times6=30240
30240

Book answer. 30,240

20
Find the number of ways that 6 men and 6 women seated at a round table such that they occupy alternative seats.
Solution
  1. Seat the 6 men first at the round table: (6-1)! ways. This leaves 6 gaps, one between each pair of neighbouring men.
    (6-1)!=5!=120
  2. The 6 women sit in the 6 gaps, one in each, in 6! ways.
    6!=720
  3. Multiply.
    5!\times6!=120\times720=86400
86400

Book answer. 86400

21
Make all the permutations of the following words: WHY, SAD, TWO, MADE.
Solution
  1. WHY, SAD and TWO have 3 different letters each, so each has 3! permutations.
    3!=6
  2. MADE has 4 different letters, so it has 4! permutations.
    4!=24
  3. List them systematically: fix the first letter, then arrange the rest.
The 6 permutations of each three-letter word.
WHYSADTWO
WHYSADTWO
WYHSDATOW
HWYASDWTO
HYWADSWOT
YWHDSAOTW
YHWDASOWT
The 24 permutations of MADE, grouped by first letter (6 in each group).
Starts with AStarts with DStarts with EStarts with M
ADEMDAEMEADMMADE
ADMEDAMEEAMDMAED
AEDMDEAMEDAMMDAE
AEMDDEMAEDMAMDEA
AMDEDMAEEMADMEAD
AMEDDMEAEMDAMEDA
6,\ 6,\ 6,\ 24\ \text{permutations}

Book answer. 6, 6, 6, 24

22
Encrypt the word LAHORE by using the permutation (3\ 4\ 6\ 1\ 5\ 2). By labelling L as 1, A as 2 and so on.
Solution

Label the letters in the order of the word, as the question says.

LetterLAHORE
Label123456
  1. As in the book example (PAK with the permutation (2\ 1\ 3) gives APK), the permutation lists the labels of the letters in the order in which they are written in the encrypted word. So write the letters with labels 3,4,6,1,5,2 in that order.
    3\to\text{H},\ 4\to\text{O},\ 6\to\text{E},\ 1\to\text{L},\ 5\to\text{R},\ 2\to\text{A}
  2. Put the letters side by side.
    \text{LAHORE}\ \longrightarrow\ \text{HOELRA}
\text{HOELRA}

Book answer. HOELRA

23
Decrypt the word "TNLUMA" by using the permutation (4\ 6\ 3\ 2\ 1\ 5).
Solution
  1. The permutation gives the label of each letter of the encrypted word, in order. Match them up.
    \text{T}\to4,\ \text{N}\to6,\ \text{L}\to3,\ \text{U}\to2,\ \text{M}\to1,\ \text{A}\to5
  2. To decrypt, write the letters in the order of their labels 1,2,3,4,5,6, as the book does with APK (2\ 1\ 3)\to PAK.
    1\to\text{M},\ 2\to\text{U},\ 3\to\text{L},\ 4\to\text{T},\ 5\to\text{A},\ 6\to\text{N}
  3. Read the letters in order.
    \text{TNLUMA}\ \longrightarrow\ \text{MULTAN}
\text{MULTAN}

Book answer. MULTAN

Note. The book prints the permutation without its closing bracket, and its answer key numbers both cryptography answers as "22" (HOELRA is for Question 22 and MULTAN for Question 23).

Exercise 6.3p. 172–173

Combinations {}^{n}C_{r}=\dfrac{n!}{r!\,(n-r)!}, used when order does not matter. Key tools: {}^{n}C_{r}={}^{n}C_{n-r}, Pascal rule {}^{n}C_{r}+{}^{n}C_{r-1}={}^{n+1}C_{r}, the ratio {}^{n}C_{r}\div{}^{n}C_{r-1}=\dfrac{n-r+1}{r}, and for committees: choose each group separately and multiply, or subtract the unwanted cases from the total.

12025 Annual I, Set B, Q.2 (ii) OR
Prove the following for n\in\mathbb{N}.
Solution
(i) {}^{n}C_{r}=\dfrac{n!}{r!\,(n-r)!}
  1. Let X={}^{n}C_{r} be the number of ways of choosing r objects out of n distinct objects, with no regard to order.
  2. Each chosen group of r objects can be arranged among itself in r! ways. So every combination gives r! permutations.
    r!\cdot X=\text{number of permutations of }r\text{ out of }n
  3. The number of permutations of r objects out of n is {}^{n}P_{r}.
    r!\,X={}^{n}P_{r}=\dfrac{n!}{(n-r)!}
  4. Divide by r!.
    {}^{n}C_{r}=X=\dfrac{n!}{r!\,(n-r)!}

Hence proved. This is the proof of the book (Section 6.4.1).

(ii) n\cdot{}^{n-1}C_{r-1}=(n-r+1)\,{}^{n}C_{r-1}
  1. Write the left side with the formula. For {}^{n-1}C_{r-1} the denominator is (r-1)!\,[(n-1)-(r-1)]!=(r-1)!\,(n-r)!.
    n\cdot{}^{n-1}C_{r-1}=\dfrac{n\,(n-1)!}{(r-1)!\,(n-r)!}=\dfrac{n!}{(r-1)!\,(n-r)!}
  2. Write the right side with the formula. For {}^{n}C_{r-1} the denominator is (r-1)!\,(n-r+1)!. Expand (n-r+1)!=(n-r+1)\,(n-r)!.
    (n-r+1)\,{}^{n}C_{r-1}=\dfrac{(n-r+1)\,n!}{(r-1)!\,(n-r+1)\,(n-r)!}=\dfrac{n!}{(r-1)!\,(n-r)!}
  3. The two expressions are the same.
    \text{LHS}=\text{RHS}

Hence proved.

(iii) r\,{}^{n}C_{r}=(n-r+1)\,{}^{n}C_{r-1}
  1. Left side: expand r!=r\,(r-1)! and cancel r.
    r\,{}^{n}C_{r}=\dfrac{r\,n!}{r!\,(n-r)!}=\dfrac{n!}{(r-1)!\,(n-r)!}
  2. Right side: as in part (ii).
    (n-r+1)\,{}^{n}C_{r-1}=\dfrac{(n-r+1)\,n!}{(r-1)!\,(n-r+1)!}=\dfrac{n!}{(r-1)!\,(n-r)!}
  3. The two are equal.
    \text{LHS}=\text{RHS}

Hence proved.

(iv) {}^{n-1}C_{r-1}+{}^{n-1}C_{r}={}^{n}C_{r}
  1. Write both terms with the formula.
    {}^{n-1}C_{r-1}=\dfrac{(n-1)!}{(r-1)!\,(n-r)!},\qquad{}^{n-1}C_{r}=\dfrac{(n-1)!}{r!\,(n-1-r)!}
  2. Use the common denominator r!\,(n-r)!. Since r!=r\,(r-1)! and (n-r)!=(n-r)\,(n-r-1)!, the numerators become r\,(n-1)! and (n-r)\,(n-1)!.
    {}^{n-1}C_{r-1}=\dfrac{r\,(n-1)!}{r!\,(n-r)!},\qquad{}^{n-1}C_{r}=\dfrac{(n-r)\,(n-1)!}{r!\,(n-r)!}
  3. Add and take out (n-1)!.
    \text{LHS}=\dfrac{(n-1)!\,\bigl[r+(n-r)\bigr]}{r!\,(n-r)!}=\dfrac{n\,(n-1)!}{r!\,(n-r)!}
  4. Use n\,(n-1)!=n!.
    =\dfrac{n!}{r!\,(n-r)!}={}^{n}C_{r}

Hence proved.

(v) {}^{n}C_{r}+{}^{n}C_{r-1}={}^{n+1}C_{r}
  1. This is part (iv) with n replaced by n+1. Part (iv) is true for every natural number, so it holds with n+1 in place of n.
    {}^{(n+1)-1}C_{r-1}+{}^{(n+1)-1}C_{r}={}^{n+1}C_{r}
  2. Simplify (n+1)-1=n and reorder the two terms.
    {}^{n}C_{r-1}+{}^{n}C_{r}={}^{n+1}C_{r}

Hence proved.

(vi) {}^{2n}C_{n}=\dfrac{2^{n}\,[1\cdot3\cdot5\cdots(2n-1)]}{n!}
  1. Use the formula with n replaced by 2n and r=n.
    {}^{2n}C_{n}=\dfrac{(2n)!}{n!\,(2n-n)!}=\dfrac{(2n)!}{n!\,n!}
  2. By Exercise 6.1, Question 4(i): \dfrac{(2n)!}{n!}=2^{n}\bigl(1\cdot3\cdot5\cdots(2n-1)\bigr).
    \dfrac{(2n)!}{n!}=2^{n}\,[1\cdot3\cdot5\cdots(2n-1)]
  3. Divide this by the second n!.
    {}^{2n}C_{n}=\dfrac{2^{n}\,[1\cdot3\cdot5\cdots(2n-1)]}{n!}

Hence proved.

(vii) {}^{n}C_{p}={}^{n}C_{q}\;\Rightarrow\;p=q or p+q=n
  1. If p=q there is nothing to prove. Suppose p\ne q, say p<q (the case q<p is the same with p,q swapped).
  2. Put the formula on both sides and cancel n!.
    \dfrac{n!}{p!\,(n-p)!}=\dfrac{n!}{q!\,(n-q)!}\;\Rightarrow\;q!\,(n-q)!=p!\,(n-p)!
  3. Collect the factorials with the same sense on each side. Expand q! down to p! and (n-p)! down to (n-q)!.
    \dfrac{q!}{p!}=\dfrac{(n-p)!}{(n-q)!}\;\Rightarrow\;(p+1)(p+2)\cdots q=(n-q+1)(n-q+2)\cdots(n-p)
  4. Both sides are products of the same number q-p of consecutive positive integers. Such a product grows strictly when the starting integer grows (every factor gets larger). So the two products can be equal only if they start at the same integer.
    p+1=n-q+1
  5. Solve.
    p+q=n

Hence {}^{n}C_{p}={}^{n}C_{q} implies p=q or p+q=n. (The second case is the symmetry rule {}^{n}C_{r}={}^{n}C_{n-r}.)

(viii) {}^{n}C_{r}+2\,{}^{n}C_{r-1}+{}^{n}C_{r-2}={}^{n+2}C_{r}
  1. Split the middle term as {}^{n}C_{r-1}+{}^{n}C_{r-1} and regroup.
    \text{LHS}=\bigl[{}^{n}C_{r}+{}^{n}C_{r-1}\bigr]+\bigl[{}^{n}C_{r-1}+{}^{n}C_{r-2}\bigr]
  2. Apply part (v) to each bracket. The second bracket is part (v) with r replaced by r-1.
    =\,{}^{n+1}C_{r}+{}^{n+1}C_{r-1}
  3. Apply part (v) again, now with n+1 in place of n.
    =\,{}^{n+2}C_{r}=\text{RHS}

Hence proved.

(ix) r\,{}^{n}C_{r}=n\,{}^{n-1}C_{r-1}
  1. Left side: r!=r\,(r-1)!, so the factor r cancels.
    r\,{}^{n}C_{r}=\dfrac{r\,n!}{r!\,(n-r)!}=\dfrac{n!}{(r-1)!\,(n-r)!}
  2. Right side: n\,(n-1)!=n! and (n-1)-(r-1)=n-r.
    n\,{}^{n-1}C_{r-1}=\dfrac{n\,(n-1)!}{(r-1)!\,(n-r)!}=\dfrac{n!}{(r-1)!\,(n-r)!}
  3. The two are equal.
    \text{LHS}=\text{RHS}

Hence proved.

(x) The product of k consecutive integers is divisible by k!.
  1. First take k consecutive positive integers m+1,\ m+2,\ \dots,\ m+k (where m\ge0). Their product is a quotient of two factorials.
    (m+1)(m+2)\cdots(m+k)=\dfrac{(m+k)!}{m!}
  2. Multiply and divide by k! to bring in a combination.
    \dfrac{(m+k)!}{m!}=k!\cdot\dfrac{(m+k)!}{k!\,m!}=k!\cdot{}^{m+k}C_{k}
  3. {}^{m+k}C_{k} counts the ways of choosing k objects from m+k, so it is a whole number. Hence the product is k! times a whole number.
    \text{divisible by }k!
  4. If the integers include 0 the product is 0, which is divisible by k!. If they are all negative, the product is (-1)^{k} times the product of k consecutive positive integers, so it is divisible by k! as well.

Hence proved.

2
Find n, if:
Solution
(i) {}^{n}C_{5}={}^{n}C_{8}
  1. The two values of r are different, so by Question 1(vii), {}^{n}C_{p}={}^{n}C_{q} gives p+q=n.
    n=5+8
  2. Add.
    n=13

Check: {}^{13}C_{5}=1287={}^{13}C_{8}.

n=13
(ii) {}^{n}C_{15}={}^{n}C_{7}
  1. 15\ne7, so 15+7=n by Question 1(vii).
    n=15+7=22

Check: {}^{22}C_{15}={}^{22}C_{7}=170544.

n=22
(iii) {}^{n}C_{50}={}^{n}C_{1}
  1. 50\ne1, so 50+1=n by Question 1(vii).
    n=51

Check: {}^{51}C_{50}=51={}^{51}C_{1}.

n=51
(iv) {}^{2n}C_{3}:{}^{n}C_{3}=11:1
  1. Write both combinations as products over 3!.
    {}^{2n}C_{3}=\dfrac{2n(2n-1)(2n-2)}{3!},\qquad{}^{n}C_{3}=\dfrac{n(n-1)(n-2)}{3!}
  2. Divide. The 3! cancels. Write 2n-2=2(n-1) and cancel n(n-1).
    \dfrac{2n(2n-1)\cdot2(n-1)}{n(n-1)(n-2)}=\dfrac{4(2n-1)}{n-2}
  3. The ratio 11:1 means the quotient is 11.
    4(2n-1)=11(n-2)
  4. Expand and solve.
    8n-4=11n-22\;\Rightarrow\;3n=18\;\Rightarrow\;n=6

Check: {}^{12}C_{3}=220 and {}^{6}C_{3}=20, and 220\div20=11.

n=6
(v) {}^{n}C_{6}:{}^{n-3}C_{3}=33:4
  1. Use the formula on both. For {}^{n-3}C_{3} the factorial is [(n-3)-3]!=(n-6)!.
    {}^{n}C_{6}=\dfrac{n!}{6!\,(n-6)!},\qquad{}^{n-3}C_{3}=\dfrac{(n-3)!}{3!\,(n-6)!}
  2. Divide. The (n-6)! cancels.
    \dfrac{n!}{6!\,(n-6)!}\cdot\dfrac{3!\,(n-6)!}{(n-3)!}=\dfrac{n!}{(n-3)!}\cdot\dfrac{3!}{6!}
  3. Use \dfrac{n!}{(n-3)!}=n(n-1)(n-2) and \dfrac{3!}{6!}=\dfrac{1}{120}, then equate to \dfrac{33}{4}.
    \dfrac{n(n-1)(n-2)}{120}=\dfrac{33}{4}
  4. Cross-multiply.
    n(n-1)(n-2)=\dfrac{33\times120}{4}=990
  5. Factorise 990=11\cdot10\cdot9. Three consecutive integers, so n=11.
    n=11

Check: {}^{11}C_{6}=462 and {}^{8}C_{3}=56, and \dfrac{462}{56}=\dfrac{33}{4}.

n=11
(vi) {}^{2n}C_{3}:{}^{n}C_{2}=12:1
  1. Write both as products.
    {}^{2n}C_{3}=\dfrac{2n(2n-1)\cdot2(n-1)}{6},\qquad{}^{n}C_{2}=\dfrac{n(n-1)}{2}
  2. Divide and cancel n(n-1).
    \dfrac{4n(n-1)(2n-1)}{6}\cdot\dfrac{2}{n(n-1)}=\dfrac{4(2n-1)}{3}
  3. The ratio 12:1 means the quotient is 12.
    4(2n-1)=36\;\Rightarrow\;2n-1=9
  4. Solve.
    n=5

Check: {}^{10}C_{3}=120 and {}^{5}C_{2}=10, and 120\div10=12.

n=5

Book answer. (i) 13, (ii) 22, (iii) 51, (iv) 6, (v) 11, (vi) 5

3
Find r, if:
Solution
(i) {}^{15}C_{3r}={}^{15}C_{r+3}
  1. By Question 1(vii), equal combinations mean either the lower numbers are equal or they add up to 15.
    3r=r+3\quad\text{or}\quad3r+(r+3)=15
  2. First case: 2r=3 gives r=\tfrac32, which is not a whole number, so it is rejected.
    r=\dfrac32
  3. Second case.
    4r+3=15\;\Rightarrow\;4r=12\;\Rightarrow\;r=3

Check: {}^{15}C_{9}={}^{15}C_{6}=5005.

r=3
(ii) {}^{8}C_{r}-{}^{7}C_{3}={}^{7}C_{2}
  1. Move {}^{7}C_{3} to the right side.
    {}^{8}C_{r}={}^{7}C_{3}+{}^{7}C_{2}
  2. Use {}^{n}C_{r}+{}^{n}C_{r-1}={}^{n+1}C_{r} (Question 1(v)) with n=7 and r=3.
    {}^{7}C_{3}+{}^{7}C_{2}={}^{8}C_{3}
  3. So {}^{8}C_{r}={}^{8}C_{3}. Either r=3, or r+3=8.
    r=3\quad\text{or}\quad r=5

Check: {}^{8}C_{3}={}^{8}C_{5}=56 and 35+21=56.

r=3\ \text{or}\ r=5
(iii) {}^{16}C_{r}={}^{16}C_{r+4}
  1. The lower numbers r and r+4 cannot be equal, so they must add up to 16.
    r+(r+4)=16
  2. Solve.
    2r=12\;\Rightarrow\;r=6

Check: {}^{16}C_{6}={}^{16}C_{10}=8008.

r=6
(iv) {}^{15}C_{r}:{}^{15}C_{r-1}=11:5
  1. Use the ratio of neighbouring combinations (derived under Question 4 below): {}^{n}C_{r}\div{}^{n}C_{r-1}=\dfrac{n-r+1}{r}.
    \dfrac{{}^{15}C_{r}}{{}^{15}C_{r-1}}=\dfrac{15-r+1}{r}=\dfrac{16-r}{r}
  2. Equate to \dfrac{11}{5} and cross-multiply.
    \dfrac{16-r}{r}=\dfrac{11}{5}\;\Rightarrow\;80-5r=11r
  3. Solve.
    16r=80\;\Rightarrow\;r=5

Check: {}^{15}C_{5}=3003 and {}^{15}C_{4}=1365, and \dfrac{3003}{1365}=\dfrac{11}{5}.

r=5

Book answer. (i) 3, (ii) 3, (iii) 6, (iv) 5

Note. In part (ii) the equation {}^{8}C_{r}=56 has two solutions, r=3 and r=5, because {}^{8}C_{3}={}^{8}C_{5}=56. The book key lists only r=3.

4
Find n and r, if:
Solution

Method. Three combinations in a ratio give two equations in n and r. For two neighbouring combinations the factorials almost cancel:

\dfrac{{}^{n}C_{r}}{{}^{n}C_{r-1}}=\dfrac{n!}{r!\,(n-r)!}\cdot\dfrac{(r-1)!\,(n-r+1)!}{n!}=\dfrac{n-r+1}{r},\qquad\dfrac{{}^{n}C_{r+1}}{{}^{n}C_{r}}=\dfrac{n-r}{r+1}

Use these two ratios to get two linear equations, then solve them together.

(i) {}^{n}C_{r-1}:{}^{n}C_{r}:{}^{n}C_{r+1}=6:14:21
  1. From the first two terms, \dfrac{{}^{n}C_{r}}{{}^{n}C_{r-1}}=\dfrac{14}{6}=\dfrac73.
    \dfrac{n-r+1}{r}=\dfrac73\;\Rightarrow\;3n-3r+3=7r\;\Rightarrow\;3n=10r-3\quad(1)
  2. From the last two terms, \dfrac{{}^{n}C_{r+1}}{{}^{n}C_{r}}=\dfrac{21}{14}=\dfrac32.
    \dfrac{n-r}{r+1}=\dfrac32\;\Rightarrow\;2n-2r=3r+3\;\Rightarrow\;2n=5r+3\quad(2)
  3. Eliminate n: multiply (1) by 2 and (2) by 3, so both sides give 6n.
    2(10r-3)=3(5r+3)\;\Rightarrow\;20r-6=15r+9
  4. Solve for r, then put it in (2).
    r=3,\qquad2n=5(3)+3=18\;\Rightarrow\;n=9

Check: {}^{9}C_{2}:{}^{9}C_{3}:{}^{9}C_{4}=36:84:126=6:14:21.

n=9,\ r=3
(ii) {}^{n}C_{r-1}:{}^{n}C_{r}:{}^{n}C_{r+1}=3:4:5
  1. First two terms: \dfrac{{}^{n}C_{r}}{{}^{n}C_{r-1}}=\dfrac43.
    \dfrac{n-r+1}{r}=\dfrac43\;\Rightarrow\;3n-3r+3=4r\;\Rightarrow\;3n=7r-3\quad(1)
  2. Last two terms: \dfrac{{}^{n}C_{r+1}}{{}^{n}C_{r}}=\dfrac54.
    \dfrac{n-r}{r+1}=\dfrac54\;\Rightarrow\;4n-4r=5r+5\;\Rightarrow\;4n=9r+5\quad(2)
  3. Eliminate n: multiply (1) by 4 and (2) by 3, so both sides give 12n.
    4(7r-3)=3(9r+5)\;\Rightarrow\;28r-12=27r+15
  4. Solve for r, then put it in (1).
    r=27,\qquad3n=7(27)-3=186\;\Rightarrow\;n=62

Check: \dfrac{{}^{62}C_{27}}{{}^{62}C_{26}}=\dfrac{36}{27}=\dfrac43 and \dfrac{{}^{62}C_{28}}{{}^{62}C_{27}}=\dfrac{35}{28}=\dfrac54.

n=62,\ r=27
(iii) {}^{n+1}C_{r+1}:{}^{n}C_{r}:{}^{n-1}C_{r-1}=22:12:6
  1. Find the ratio of the first two. By the formula, {}^{n+1}C_{r+1}=\dfrac{(n+1)!}{(r+1)!\,(n-r)!} and {}^{n}C_{r}=\dfrac{n!}{r!\,(n-r)!}, so the quotient is \dfrac{n+1}{r+1}.
    \dfrac{n+1}{r+1}=\dfrac{22}{12}=\dfrac{11}{6}\;\Rightarrow\;6n+6=11r+11\quad(1)
  2. Ratio of the last two. By Question 1(ix), r\,{}^{n}C_{r}=n\,{}^{n-1}C_{r-1}, so {}^{n}C_{r}\div{}^{n-1}C_{r-1}=\dfrac{n}{r}.
    \dfrac{n}{r}=\dfrac{12}{6}=2\;\Rightarrow\;n=2r\quad(2)
  3. Put n=2r from (2) into (1).
    6(2r)+6=11r+11\;\Rightarrow\;r=5
  4. Then n=2r.
    n=10

Check: {}^{11}C_{6}:{}^{10}C_{5}:{}^{9}C_{4}=462:252:126=22:12:6.

n=10,\ r=5
(iv) {}^{n}C_{r}:{}^{n}C_{r+1}:{}^{n}C_{r+2}=1:2:3
  1. First two terms: \dfrac{{}^{n}C_{r+1}}{{}^{n}C_{r}}=\dfrac21.
    \dfrac{n-r}{r+1}=2\;\Rightarrow\;n-r=2r+2\;\Rightarrow\;n=3r+2\quad(1)
  2. Last two terms: \dfrac{{}^{n}C_{r+2}}{{}^{n}C_{r+1}}=\dfrac32. The ratio formula with r+1 in place of r is \dfrac{n-(r+1)}{r+2}.
    \dfrac{n-r-1}{r+2}=\dfrac32\;\Rightarrow\;2n-2r-2=3r+6\;\Rightarrow\;2n=5r+8\quad(2)
  3. Put n=3r+2 from (1) into (2).
    2(3r+2)=5r+8\;\Rightarrow\;6r+4=5r+8\;\Rightarrow\;r=4
  4. Then from (1).
    n=3(4)+2=14

Check: {}^{14}C_{4}:{}^{14}C_{5}:{}^{14}C_{6}=1001:2002:3003=1:2:3.

n=14,\ r=4

Book answer. (i) 9; 3, (ii) 62; 27, (iii) 10; 5, (iv) 14; 4

5
In how many ways can 11 players be chosen out of 16 if
Solution
(i) there is no restriction.
  1. The order of choosing players does not matter, so use combinations of 11 out of 16.
    {}^{16}C_{11}
  2. Use {}^{n}C_{r}={}^{n}C_{n-r} to get smaller numbers: {}^{16}C_{11}={}^{16}C_{5}.
    {}^{16}C_{5}=\dfrac{16\cdot15\cdot14\cdot13\cdot12}{5\cdot4\cdot3\cdot2\cdot1}=\dfrac{524160}{120}=4368
4368
(ii) a particular player is always chosen.
  1. The particular player is already in the team, so only the other 10 places remain. They are filled from the other 15 players.
    {}^{15}C_{10}
  2. Use symmetry: {}^{15}C_{10}={}^{15}C_{5}.
    {}^{15}C_{5}=\dfrac{15\cdot14\cdot13\cdot12\cdot11}{5\cdot4\cdot3\cdot2\cdot1}=\dfrac{360360}{120}=3003
3003

Book answer. (i) 4368, (ii) 3003

6
Out of 5 men and 3 women, a committee of 3 is to be formed. In how many ways can it be formed if at least one man is selected?
Solution
  1. There are 5+3=8 persons. All committees of 3:
    {}^{8}C_{3}=\dfrac{8\cdot7\cdot6}{3\cdot2\cdot1}=56
  2. "At least one man" fails only when no man is chosen, that is, all 3 are women. There is only one such committee (all three women).
    {}^{3}C_{3}=1
  3. Subtract the unwanted committees from the total.
    56-1=55

Check by adding the cases: 1 man and 2 women: {}^{5}C_{1}\cdot{}^{3}C_{2}=15; 2 men and 1 woman: {}^{5}C_{2}\cdot{}^{3}C_{1}=30; 3 men: {}^{5}C_{3}=10. Total 15+30+10=55.

55

Book answer. 55

7
A committee of 5 members is to be formed out of 6 men and 4 women. In how many ways can it be done if it has
Solution
(i) exactly 2 women
  1. Exactly 2 women means 2 women and 3 men. Choose the women and the men separately, then multiply.
    {}^{4}C_{2}\times{}^{6}C_{3}
  2. Evaluate.
    6\times20=120
120
(ii) at least 2 women
  1. All committees of 5 out of 10 people:
    {}^{10}C_{5}=252
  2. The unwanted cases are 0 women (all 5 men) and 1 woman (with 4 men).
    {}^{4}C_{0}\,{}^{6}C_{5}=6,\qquad{}^{4}C_{1}\,{}^{6}C_{4}=4\times15=60
  3. Subtract.
    252-(6+60)=186

Check by adding the wanted cases: 2 women 120, 3 women {}^{4}C_{3}\,{}^{6}C_{2}=60, 4 women {}^{4}C_{4}\,{}^{6}C_{1}=6. Total 120+60+6=186.

186
(iii) at most 2 women
  1. At most 2 women means 0, 1 or 2 women. Find each case.
    0\text{ women: }{}^{6}C_{5}=6;\quad1\text{ woman: }{}^{4}C_{1}\,{}^{6}C_{4}=60;\quad2\text{ women: }{}^{4}C_{2}\,{}^{6}C_{3}=120
  2. Add the three cases (they cannot overlap).
    6+60+120=186
186

Book answer. (i) 120, (ii) 186, (iii) 186

8
There are 10 points on a circle. Find the number of (i) lines (ii) triangles that can be drawn?
Solution
(i) lines
  1. A line is fixed by any 2 of the points, and the line through A and B is the same as the line through B and A. So the order does not matter: use combinations.
    {}^{10}C_{2}
  2. Evaluate.
    \dfrac{10\cdot9}{2\cdot1}=45
45
(ii) triangles
  1. A triangle is fixed by any 3 of the points. Three points on a circle are never in a straight line, so every choice of 3 gives a triangle. Order does not matter.
    {}^{10}C_{3}
  2. Evaluate.
    \dfrac{10\cdot9\cdot8}{3\cdot2\cdot1}=120
Ten points on a circle. Every pair joins to give a line and every triple gives a triangle (one triangle is drawn). No three points lie on one straight line.
120

Book answer. (i) 45, (ii) 120

9
Find the number of diagonals in n sided polygon?
Solution
  1. A polygon with n sides has n vertices. Joining any 2 vertices gives a line segment.
    {}^{n}C_{2}=\dfrac{n(n-1)}{2}
  2. Among these segments, the n sides of the polygon are not diagonals. Subtract them.
    \text{diagonals}={}^{n}C_{2}-n
  3. Simplify.
    \dfrac{n(n-1)}{2}-n=\dfrac{n(n-1)-2n}{2}=\dfrac{n(n-3)}{2}

Check with a square (n=4): \dfrac{4\cdot1}{2}=2 diagonals.

{}^{n}C_{2}-n=\dfrac{n(n-3)}{2}

Book answer. ^nC_2-n

10
In how many ways a group of 10 girls can be divided into two groups of 3 and 7.
Solution
  1. Choose the 3 girls for the smaller group. The other 7 girls then form the second group automatically.
    {}^{10}C_{3}
  2. Evaluate. (Choosing 7 first would give {}^{10}C_{7}={}^{10}C_{3}, the same number.)
    \dfrac{10\cdot9\cdot8}{3\cdot2\cdot1}=120
120

Book answer. 120

11
Number of diagonals in n-sided polygon is 35. Find the number n?
Solution
  1. Use the number of diagonals of an n-sided polygon from Question 9.
    \dfrac{n(n-3)}{2}=35
  2. Cross-multiply.
    n(n-3)=70\;\Rightarrow\;n^{2}-3n-70=0
  3. Factorise: two numbers with product -70 and sum -3 are -10 and 7.
    (n-10)(n+7)=0\;\Rightarrow\;n=10\ \text{or}\ n=-7
  4. The number of sides is positive, so n=10.
    n=10

Check: a decagon has \dfrac{10\cdot7}{2}=35 diagonals.

n=10

Book answer. 10

12
For the post of 6 officers, there are 100 applicants, 2 posts are reserved for serving candidates and remaining for others. There are 20 serving candidates among the applicants. In how many ways this selection can be made?
Solution
  1. Applicants: 20 serving candidates and 100-20=80 others.
    20+80=100
  2. Two posts are reserved for serving candidates. Choose 2 from the 20 serving candidates.
    {}^{20}C_{2}=\dfrac{20\cdot19}{2}=190
  3. The remaining 6-2=4 posts are for the others. Choose 4 from the 80 other applicants.
    {}^{80}C_{4}=\dfrac{80\cdot79\cdot78\cdot77}{4\cdot3\cdot2\cdot1}=1581580
  4. The two selections are independent, so multiply.
    190\times1581580=300500200
{}^{20}C_{2}\times{}^{80}C_{4}=300500200

Book answer. 300500200

Note. The question does not say who may fill the four open posts. The book answer 300500200 takes them from the 80 non-serving applicants, which is the reading used here.

13
In an examination, a candidate has to pass in each of 6 subjects. In how many ways he cannot qualify the examination?
Solution
  1. In each subject the candidate either passes or fails: 2 possible results. For 6 subjects, the rule of product gives all possible combinations of results.
    2^{6}=64
  2. The candidate qualifies only if he passes in all 6 subjects. This is exactly 1 of the outcomes.
    1
  3. In every other outcome he fails in at least one subject and cannot qualify.
    64-1=63

Check by counting the number of failed subjects: \sum_{k=1}^{6}{}^{6}C_{k}=6+15+20+15+6+1=63.

63

Book answer. 63

14
A question paper has three parts A, B and C each containing 8 questions. If a student has to choose 5 questions from A, and 3 questions each from B and C. In how many ways can he choose the questions?
Solution
  1. Choose 5 questions out of the 8 in part A.
    {}^{8}C_{5}={}^{8}C_{3}=\dfrac{8\cdot7\cdot6}{6}=56
  2. Choose 3 questions out of the 8 in part B.
    {}^{8}C_{3}=56
  3. Choose 3 questions out of the 8 in part C.
    {}^{8}C_{3}=56
  4. The three choices are independent, so multiply.
    56\times56\times56=175616
{}^{8}C_{5}\times{}^{8}C_{3}\times{}^{8}C_{3}=175616

Book answer. 175616

Review Exercise 6p. 174

Revision of the whole unit: permutations and combinations of distinct objects, objects that are alike, circular arrangements, the key-chain case, and basic counting.

1 (i)
If 3\,{}^{n}P_{3}={}^{n}P_{4} then value of n is:
  1. A5
  2. B6Answer
  3. C7
  4. D8
Why
  1. Write both permutations as products of consecutive factors.
    3\,n(n-1)(n-2)=n(n-1)(n-2)(n-3)
  2. Cancel n(n-1)(n-2) (not zero, since {}^{n}P_{4} needs n\ge4).
    3=n-3\;\Rightarrow\;n=6

Check: 3\,{}^{6}P_{3}=3\times120=360={}^{6}P_{4}. For n=5 the left side is 180 but {}^{5}P_{4}=120, so option (a) fails.

Book answer. b

1 (ii)2026 Annual I, Set D, MCQ 19
Number of ways of arrangement of the word "GARDEN":
  1. A480
  2. B600
  3. C720Answer
  4. D840
Why

GARDEN has 6 letters G, A, R, D, E, N, all different, so they can be arranged in 6!=720 ways.

The values 480, 600 and 840 are not factorials of any number, so they cannot be the count of arranging 6 different letters. (840=\dfrac{7!}{3!} would be for a different word.)

Book answer. c

1 (iii)
The product of r consecutive positive numbers is divisible by:
  1. Ar!Answer
  2. B(r+1)!
  3. Cr!+1
  4. D2r!
Why

The product (m+1)(m+2)\cdots(m+r)=\dfrac{(m+r)!}{m!}=r!\cdot{}^{m+r}C_{r}, which is r! times a whole number (Exercise 6.3, Question 1(x)). So it is divisible by r!.

It need not be divisible by the others. For r=2 and the numbers 1,2: the product is 2, which is not divisible by (r+1)!=6, by r!+1=3 or by 2r!=4.

Book answer. a

1 (iv)
The total number of 6-digit number in which all the odd and only odd digits appear is:
  1. A\dfrac52\,6!Answer
  2. B6!
  3. C\dfrac12\,6!
  4. D\dfrac32\,6!
Why
  1. There are 5 odd digits: 1,3,5,7,9. A 6-digit number using all of them and only odd digits has 6 places for 5 digits, so exactly one odd digit is used twice.
  2. Choose the digit that is repeated.
    5\text{ ways}
  3. Arrange the 6 digits, of which two are alike. (No leading zero problem: 0 is not an odd digit.)
    \dfrac{6!}{2!}
  4. Multiply.
    5\times\dfrac{6!}{2!}=\dfrac52\,6!=1800

Book answer. a

1 (v)
Let A=\{1,2,3,\dots,20\}. Find the number of ways that the integer chosen is a prime number is:
  1. A3
  2. B5
  3. C7
  4. D8Answer
Why

List the primes in A: 2,3,5,7,11,13,17,19. There are 8 of them, so there are 8 ways of choosing a prime. (1 is not a prime.)

Book answer. d

1 (vi)
From A=\{1,3,5,7,9\} and B=\{2,4,6,8\} if a cartesian product A\times B is chosen, then the number of ways that a+b=9 is:
  1. A0
  2. B2
  3. C3
  4. D4Answer
Why

Pairs (a,b)\in A\times B with a+b=9 means b=9-a. Test each a: 1\to8, 3\to6, 5\to4, 7\to2 all lie in B; 9\to0 does not.

(1,8),\ (3,6),\ (5,4),\ (7,2)

There are 4 such pairs.

Book answer. d

1 (vii)
A student has to answer 10 out of 12 questions in an examination such that he must choose at least 4 from first five questions. The number of choices is:
  1. A30
  2. B35Answer
  3. C40
  4. D45
Why
  1. "At least 4 of the first five" means exactly 4 or exactly 5 of the first five. The other 7 questions supply the rest of the 10.
  2. Exactly 4 from the first five and 6 from the last seven.
    {}^{5}C_{4}\times{}^{7}C_{6}=5\times7=35
  3. Exactly 5 from the first five and 5 from the last seven.
    {}^{5}C_{5}\times{}^{7}C_{5}=1\times21=21
  4. Add the two cases.
    35+21=56

Option (b), 35, is the count of the first case only. It is the book key.

Book answer. b

Note. Counting both allowed cases gives 56, which is not among the options. The book key (b) =35 counts only "exactly 4 from the first five". Option (b) is the closest listed choice and is the book answer.

1 (viii)
If {}^{n}C_{4}={}^{n}C_{10} then value of n is:
  1. A10
  2. B12
  3. C13
  4. D14Answer
Why

Since 4\ne10, equal combinations mean the lower numbers add up to n (Exercise 6.3, Question 1(vii), or {}^{n}C_{r}={}^{n}C_{n-r}).

n=4+10=14

Check: {}^{14}C_{4}=1001={}^{14}C_{10}.

Book answer. d

1 (ix)
If {}^{15}C_{3r}={}^{15}C_{r+3} then value of r is:
  1. A1
  2. B2
  3. C3Answer
  4. D4
Why

Either 3r=r+3, which gives r=\tfrac32 (not a whole number), or 3r+(r+3)=15, which gives 4r=12 and r=3.

Check: {}^{15}C_{9}={}^{15}C_{6}. For r=1 the two sides are {}^{15}C_{3} and {}^{15}C_{4}, which are different, so (a) fails.

Book answer. c

1 (x)
The number of ways in which r letters can be posted in n letter boxes in a town is:
  1. A{}^{n}C_{r}
  2. B{}^{n}P_{r}
  3. Cr^{n}
  4. Dn^{r}Answer
Why

Take the letters one at a time. Each letter can be posted in any of the n boxes, and a box may receive more than one letter, so there is no restriction between letters.

\underbrace{n\times n\times\cdots\times n}_{r\text{ letters}}=n^{r}

Options (a) and (b) would need each box to get at most one letter. Option (c), r^{n}, would be the count if each of n boxes chose one of the r letters.

Book answer. c

Note. The book key gives (c) r^{n}, but each of the r letters has n choices of box, so the count is n^{r}, option (d). For r=2 letters and n=3 boxes: 3^{2}=9 ways (and 2^{3}=8 is wrong).

2
How many words can be formed by using four distinct alphabets?
Solution
  1. Take four given distinct letters. Each word uses all four letters, and a different order gives a different word.
  2. The number of arrangements of 4 distinct objects is 4!.
    4!=4\times3\times2\times1=24
24

Book answer. 24

Note. The question does not name the four letters. The book answer 24=4! is for four given distinct letters.

3
How many 3-digit numbers are there which have 0 at unit place?
Solution
  1. The units place is fixed as 0: 1 way.
    1
  2. The hundreds digit cannot be 0, so it is one of 1,2,\dots,9.
    9\text{ ways}
  3. The tens digit can be any digit 0 to 9 (the question does not forbid repeating 0).
    10\text{ ways}
  4. Multiply.
    9\times10\times1=90

These are 100,110,120,\dots,990: the multiples of 10 from 100 to 990, and \dfrac{990-100}{10}+1=90.

90

Book answer. 90

Note. If digits could not repeat, the tens digit would have 8 choices and the answer would be 72. The book answer 90 allows repetition.

4
How many six-digit numbers can be formed using the digits 0,2,3,4,5,7 without repeating.
Solution
  1. A six-digit number cannot begin with 0. So the first place has 5 choices (2,3,4,5,7).
    5
  2. The other 5 places use the remaining 5 digits (including 0) in any order.
    5!=120
  3. Multiply.
    5\times120=600

Check by subtraction: all arrangements 6!=720 minus those starting with 0, 5!=120, gives 600.

600

Book answer. 600

5
The number of ways of arranging 7 keys in a key chain.
Solution
  1. Keys on a key chain form a circle, so use circular permutations: (7-1)! ways.
    (7-1)!=6!=720
  2. A key chain can be flipped over, which turns every clockwise arrangement into the anticlockwise arrangement of the same keys. So the arrangements are counted twice; divide by 2 (as in the book, Section 6.3.3).
    \dfrac{(7-1)!}{2}=\dfrac{720}{2}=360
360

Book answer. 360

6
Twelve persons are seated at a round table. Find the number of ways of their arrangement if two particular persons do not want to sit together.
Solution
  1. All ways of seating 12 persons at a round table:
    (12-1)!=11!=39916800
  2. Count the arrangements in which the two particular persons do sit together. Tie them as one block. With the other 10 persons that makes 11 objects, arranged round the table in (11-1)! ways.
    10!=3628800
  3. Inside the block the two persons can swap places in 2! ways.
    10!\times2!=7257600
  4. Subtract the unwanted arrangements from the total.
    11!-2\times10!=39916800-7257600=32659200

Factorised: 11!-2\cdot10!=10!\,(11-2)=9\times10!.

11!-2\cdot10!=32659200

Book answer. 32,659,200

FBISE 2025 and 2026 questions

Questions from the FBISE HSSC-I 2026 (1st Annual) and FBISE HSSC-I 2025 (1st Annual) papers that belong to this unit, answered the way an examiner expects.

2026 Annual I, Set B, MCQ 41 mark
Number of ways of arrangements of the letters in the word "SUNDAY" are:
  1. A120
  2. B480
  3. C600
  4. D720Answer
Why

SUNDAY has 6 different letters, and an arrangement uses all of them with order mattering, so the number of ways is {}^{6}P_{6}=6!=720.

Option A, 120, is 5!; it would be the answer for 5 letters. The other values 480 and 600 are not factorials, so they cannot count arrangements of 6 different letters.

2026 Annual I, Set B, MCQ 51 mark
Number of ways to select 8 players from 12 are:
  1. A495Answer
  2. B720
  3. C11885
  4. D19958
Why

Selecting players is a combination (order does not matter): {}^{12}C_{8}={}^{12}C_{4}=\dfrac{12\cdot11\cdot10\cdot9}{4!}=\dfrac{11880}{24}=495.

The large options come from counting orders as well: {}^{12}P_{8}=19\,958\,400, far bigger than any selection count. The selection count is {}^{12}P_{8}\div8!=495.

2025 Annual I, Set B, MCQ 191 mark
How many 5-letter words can be formed from the word 'MATHS' without repeating any letter?
  1. A20
  2. B60
  3. C120Answer
  4. D240
Why

The word MATHS has 5 different letters, and a 5-letter word uses all of them with order mattering. The number of arrangements is {}^{5}P_{5}=5!=120.

Option B, 60, would be {}^{5}P_{3} (3-letter words); option A, 20, is {}^{5}P_{2}. Here all 5 letters are used, so r=n=5.

2025 Annual I, Set B, MCQ 201 mark
In how many different ways a player can select 6 numbers from a set of 49 numbers, in a lottery?
  1. A^{49}C_6Answer
  2. B\dfrac{49!}{6!}
  3. C^{49}P_6
  4. D6!
Why

Choosing 6 numbers out of 49 for a lottery ticket is a selection: the order in which the numbers are picked does not matter. So the number of ways is the combination {}^{49}C_{6}.

Options B and C, \dfrac{49!}{6!} and {}^{49}P_{6}, count ordered selections ({}^{49}P_{6}=\dfrac{49!}{43!}), which count each group of 6 numbers 6! times.

2025 Annual I, Set B, Q.2 (ii) OR4 marks
Verify that: \dbinom{n}{r}+\dbinom{n}{r-1}=\dbinom{n+1}{r}
Solution

Verify that {}^{n}C_{r}+{}^{n}C_{r-1}={}^{n+1}C_{r}, written \dbinom{n}{r}+\dbinom{n}{r-1}=\dbinom{n+1}{r}. Use {}^{n}C_{r}=\dfrac{n!}{r!\,(n-r)!}.

  1. Write both terms of the left side with the formula.
    \text{LHS}=\dfrac{n!}{r!\,(n-r)!}+\dfrac{n!}{(r-1)!\,(n-r+1)!}
  2. Make the denominators equal to r!\,(n-r+1)!. Use r!=r\,(r-1)! and (n-r+1)!=(n-r+1)(n-r)!: multiply the first fraction by \dfrac{n-r+1}{n-r+1} and the second by \dfrac{r}{r}.
    \text{LHS}=\dfrac{n!\,(n-r+1)}{r!\,(n-r+1)!}+\dfrac{n!\,r}{r!\,(n-r+1)!}
  3. Add the numerators and take out n!.
    \text{LHS}=\dfrac{n!\,[(n-r+1)+r]}{r!\,(n-r+1)!}=\dfrac{n!\,(n+1)}{r!\,(n+1-r)!}
  4. Use (n+1)\,n!=(n+1)!.
    \text{LHS}=\dfrac{(n+1)!}{r!\,[(n+1)-r]!}={}^{n+1}C_{r}=\text{RHS}

Hence verified.

2026 Annual I, Set B, Q.2 (iii) OR4 marks
Find the value of n if {}^nP_4:{}^{n-1}P_3=9:1.
Solution

Use {}^{n}P_{r}=n(n-1)(n-2)\cdots(n-r+1) for both permutations.

  1. Write each permutation as a product.
    {}^{n}P_{4}=n(n-1)(n-2)(n-3),\qquad {}^{n-1}P_{3}=(n-1)(n-2)(n-3)
  2. Form the ratio and cancel the common factor (n-1)(n-2)(n-3).
    \dfrac{{}^{n}P_{4}}{{}^{n-1}P_{3}}=\dfrac{n(n-1)(n-2)(n-3)}{(n-1)(n-2)(n-3)}=n
  3. The ratio is given as 9:1, that is 9.
    n=9

Check: {}^{9}P_{4}=3024 and {}^{8}P_{3}=336, and 3024\div336=9.

n=9
2026 Annual I, Set B, Q.2 (vii) OR4 marks
A class has 5 boys and 4 girls. In how many ways can a group of 3 students be formed?
Solution

A group is a selection, so order does not matter. There are 5+4=9 students in all, and 3 are chosen with no condition.

  1. Use {}^{n}C_{r}=\dfrac{n!}{r!\,(n-r)!} with n=9,\ r=3.
    {}^{9}C_{3}=\dfrac{9\cdot8\cdot7}{3\cdot2\cdot1}
  2. Simplify.
    {}^{9}C_{3}=\dfrac{504}{6}=84
84\ \text{ways}
2025 Annual I, Set B, Q.2 (viii) OR4 marks
How many words can be formed by using the letters from the word 'EDUCATION' such that all the vowels are never together?
Solution

EDUCATION has 9 different letters: the vowels are E, U, A, I, O (5 of them) and the consonants are D, C, T, N (4 of them).

  1. All arrangements of the 9 letters:
    9!=362880
  2. Arrangements with all vowels together: tie the 5 vowels into one block. The block and the 4 consonants make 5 objects, arranged in 5! ways.
    5!=120
  3. Inside the block the vowels can be arranged in 5! ways.
    120\times120=14400
  4. Vowels never together means the total minus those with all vowels together.
    362880-14400=348480
348480
2026 Annual I, Set B, Q.3 OR08 for the whole OR = 8 marks
A committee of 5 members is to be selected from a group of 8 men and 6 women. In how many ways can the committee be formed if it must include at least 2 women?
Solution

There are 8+6=14 persons. A committee is a selection, so use combinations. "At least 2 women" means 2,\ 3,\ 4 or 5 women, and the rest are men.

  1. Case 2 women, 3 men (rule of product).
    {}^{6}C_{2}\times{}^{8}C_{3}=15\times56=840
  2. Case 3 women, 2 men.
    {}^{6}C_{3}\times{}^{8}C_{2}=20\times28=560
  3. Case 4 women, 1 man.
    {}^{6}C_{4}\times{}^{8}C_{1}=15\times8=120
  4. Case 5 women, 0 men.
    {}^{6}C_{5}\times{}^{8}C_{0}=6\times1=6
  5. The cases cannot overlap, so add them.
    840+560+120+6=1526
  1. Check by the complement: all committees minus those with 0 or 1 woman.
    {}^{14}C_{5}-{}^{8}C_{5}-{}^{8}C_{4}\,{}^{6}C_{1}=2002-56-420=1526

The committee can be formed in 1526 ways.

1526\ \text{ways}
2025 Annual I, Set B, Q.6 OR08 for the whole OR; parts (a) to (d) not split on paper = 8 marks
A company has 7 engineers and 5 managers. In how many ways can a project team of 5 be selected if it includes: (a) 3 engineers and 2 managers? (b) 4 engineers and 1 manager? (c) At least 4 engineers? (d) At the most 1 manager?
Solution

Choose a team of 5 from 7 engineers and 5 managers (order does not matter, so use combinations). Total persons: 12.

  1. (a) 3 engineers and 2 managers: choose each group, then multiply (rule of product).
    {}^{7}C_{3}\times{}^{5}C_{2}=35\times10=350
  1. (b) 4 engineers and 1 manager.
    {}^{7}C_{4}\times{}^{5}C_{1}=35\times5=175
  1. (c) At least 4 engineers means 4 engineers with 1 manager, or 5 engineers with no manager. Add the two cases, which cannot overlap.
    {}^{7}C_{4}\,{}^{5}C_{1}+{}^{7}C_{5}\,{}^{5}C_{0}=175+21=196
  1. (d) At most 1 manager means no manager (5 engineers) or 1 manager (4 engineers).
    {}^{7}C_{5}+{}^{7}C_{4}\,{}^{5}C_{1}=21+175=196

Parts (c) and (d) have the same answer because both mean 4 or 5 engineers.

350,\ 175,\ 196,\ 196
2026 Annual I, Set D, MCQ 191 mark
Number of ways of arrangement of the letters in the word "GARDEN" are:
  1. A480
  2. B600
  3. C720Answer
  4. D840
Why

GARDEN has 6 letters G, A, R, D, E, N, all different, so they can be arranged in {}^{6}P_{6}=6!=720 ways.

The values 480, 600 and 840 are not factorials, so none of them can be the count of arranging 6 different letters. (840=\dfrac{7!}{3!} belongs to a different word.)

2025 Annual I, Set D, MCQ 191 mark
A cell phone password consists of 4 distinct digits (0-9). How many possible passwords can be set?
  1. A^{10}C_4
  2. B^{10}P_4Answer
  3. C^{9}C_4
  4. D^{9}P_4
Why

A password of 4 distinct digits chosen from the 10 digits 0 to 9 is an arrangement: the passwords 1234 and 4321 differ. So the number is {}^{10}P_{4}=10\cdot9\cdot8\cdot7=5040.

Option A, {}^{10}C_{4}, ignores order. Options C and D use 9 digits, but 0 is allowed in a password, so all 10 digits are available.

2026 Annual I, Set D, MCQ 201 mark
Number of ways to choose 10 members from 15 are:
  1. A360,360
  2. B\dfrac{15!}{10!}
  3. C\dfrac{15!}{5!}
  4. D3003Answer
Why

Choosing members is a combination: {}^{15}C_{10}=\dfrac{15!}{10!\,5!}={}^{15}C_{5}=\dfrac{15\cdot14\cdot13\cdot12\cdot11}{5!}=\dfrac{360360}{120}=3003.

Options A and B are the same number, \dfrac{15!}{10!}=360\,360={}^{15}P_{5}: they leave out the division by 5! for the order inside the group. Option C is \dfrac{15!}{5!}={}^{15}P_{10}, an even larger arrangement count.

2025 Annual I, Set D, MCQ 201 mark
How many 5-letter words can be formed from the word 'TABLE' without repeating any letter?
  1. A20
  2. B60
  3. C120Answer
  4. D240
Why

The word TABLE has 5 different letters and a 5-letter word uses all of them: {}^{5}P_{5}=5!=120.

Option B, 60, is {}^{5}P_{3}, which would be for 3-letter words.

2026 Annual I, Set D, Q.2 (ii) OR4 marks
Evaluate \dfrac{(n-1)!}{(n-3)!}.
Solution

Expand the larger factorial until the factor (n-3)! appears: (n-1)!=(n-1)(n-2)(n-3)!.

  1. Write (n-1)! in terms of (n-3)!.
    (n-1)!=(n-1)(n-2)\,(n-3)!
  2. Cancel the common factor (n-3)!.
    \dfrac{(n-1)!}{(n-3)!}=\dfrac{(n-1)(n-2)\,(n-3)!}{(n-3)!}=(n-1)(n-2)
  3. Multiply out if required.
    (n-1)(n-2)=n^{2}-3n+2
(n-1)(n-2)=n^{2}-3n+2
2025 Annual I, Set D, Q.2 (ii) OR4 marks
Verify that: {}^nP_r={}^{n-1}P_r+r\cdot{}^{n-1}P_{r-1}.
Solution

Verify that {}^{n}P_{r}={}^{n-1}P_{r}+r\cdot{}^{n-1}P_{r-1}. Use {}^{n}P_{r}=\dfrac{n!}{(n-r)!}.

  1. Write both terms of the right side with the formula.
    \text{RHS}=\dfrac{(n-1)!}{(n-1-r)!}+r\cdot\dfrac{(n-1)!}{(n-r)!}
  2. Make the denominators equal to (n-r)!. Since (n-r)!=(n-r)\,(n-r-1)!, multiply the first fraction by \dfrac{n-r}{n-r}.
    \text{RHS}=\dfrac{(n-r)\,(n-1)!}{(n-r)!}+\dfrac{r\,(n-1)!}{(n-r)!}
  3. Add and take out (n-1)!.
    \text{RHS}=\dfrac{(n-1)!\,[(n-r)+r]}{(n-r)!}=\dfrac{n\,(n-1)!}{(n-r)!}
  4. Use n\,(n-1)!=n!.
    \text{RHS}=\dfrac{n!}{(n-r)!}={}^{n}P_{r}=\text{LHS}

Hence verified.

2026 Annual I, Set D, Q.2 (x) OR4 marks
Find r if {}^{54}P_r:{}^{56}P_{r+3}=1:30800.
Solution

Write both permutations with factorials: {}^{n}P_{r}=\dfrac{n!}{(n-r)!}.

  1. Write each permutation.
    {}^{54}P_{r}=\dfrac{54!}{(54-r)!},\qquad {}^{56}P_{r+3}=\dfrac{56!}{(56-r-3)!}=\dfrac{56!}{(53-r)!}
  2. Form the ratio. Use 56!=56\cdot55\cdot54! and (54-r)!=(54-r)(53-r)!.
    \dfrac{{}^{54}P_{r}}{{}^{56}P_{r+3}}=\dfrac{54!}{(54-r)!}\cdot\dfrac{(53-r)!}{56!}=\dfrac{1}{56\cdot55\,(54-r)}=\dfrac{1}{3080\,(54-r)}
  3. Equate to the given ratio \dfrac{1}{30800}.
    3080\,(54-r)=30800
  4. Divide by 3080 and solve.
    54-r=10\ \Rightarrow\ r=44

Check: r+3=47\le56, so both permutations are defined.

r=44

Note. The book's Exercise 6.2 Q3 (vii) is the same question with r shifted by 3 ({}^{54}P_{r+3}:{}^{56}P_{r+6}=1:30800), so its answer is r=41.

2025 Annual I, Set D, Q.2 (x) OR (a)
A bakery offers 2 types of breads, 7 types of fillings and 5 types of sauces for a custom sandwich. How many different sandwich combinations can be made?
Solution

A sandwich is made by choosing a bread, a filling and a sauce one after the other, so the rule of product applies.

  1. Breads, fillings and sauces: 2, 7 and 5 choices.
    2\times7\times5=70
70\ \text{combinations}
2025 Annual I, Set D, Q.2 (x) OR (b)
A bakery offers 2 types of breads, 7 types of fillings and 5 types of sauces for a custom sandwich. How many weeks can a customer eat a different sandwich each day without repetition?
Solution
  1. One different sandwich each day uses up 70 sandwiches, so the customer can eat for 70 days (from part (a)).
    70\ \text{days}
  2. A week has 7 days.
    \dfrac{70}{7}=10

The customer can eat a different sandwich every day for 10 weeks.

10\ \text{weeks}
2026 Annual I, Set D, Q.6 OR08 for the whole OR = 8 marks
A box contains 7 red, 5 blue and 4 green balls. In how many ways can 5 balls be selected if at least 2 are red?
Solution

The box has 7+5+4=16 balls, of which 7 are red and 9 are not red (blue or green). Balls of a kind are treated as different, and a selection ignores order, so use combinations. "At least 2 red" means 2,\ 3,\ 4 or 5 red balls, and the rest are non-red.

  1. Case 2 red, 3 non-red (rule of product).
    {}^{7}C_{2}\times{}^{9}C_{3}=21\times84=1764
  2. Case 3 red, 2 non-red.
    {}^{7}C_{3}\times{}^{9}C_{2}=35\times36=1260
  3. Case 4 red, 1 non-red.
    {}^{7}C_{4}\times{}^{9}C_{1}=35\times9=315
  4. Case 5 red, 0 non-red.
    {}^{7}C_{5}\times{}^{9}C_{0}=21\times1=21
  5. The cases cannot overlap, so add them.
    1764+1260+315+21=3360
  1. Check by the complement: all selections minus those with 0 or 1 red ball.
    {}^{16}C_{5}-{}^{9}C_{5}-{}^{7}C_{1}\,{}^{9}C_{4}=4368-126-882=3360

The balls can be selected in 3360 ways.

3360\ \text{ways}
2025 Annual I, Set D, Q.6 OR08 for the whole OR; parts (a) to (d) not split on paper = 8 marks
A basketball club has 7 forwards and 5 guards. In how many ways a team of 5 can be selected if it includes: (a) 3 forwards and 2 guards? (b) 4 forwards and 1 guard? (c) At least 4 forwards? (d) At the most 1 guard?
Solution

Choose a team of 5 from 7 forwards and 5 guards (order does not matter, so use combinations).

  1. (a) 3 forwards and 2 guards.
    {}^{7}C_{3}\times{}^{5}C_{2}=35\times10=350
  1. (b) 4 forwards and 1 guard.
    {}^{7}C_{4}\times{}^{5}C_{1}=35\times5=175
  1. (c) At least 4 forwards: 4 forwards and 1 guard, or 5 forwards and no guard.
    175+{}^{7}C_{5}\,{}^{5}C_{0}=175+21=196
  1. (d) At most 1 guard: no guard (5 forwards) or 1 guard (4 forwards).
    {}^{7}C_{5}+{}^{7}C_{4}\,{}^{5}C_{1}=21+175=196

Parts (c) and (d) have the same answer because both mean 4 or 5 forwards.

350,\ 175,\ 196,\ 196

Exam focus

  1. Choose between permutation and combination, and use {}^{n}P_{n}=n! or {}^{n}C_{r} for a quick count. (mcq)
    Eight MCQs in two years: 2026 Set B MCQ 4 (SUNDAY, 6!) and MCQ 5 ({}^{12}C_{8}), Set D MCQ 19 (GARDEN, 6!, same as Review Exercise 6 MCQ (ii)) and MCQ 20 ({}^{15}C_{10}=3003); 2025 Set B MCQ 19, 20 and Set D MCQ 19, 20. Decide first whether order matters.
    Go to answer
  2. Committee or team selection with conditions such as at least, at most or exactly, using the rule of product and the complement. (problem)
    8 marks every set: 2026 Set B Q.3 OR (at least 2 women from 8 men and 6 women, 1526) and Set D Q.6 OR (at least 2 red balls, 3360); 2025 Set B Q.6 OR and Set D Q.6 OR. Book: Exercise 6.3 Q6, Q7 and Q14.
    Go to answer
  3. Find n or r from an equation with {}^{n}P_{r} using factorials. (problem)
    2026 Set B Q.2 (iii) OR ({}^{n}P_{4}:{}^{n-1}P_{3}=9:1, n=9, same as Exercise 6.2 Q2 (vii)) and Set D Q.2 (x) OR ({}^{54}P_{r}:{}^{56}P_{r+3}=1:30800, r=44, close to Exercise 6.2 Q3 (vii)); 4 marks each.
    Go to answer
  4. Simplify a factorial expression, or prove an identity of {}^{n}P_{r} or {}^{n}C_{r} with factorials. (problem)
    2026 Set D Q.2 (ii) OR (\dfrac{(n-1)!}{(n-3)!}); 2025 Set B Q.2 (ii) OR ({}^{n}C_{r}+{}^{n}C_{r-1}={}^{n+1}C_{r}) and Set D Q.2 (ii) OR ({}^{n}P_{r}={}^{n-1}P_{r}+r\,{}^{n-1}P_{r-1}). Book: Exercise 6.1 Q1, Exercise 6.2 Q1 and Exercise 6.3 Q1.
    Go to answer
  5. Direct selection of a group with {}^{n}C_{r} (no condition). (problem)
    2026 Set B Q.2 (vii) OR (3 students from 5 boys and 4 girls, {}^{9}C_{3}=84), 4 marks. Do not split into boys and girls unless a condition asks for it.
    Go to answer
  6. Arrangements of the letters of a word with a condition (vowels never together). (problem)
    2025 Set B Q.2 (viii) OR (EDUCATION, 4 marks). Same method as Exercise 6.2 Q13: total arrangements minus those with the vowels tied in a block.
    Go to answer
  7. Rule of product for a multi-stage choice (bread, filling, sauce), then convert to weeks. (problem)
    2025 Set D Q.2 (x) OR (a), (b), 4 marks: 2\times7\times5=70, then 70\div7=10 weeks. Not repeated in 2026, but the rule of product is used inside every 2026 selection question.
    Go to answer
  8. Circular permutations and seating at a round table. (problem)
    Not in the 2025 or 2026 papers; Exercise 6.2 Q8, Q19, Q20 and Review Exercise 6 Q5, Q6 practise (n-1)! with conditions.
    Go to answer
  9. Arrangements with alike objects, \dfrac{n!}{p!\,q!\,r!} (flags, repeated letters, digits). (problem)
    Not in the 2025 or 2026 papers; Exercise 6.2 Q7, Q9, Q11. A likely paper question because the book gives a formula for it.
    Go to answer

Mark this unit as done to fill the Class 11 Mathematics ring.

Next, unit 7
Mathematical induction and binomial theorem

© 2026 FBISE Fold. Independent study notes, not affiliated with the Federal Board of Intermediate and Secondary Education.