Free worked solutions · 2026 Edition

Chapter 4: Counting principles worked solutions

Worked solutions to the practice questions in Chapter 4 of The Ultimate Guide for the IB: Mathematics: Analysis and Approaches HL (2026 Edition). Each solution shows every step with the mark it earns, the way an IB mark scheme does.

Chapter 4 of 19
Volume 1
25 practice questions
4 Going further
Free, no sign-up

Start with Basics All 19 chapters

Basics

One idea at a time, in the order the chapter teaches them.

Question 1

[6 marks]

A mountain hut offers a set lunch. A guest chooses one of 3 soups, one of 5 main dishes and one of 4 desserts.

(a) Find the number of different set lunches.

[2]

On Sundays the hut serves a light lunch instead: a guest chooses one main dish together with either a soup or a dessert, but not both.

(b) Find the number of different light lunches.

[2]

(c) On weekdays a guest must choose a main dish, but may leave out the soup, the dessert or both. Find the number of different meals a guest can order on a weekday.

[2]

Show solutionHide solution

(a) 3 \times 5 \times 4

= 60

(b) soup or dessert: 3 + 4 = 7 choices (addition principle)

7 \times 5 = 35

(c) soup: 3 + 1 = 4 options (including “no soup”), dessert: 4 + 1 = 5 options, so 4 \times 5 \times 5

= 100

Final answer

(a) 60
(b) 35
(c) 100

Question 2

[8 marks]

For each situation, state whether the order of the chosen items matters, and find the number of possibilities.

(a) Nadia packs 3 of her 8 different jigsaw puzzles for a holiday.

[2]

(b) A craft fair awards a gold, a silver and a bronze ribbon to 3 of 8 quilts.

[2]

(c) A class of 8 students sends 2 of its students to a student council meeting.

[2]

(d) 4 of the 8 members of a swimming squad are chosen to swim the first, second, third and fourth legs of a relay.

[2]

Show solutionHide solution

(a) order does not matter (a selection)

\binom{8}{3} = 56

(b) order matters (the ribbons are different)

{}^{8}P_{3} = 336

(c) order does not matter

\binom{8}{2} = 28

(d) order matters (the legs are different)

{}^{8}P_{4} = 1680

Note: award A1 only for the correct value; the R1 may be implied by the correct use of \binom{n}{r} or {}^{n}P_{r}.

Final answer

(a) order does not matter, 56
(b) order matters, 336
(c) order does not matter, 28
(d) order matters, 1680

Question 3

[7 marks]

A tree farm sells 9 different apple saplings and 4 different pear saplings. Mila buys 4 different saplings.

(a) Find the number of possible choices of 4 saplings.

[1]

(b) Find the number of choices that contain exactly 3 apple saplings.

[2]

(c) Find the number of choices that contain at most one pear sapling.

[2]

(d) Find the number of choices that contain at least one sapling of each fruit.

[2]

Show solutionHide solution

(a) \binom{13}{4} = 715

(b) 3 apple and 1 pear: \binom{9}{3} \times \binom{4}{1} = 84 \times 4

= 336

(c) no pear or exactly one pear: \binom{9}{4} + 336 = 126 + 336

= 462

(d) total minus “all apple” minus “all pear”: 715 - \binom{9}{4} - \binom{4}{4} = 715 - 126 - 1

= 588

Note: in (d) accept adding the cases 3 + 1, 2 + 2, 1 + 3: 336 + 216 + 36 = 588.

Final answer

(a) 715
(b) 336
(c) 462
(d) 588

Question 4

[7 marks]

A film society has shortlisted 10 different films. It will choose 4 of them to show at its weekend festival; the order of the showings is decided later.

(a) Find the number of possible choices of 4 films.

[1]

(b) One of the films is a documentary about glaciers. Find the number of choices that include this documentary.

[2]

Two of the films, a comedy and a western, come from the same distributor, and the society can afford to show only one of them.

(c) Find the number of choices that do not include both the comedy and the western.

[2]

(d) Find the number of choices that include exactly one of the comedy and the western.

[2]

Show solutionHide solution

(a) \binom{10}{4} = 210

(b) the other 3 films from the remaining 9: \binom{9}{3}

= 84

(c) choices containing both: \binom{8}{2} = 28

210 - 28 = 182

(d) 2 \times \binom{8}{3} = 2 \times 56

= 112

Note: in (c) accept 112 + \binom{8}{4} = 112 + 70 = 182 (exactly one, or neither).

Final answer

(a) 210
(b) 84
(c) 182
(d) 112

Question 5

[8 marks]

Twelve volunteers at a food festival are split into three named teams: a kitchen team of five, a ticket team of four and a stage team of three.

(a) Show that the number of ways of forming the three teams is 27\,720.

[2]

Two friends, Ana and Ben, ask to be in the same team.

(b) Find the number of ways of forming the three teams so that Ana and Ben are in the same team.

[4]

On another day, 8 of the volunteers are split into two groups of 4 for a tug-of-war. The two groups are not named.

(c) Find the number of ways of splitting the 8 volunteers into the two groups.

[2]

Show solutionHide solution

(a) \binom{12}{5} \times \binom{7}{4} \times \binom{3}{3}

= 792 \times 35 \times 1 = 27\,720 A1AG

(b) three cases, by the team that Ana and Ben join

kitchen: \binom{10}{3}\binom{7}{4} = 120 \times 35 = 4200

ticket: \binom{10}{5}\binom{5}{2} = 252 \times 10 = 2520; stage: \binom{10}{5}\binom{5}{4} = 252 \times 5 = 1260

total = 4200 + 2520 + 1260 = 7980

(c) \dfrac{1}{2}\binom{8}{4}

= 35

Note: the division by 2 is needed because the groups are not named: choosing group \{P, Q, R, S\} leaves the same split as choosing the other four. Award M1A0 for 70.

Final answer

(a) shown, 27\,720
(b) 7980
(c) 35

Question 6

[9 marks]

Seven kayakers, including Kai, Lou and their guide Mo, paddle in single file through a narrow gorge.

(a) Find the number of orders in which the seven kayakers can paddle.

[1]

(b) Find the number of orders in which Mo is either first or last.

[2]

(c) Find the number of orders in which Mo is first and Kai and Lou are next to each other.

[3]

(d) Find the number of orders in which exactly two kayakers are between Kai and Lou.

[3]

Show solutionHide solution

(a) 7! = 5040

(b) 2 places for Mo, then 6! for the others: 2 \times 6!

= 1440

(c) Mo first; Kai and Lou as a block (in 2 orders) with the other 4 kayakers: 5 items in places 2 to 7

5! \times 2

= 240

(d) places (1, 4), (2, 5), (3, 6), (4, 7): 4 pairs of places

2 orders for Kai and Lou, 5! for the others: 4 \times 2 \times 5!

= 960

Final answer

(a) 5040
(b) 1440
(c) 240
(d) 960

Question 7

[7 marks]

A coding club has 11 members: 7 first-year students and 4 second-year students. Four members are chosen at random to present at an open evening.

(a) Find the probability that all four are from the same year.

[3]

(b) Find the probability that exactly three are first-year students.

[2]

The club captain is a first-year student and the vice-captain is a second-year student.

(c) Find the probability that the captain is chosen but the vice-captain is not.

[2]

Show solutionHide solution

total number of choices \binom{11}{4} = 330

(a) all first-year \binom{7}{4} = 35, all second-year \binom{4}{4} = 1 M1A1

\dfrac{35 + 1}{330} = \dfrac{6}{55}

(b) \dfrac{\binom{7}{3}\binom{4}{1}}{330} = \dfrac{140}{330}

= \dfrac{14}{33}

(c) the captain is in; the other 3 are chosen from the 9 members who are neither captain nor vice-captain: \dfrac{\binom{9}{3}}{330} = \dfrac{84}{330}

= \dfrac{14}{55}

Final answer

(a) \frac{6}{55}
(b) \frac{14}{33}
(c) \frac{14}{55}

Tutorial

Exam-style questions on each question type, with the marks the IB would give.

Question 8

[5 marks]

(a) Find the number of three-digit positive integers.

[1]

(b) Find the number of three-digit positive integers in which all three digits are different.

[2]

(c) Find the number of three-digit positive integers that are odd and have all three digits different.

[2]

Show solutionHide solution

(a) The first digit has 9 choices (1 to 9), the others 10: 9\times10\times10 = 900.

[1]

(b) First digit 9 ways (not 0), second 9 ways (any digit except the first, now 0 allowed), third 8 ways.

[1]

9\times9\times8 = 648.

[1]

(c) Fix the last digit first: it is odd, 5 ways.

[1]

The first digit is non-zero and different from the last: 8 ways; the middle digit is different from both: 8 ways. 5\times8\times8 = 320.

[1]

Final answer

(a) 900
(b) 648
(c) 320

Question 9

[6 marks]

The seven different letters P, Q, R, S, T, U, V are arranged in a row.

(a) Find the number of arrangements in which P is next to Q and R is next to S.

[3]

(b) Find the number of arrangements in which P is next to Q but R is not next to S.

[3]

Show solutionHide solution

(a) Two blocks (PQ and RS) and the letters T, U, V make 5 items: 5! arrangements.

[1]

Each block can be written in 2! ways.

[1]

5!\times 2\times 2 = 480.

[1]

(b) P next to Q (no other condition): 6!\times 2 = 1440.

[1]

Remove those in which R is also next to S: 1440 - 480.

[1]

= 960.

[1]

Final answer

(a) 480
(b) 960

Question 10

[7 marks]

Five red flags and three blue flags are arranged in a row. All eight flags are different from one another.

(a) Find the number of arrangements in which no two blue flags are next to each other.

[4]

(b) Find the number of arrangements in which no two blue flags are next to each other and the first flag in the row is red.

[3]

Show solutionHide solution

(a) Arrange the red flags first: 5! = 120 ways.

[1]

They leave 6 gaps (including both ends).

[1]

Place the three blue flags in three different gaps, order mattering: {}^{6}\mathrm{P}_{3} = 120.

[1]

120\times 120 = 14\,400.

[1]

(b) If the first flag is red, the gap before the first red flag is not used, so the blue flags go into 3 of the other 5 gaps.

[1]

{}^{5}\mathrm{P}_{3} = 60 ways to place them.

[1]

5!\times 60 = 7200.

[1]

Final answer

(a) 14\,400
(b) 7200

Question 11

[5 marks]

Nine singers stand on risers arranged in three rows of three, so that there are nine distinct positions. Ola and Pia are two of the singers.

(a) Find the number of ways of placing the nine singers in the nine positions.

[1]

(b) Find the number of ways in which Ola and Pia are in the same row.

[3]

(c) Hence find the number of ways in which Ola and Pia are in different rows.

[1]

Show solutionHide solution

(a) 9! = 362\,880.

[1]

(b) Ola takes any of the 9 positions.

[1]

Pia takes either of the 2 other positions in Ola's row, and the other seven singers fill the remaining seven positions in 7! ways.

[1]

9\times 2\times 7! = 90\,720.

[1]

(c) 362\,880 - 90\,720 = 272\,160.

[1]

Final answer

(a) 362\,880
(b) 90\,720
(c) 272\,160

Question 12

[5 marks]

Fourteen distinct mineral specimens are split into two collections of seven.

(a) One collection goes to the east cabinet and the other to the west cabinet. Find the number of possible assignments.

[1]

(b) The two collections are not labelled. Find the number of different splits.

[2]

(c) Two particular specimens must be in the same collection. Find the number of different splits when the collections are not labelled.

[2]

Show solutionHide solution

(a) Choose the east collection; the west collection is then determined: \binom{14}{7}=3432.

[1]

(b) Each split has two east/west assignments, giving \frac12\binom{14}{7}=1716.

[2]

(c) The collection containing the designated pair is uniquely identified. Choose its other five specimens from the remaining twelve: \binom{12}{5}=792.

[2]

Final answer

(a) 3432
(b) 1716
(c) 792

Question 13

[6 marks]

(a) Show that \binom{n}{2} = \dfrac{n(n-1)}{2}.

[1]

In a league every team plays every other team exactly once. A league has 45 matches in total.

(b) Find the number of teams in the league.

[3]

(c) Show that \binom{n}{2} - \binom{n-1}{2} = n-1, and explain what this represents when a new team joins a league.

[2]

Show solutionHide solution

(a) \binom{n}{2} = \dfrac{n!}{2!\,(n-2)!} = \dfrac{n(n-1)(n-2)!}{2\,(n-2)!} = \dfrac{n(n-1)}{2}.

[1]

(b) Each match is an unordered pair of teams: \dfrac{n(n-1)}{2} = 45 \Rightarrow n^2 - n - 90 = 0.

[1]

(n-10)(n+9) = 0.

[1]

A number of teams cannot be negative, so n = 10.

[1]

(c) \dfrac{n(n-1)}{2} - \dfrac{(n-1)(n-2)}{2} = \dfrac{(n-1)\bigl(n-(n-2)\bigr)}{2} = n-1.

[2]

When a team joins a league of n-1 teams there are n-1 extra matches, one against each existing team.

Final answer

(a) shown
(b) 10 teams
(c) shown: the new team plays one match against each of the n-1 existing teams

Question 14

[8 marks]

A club has n members, where n\ge 6. Priya and Quinn are two of the members. A committee of 4 members is chosen at random from the club.

(a) Show that the probability that Priya is on the committee is \dfrac{4}{n}.

[2]

The probability that both Priya and Quinn are on the committee is \dfrac{1}{13}.

(b) Find n.

[4]

(c) For the value of n found in part (b), find the probability that exactly one of Priya and Quinn is on the committee.

[2]

Show solutionHide solution

(a) Priya is on the committee: choose the other 3 from the remaining n-1, so P=\dfrac{\binom{n-1}{3}}{\binom{n}{4}}.

[1]

=\dfrac{(n-1)(n-2)(n-3)/6}{n(n-1)(n-2)(n-3)/24}=\dfrac{4}{n}.

[1]

(b) Both on the committee: P=\dfrac{\binom{n-2}{2}}{\binom{n}{4}}.

[1]

=\dfrac{(n-2)(n-3)/2}{n(n-1)(n-2)(n-3)/24}=\dfrac{12}{n(n-1)}.

[1]

\dfrac{12}{n(n-1)}=\dfrac1{13}\Rightarrow n^2-n-156=0.

[1]

(n-13)(n+12)=0, and n>0, so n=13.

[1]

(c) Exactly one: choose which of the two (2 ways) and 3 others from the 11 non-members: \dfrac{2\binom{11}{3}}{\binom{13}{4}}=\dfrac{330}{715}.

[1]

=\dfrac{6}{13}.

[1]

Final answer

(a) shown
(b) n=13
(c) \frac{6}{13}

Question 15

[5 marks]

A basketball player takes 9 free throws and scores with exactly 4 of them. Every set of positions for the 4 scoring throws is equally likely.

(a) Write down the number of possible sets of positions.

[1]

(b) Find the probability that the 4 scoring throws are consecutive.

[2]

(c) Find the probability that no two scoring throws are consecutive.

[2]

Show solutionHide solution

(a) A set of positions is a choice of 4 of the 9 throws, so there are \binom94=126 sets.

(b) Four consecutive throws can start at throw 1,2,\ldots,6, so there are 6 runs.

The probability is \dfrac{6}{126}=\dfrac1{21}.

(c) The 5 missed throws leave 6 gaps, including both ends. Choose 4 of the gaps for the scoring throws: \binom64=15.

The probability is \dfrac{15}{126}=\dfrac{5}{42}.

Final answer

(a) 126
(b) \frac{1}{21}
(c) \frac{5}{42}

Mastery

Full exam questions that mix question types, at Paper 1 and Paper 2 standard.

Question 16

[4 marks]

A school council has twelve members. A working party of six is formed by first appointing a convenor and a minute-taker, and then choosing four more members to complete the party. Determine the number of ways in which the working party can be formed.

[4]

Show solutionHide solution

The convenor and the minute-taker are distinct roles, so the number of ways of filling them is

{}^{12}P_2=12\times11=132

The four remaining places are filled from the other ten members, order not mattering:

{}^{10}C_4=210

By the multiplication principle:

132\times210=27\,720

27\,720

[4]

Final answer

27\,720

Question 17

[3 marks]

Sixteen students at a coding camp must be split into four teams of equal size to enter a hackathon. The teams are not named or numbered. Find the total number of different ways in which the four teams can be formed.

[3]

Show solutionHide solution

METHOD 1 Arrange all 16 students in a line, divide by 4! for the order inside each team and by a further 4! because the four equal teams are indistinguishable:

\frac{16!}{(4!)^4\,4!}=2\,627\,625

METHOD 2 Choose the teams one at a time, then divide by 4! for the order of the teams:

\frac{{}^{16}C_4\times{}^{12}C_4\times{}^{8}C_4\times{}^{4}C_4}{4!}=\frac{1820\times495\times70\times1}{24}=2\,627\,625

2\,627\,625

[3]

Final answer

2\,627\,625

Question 18

[4 marks]

Five-digit positive integers are written using the digits 0,1,2,\ldots,9, and a number may not begin with 0. Find how many of these integers satisfy each condition.

(a) all five digits are different and the integer is odd;

[2]

(b) all five digits are different, decrease strictly from left to right, and the integer is a multiple of 5.

[2]

Show solutionHide solution

(a) Fill the last digit first: it must be odd, so 5 choices. The first digit is non-zero and different from the last digit: 8 choices. The three middle digits are distinct and different from both ends: 8\times7\times6 ways.

5\times8\times8\times7\times6=13\,440

13\,440

[2]

(b) A strictly decreasing list is fixed once its set of digits is chosen. The last digit is 0 or 5.

Last digit 0: choose the other four digits from 1 to 9: {}^9C_4=126.

Last digit 5: all the other four digits must exceed 5, so they are 9,8,7,6: {}^4C_4=1.

Total: 126+1=127.

127

[2]

Final answer

(a) 13\,440
(b) 127

Question 19

[5 marks]

Let S be the set of the first twenty positive integers, S=\{1,2,3,\ldots,20\}. Mina chooses three different integers from S and adds them. Selections are unordered, so \{2,9,14\} and \{14,2,9\} count as the same selection.

Determine the number of selections for which the sum is a multiple of 3.

[5]

Show solutionHide solution

Sort the integers by their remainder on division by 3:

remainder 0: 3,6,\ldots,18 (6 numbers); remainder 1: 1,4,\ldots,19 (7 numbers); remainder 2: 2,5,\ldots,20 (7 numbers).

A sum of three integers is a multiple of 3 exactly when either all three have the same remainder, or the three remainders are 0,1,2 in some order.

Case 1 (same remainder):

{}^6C_3+{}^7C_3+{}^7C_3=20+35+35=90

Case 2 (one of each remainder):

6\times7\times7=294

Total:

90+294=384

384

[5]

Final answer

384

Question 20

[5 marks]

Nine contestants take part in a quiz final and are ranked from first to ninth, with no tied places. Dev, Esha and Farah are three of the nine contestants.

Find the number of possible rankings in which

(a) Esha is ranked exactly two places below Dev (so, for example, Dev third and Esha fifth);

[2]

(b) Dev is ranked above Esha, and Esha is ranked above Farah.

[3]

Show solutionHide solution

(a) Dev can occupy places 1 to 7, and Esha is then fixed two places below, giving 7 position pairs. The other seven contestants fill the remaining seven places in 7! ways:

7\times 7! = 35\,280

35\,280

[2]

(b) The three named contestants can finish in 3!=6 relative orders, all equally numerous by symmetry, and exactly one of them is Dev, Esha, Farah. Hence

\frac{9!}{3!} = \frac{362\,880}{6} = 60\,480

60\,480

[3]

Final answer

(a) 35\,280
(b) 60\,480

Question 21

[6 marks]

A cinema has a single row of 14 empty seats. Four friends, Gus, Hana, Ivo and Jade, buy tickets for this row.

(a) Find the number of possible ways in which they can be seated in the row if they decide not to occupy four consecutive seats.

[3]

The next evening the four friends are joined by three other people, and all seven sit in the same row of 14 empty seats. This time Gus, Hana, Ivo and Jade sit in four consecutive seats.

(b) Find the number of possible ways in which the seven people can be seated.

[3]

Show solutionHide solution

(a) All ways of seating the four friends: {}^{14}P_4=14\times13\times12\times11=24\,024.

Four consecutive seats can start at any of seats 1 to 11, and the friends can be ordered in 4! ways: 11\times24=264.

24\,024-264=23\,760

23\,760

[3]

(b) The four friends occupy a block of consecutive seats in 11\times4!=264 ways. The three other people then take any three of the remaining 10 seats in order: {}^{10}P_3=720.

264\times720=190\,080

190\,080

[3]

Final answer

(a) 23\,760
(b) 190\,080

Question 22

[8 marks]

A gallery wall has eight identical display frames arranged in two rows of four. Two frames share an edge if they are neighbours in the same row or directly above one another in the same column. Six different exhibits, named Aster, Birch, Cedar, Dahlia, Elm and Fennel, are to be placed in the frames. Aster and Birch are by rival artists.

Find the number of ways of placing the exhibits in each of the following cases.

(a) Each frame can hold any number of exhibits, and Aster and Birch must not be placed in the same frame.

[4]

(b) Each frame holds at most one exhibit, and Aster and Birch must not be placed in frames that share an edge.

[4]

Show solutionHide solution

(a) Aster may go in any of 8 frames; Birch then has 7 choices; each of the other four exhibits has 8 choices:

8\times 7\times 8^4 = 229\,376

Alternatively: all placements 8^6 minus those with Aster and Birch together 8^5:

8^6-8^5 = 262\,144-32\,768 = 229\,376

229\,376

[4]

(b) All placements with at most one exhibit per frame: {}^8P_6 = 8\times7\times6\times5\times4\times3 = 20\,160.

Pairs of frames sharing an edge: 2\times 3 = 6 in the rows and 4 in the columns, so 10 pairs.

Aster and Birch in a sharing pair: choose the pair (10), order them (2), then place the other four exhibits in the remaining six frames: {}^6P_4 = 360:

10\times 2\times 360 = 7200

Subtracting:

20\,160 - 7200 = 12\,960

12\,960

[4]

Final answer

(a) 229\,376
(b) 12\,960

Question 23

[5 marks]

In a table-tennis league every pair of players is scheduled to meet exactly three times. Before the season ends, Omar leaves the league after playing only four matches. All the other scheduled matches, which did not involve Omar, are played. In total 169 matches are played.

Determine the number of players who originally entered the league.

[5]

Show solutionHide solution

Let n be the number of players originally in the league. Among the other n-1 players each pair meets three times, so the number of matches not involving Omar is

3\times{}^{n-1}C_2=\frac{3(n-1)(n-2)}{2}

Adding Omar's four matches, the total is \dfrac{3(n-1)(n-2)}{2}+4=169, so

3(n-1)(n-2)=330 \implies (n-1)(n-2)=110

n^2-3n-108=0 \implies (n-12)(n+9)=0

As n>0, n=12.

Check: 3\times\binom{11}{2}+4=165+4=169.

[5]

Final answer

12 players

Question 24

[7 marks]

A manager has n staff to divide into two project teams. For practical reasons the first team must contain exactly four people and the second team must contain at least four people. The manager picks four people for the first team and puts the rest in the second team.

(a) Write down an expression, in terms of n, for the number of ways in which the staff can be assigned.

[1]

Two of the staff insist on working together, so they must be placed in the same team. The manager agrees, and finds that the number of possible assignments is now \dfrac49 of the number in part (a).

(b) Determine the value of n.

[6]

Show solutionHide solution

(a) ^nC_4

[1]

(b) Both of the pair in the first team: the other two members are chosen from n-2 people, {}^{n-2}C_2 ways. Both in the second team: all four first-team members come from the other n-2 people, {}^{n-2}C_4 ways. So

\text{ways}={}^{n-2}C_2+{}^{n-2}C_4

Setting this equal to \dfrac49\,{}^nC_4:

\frac{(n-2)(n-3)}{2}+\frac{(n-2)(n-3)(n-4)(n-5)}{24}=\frac49\cdot\frac{n(n-1)(n-2)(n-3)}{24}

Dividing by \dfrac{(n-2)(n-3)}{24} (valid as n>3):

12+(n-4)(n-5)=\frac{4n(n-1)}{9}

9n^2-81n+288=4n^2-4n \implies 5n^2-77n+288=0

(5n-32)(n-9)=0 \implies n=9\ \text{ or }\ n=6.4

Since n is an integer, n=9.

[6]

Final answer

(a) \binom{n}{4}
(b) n=9

Question 25

[12 marks]

Nineteen distinct archive volunteers are available: eleven cataloguers and eight conservators. An expedition selects eight volunteers.

(a) Find the number of possible expeditions.

[1]

(b) Find the number of expeditions with four volunteers from each specialism.

[2]

(c) Find the number of expeditions with at least three volunteers from each specialism.

[4]

(d) The eight volunteers of an expedition counted in part (b) then board a boat in single file. Find the number of ways of choosing such an expedition and its boarding order.

[1]

Conservators Mei and Noor are two specified volunteers.

(e) Find the number of expeditions that do not include both Mei and Noor.

[2]

(f) One expedition is selected, all selections being equally likely. Find the probability that Mei and Noor are both on it.

[2]

Show solutionHide solution

(a) \binom{19}{8}=75582.

[1]

(b) \binom{11}{4}\binom{8}{4}=23100.

[2]

(c) The cataloguer count j is 3,4 or 5. Summing \binom{11}{j}\binom{8}{8-j} over these cases gives 9240+23100+25872=58212.

[4]

(d) \binom{11}{4}\binom{8}{4}8!=931392000.

[1]

(e) Fixing the specified pair leaves six places selected from seventeen others. Exclude those cases: \binom{19}{8}-\binom{17}{6}=63206.

[2]

(f) p=\frac{\binom{17}{6}}{\binom{19}{8}}=\frac{28}{171}.

[2]

Final answer

(a) 75\,582
(b) 23\,100
(c) 58\,212
(d) 931\,392\,000
(e) 63\,206
(f) \frac{28}{171}

Going further

Beyond the syllabus: the worked examples and investigations of the chapter's Going further pages.

G1 Paths that never cross the diagonal

G1 Worked example

[11 marks]

In a class vote, Asha receives 5 votes and Ben receives 3. The 8 papers are counted one at a time, and a counting order is fixed by choosing which 3 of the 8 places in the count hold Ben's papers. Each counting order is drawn as a path from (0,0): a vote for Asha is a step (1,0) and a vote for Ben is a step (0,1).

(a) Find the number of possible counting orders.

[1]

(b) Explain why Asha is never behind Ben during the count exactly when the path never touches the line y=x+1.

[2]

(c) A path touches y=x+1 for the first time at the point T. Every step after T is swapped: each (1,0) becomes (0,1) and each (0,1) becomes (1,0). Show that the new path ends at (2,6), and explain why every path from (0,0) to (2,6) comes from exactly one path that touches the line.

[3]

(d) All counting orders are equally likely. Find the probability that Asha is never behind Ben.

[2]

(e) By considering paths that start with the step from (0,0) to (1,0) and then never touch y=x, find the probability that Asha is ahead after every paper is counted.

[3]

Show solutionHide solution

(a) \binom83=56

(b) after any number of papers the path is at (a,b), where a and b are the votes counted so far for Asha and Ben, so Asha is behind exactly when y>x

y-x starts at 0 and changes by 1 at each step, so it cannot pass 1 without equalling 1: a path with y>x somewhere touches y=x+1, and a path that touches it has y>x there

(c) at T=(t,t+1) the path still has 5-t steps (1,0) and 2-t steps (0,1) to make. After the swap it makes 2-t and 5-t, so it ends at (t+2-t,\ t+1+5-t)=(2,6)

M1A1

(2,6) lies above the line and (0,0) below it, so every path to (2,6) touches y=x+1; swapping its steps after the first touch gives back a touching path to (5,3). The two swaps undo each other, so the paths match in pairs

(d) touching paths = paths to (2,6)=\binom82=28

never behind: 56-28=28 orders, probability \frac{28}{56}=\frac12

(e) the first paper must be Asha's; from (1,0) the path must never touch y=x. There are \binom73=35 paths from (1,0) to (5,3)

those that touch y=x match, by the same swap, the paths from (1,0) to the reflection (3,5): \binom72=21

35-21=14 orders, probability \frac{14}{56}=\frac14

Final answer

(a) 56
(d) \frac12
(e) \frac14

G1 Investigation

[12 marks]

A path from (0,0) to (n,n) is made of n steps \mathrm{R}=(1,0) and n steps \mathrm{U}=(0,1). Call a path good if it never goes above the line y=x, and let g_n be the number of good paths.

(a) List the good paths for n=1, 2 and 3 as words in R and U, and count them.

[3]

(b) For n=1,2,3, calculate \binom{2n}{n}\div g_n. Conjecture a formula for g_n, and use it to predict g_4.

[2]

(c) Use the reflection argument of the worked example to prove your conjecture.

[4]

(d) Show that \dfrac{g_{n+1}}{g_n}=\dfrac{2(2n+1)}{n+2}, and find the limit of this ratio as n\to\infty.

[3]

Show solutionHide solution

(a) n=1: RU, so g_1=1

n=2: RRUU, RURU, so g_2=2

n=3: RRRUUU, RRURUU, RRUURU, RURRUU, RURURU, so g_3=5

(b) \frac21=2, \frac62=3, \frac{20}5=4: conjecture g_n=\dfrac{1}{n+1}\dbinom{2n}{n}

g_4=\frac{70}5=14

(c) a path is not good exactly when it touches y=x+1 (the argument of the worked example, part (b))

at the first touch (t,t+1) there remain n-t steps R and n-t-1 steps U; after the swap there are n-t-1 R and n-t U, so the path ends at (n-1,n+1); the swap can be undone, so bad paths match paths to (n-1,n+1) one to one

number of bad paths =\dbinom{2n}{n-1}

g_n=\dbinom{2n}{n}-\dbinom{2n}{n-1}=\dbinom{2n}{n}\left(1-\dfrac{n}{n+1}\right)=\dfrac1{n+1}\dbinom{2n}{n}, using \dbinom{2n}{n-1}=\dfrac{n}{n+1}\dbinom{2n}{n}

(d) \dfrac{g_{n+1}}{g_n}=\dfrac{n+1}{n+2}\times\dfrac{(2n+2)!\,n!\,n!}{(n+1)!\,(n+1)!\,(2n)!}

=\dfrac{n+1}{n+2}\times\dfrac{(2n+2)(2n+1)}{(n+1)(n+1)}, and 2n+2=2(n+1) cancels one factor n+1, leaving \dfrac{2(2n+1)}{n+2}

=\dfrac{4+\frac2n}{1+\frac2n}\to4

Final answer

(a) 1,2,5
(b) g_n=\frac{1}{n+1}\binom{2n}{n}, g_4=14
(d) 4

G2 Counting one set two ways

G2 Worked example

[11 marks]

A club has n members, where n\ge2.

(a) By counting in two ways the choices of a committee of r members, 1\le r\le n, together with a chair who is on the committee, show that r\binom nr=n\binom{n-1}{r-1}.

[3]

(b) Hence show that \displaystyle\sum_{r=1}^{n}r\binom nr=n\,2^{n-1}.

[2]

(c) By also choosing a secretary from the committee, different from the chair, show that r(r-1)\binom nr=n(n-1)\binom{n-2}{r-2} for 2\le r\le n. Hence find \displaystyle\sum_{r=2}^{n}r(r-1)\binom nr.

[4]

(d) Hence find \displaystyle\sum_{r=1}^{n}r^2\binom nr in a simplified form, and check your answer when n=3.

[2]

Show solutionHide solution

(a) committee first: \binom nr ways, then the chair: r ways, giving r\binom nr

chair first: n ways, then the other r-1 members from the remaining n-1: n\binom{n-1}{r-1}

both count the same choices, so r\binom nr=n\binom{n-1}{r-1}

R1AG

(b) \displaystyle\sum_{r=1}^{n}r\binom nr=n\sum_{r=1}^{n}\binom{n-1}{r-1}

=n\,2^{n-1}, since row n-1 of Pascal's triangle adds up to 2^{n-1}

(c) committee, then chair, then secretary: \binom nr\times r\times(r-1)

chair and secretary first: n(n-1) ways, then r-2 more from the other n-2: n(n-1)\binom{n-2}{r-2}

\displaystyle\sum_{r=2}^{n}r(r-1)\binom nr=n(n-1)\sum_{r=2}^{n}\binom{n-2}{r-2}

=n(n-1)2^{n-2}

(d) r^2=r(r-1)+r, so the sum is n(n-1)2^{n-2}+n\,2^{n-1}=n(n+1)2^{n-2}

check n=3: 1\times3+4\times3+9\times1=24 and 3\times4\times2=24

Final answer

(c) n(n-1)2^{n-2}
(d) n(n+1)2^{n-2} (24 when n=3)

G2 Investigation

[12 marks]

A group consists of n boys and n girls, where n\in\mathbb{Z}^+. A committee of n people is chosen from the group.

(a) For n=1,2,3,4,5, calculate \displaystyle\sum_{k=0}^{n}\binom nk^2 and compare it with \dbinom{2n}{n}.

[2]

(b) By sorting the possible committees according to the number k of boys, prove that \displaystyle\sum_{k=0}^{n}\binom nk^2=\binom{2n}{n}.

[3]

(c) Each committee now chooses a chair, who must be a boy. By counting these choices in two ways, show that \displaystyle\sum_{k=1}^{n}k\binom nk^2=n\binom{2n-1}{n-1}.

[4]

(d) Hence show that, over all \binom{2n}{n} committees, the mean number of boys is \dfrac n2. Explain why this answer could be expected.

[3]

Show solutionHide solution

(a) 2,\ 6,\ 20,\ 70,\ 252

these equal \binom21,\binom42,\binom63,\binom84,\binom{10}5

(b) a committee with k boys has n-k girls: \binom nk\binom n{n-k} choices

\binom n{n-k}=\binom nk, so this is \binom nk^2

every committee has exactly one value of k from 0 to n, so adding over k counts all \binom{2n}{n} committees once

(c) by the number of boys: a committee with k boys can choose its chair in k ways, giving k\binom nk^2

M1A1

chair first: n boys to choose from, then the other n-1 members from the remaining 2n-1 people: n\binom{2n-1}{n-1}

M1A1

(d) mean =\dfrac{\sum k\binom nk^2}{\binom{2n}n}=\dfrac{n\binom{2n-1}{n-1}}{\binom{2n}{n}}

\binom{2n-1}{n-1}=\dfrac{(2n-1)!}{(n-1)!\,n!}=\dfrac{n}{2n}\times\dfrac{(2n)!}{n!\,n!}=\frac12\binom{2n}n, so the mean is \dfrac n2

swapping boys and girls pairs each committee with k boys with one with n-k boys, so the numbers of boys average to \frac n2

Final answer

(a) 2,6,20,70,252, equal to \binom{2n}{n}
(d) \frac n2

TI-84 Plus CE keystrokes

The GDC panels in the book give keystrokes for the TI-Nspire CX II and the Casio fx-CG50. These are the TI-84 Plus CE keystrokes for the same calculator jobs. The full list of TI-84 keystrokes is in Chapter 19.

Job	TI-84 Plus CE keystrokes
Solve an equation	`MATH, Numeric Solver (MATH, 0:Solver on older OS versions): enter the equation, then SOLVE. Or graph both sides and use 2nd TRACE (CALC), 5:intersect`

From the book

The Ultimate Guide for the IB: Mathematics: Analysis and Approaches HL

Chapter 4 teaches counting principles from the basics to full exam questions: how the IB asks it, every question type with a marked example, and these practice questions in three steps.

About the book