Questions on combinatorics

Question 1

From 10 different letters, how many ordered strings of 4 can be made, and how many unordered selections of 4?

Accepted Answer

Ordered: 10 × 9 × 8 × 7 = 5040, which is ¹⁰P₄. Unordered: divide by the 4! = 24 orderings of each selection, giving 210 = ¹⁰C₄. M1 A1 for the ordered count, A1 for the unordered count. The two always differ by a factor of exactly r!.

Question 2

In how many ways can 8 people be seated round a circular table, if only their positions relative to each other matter?

Accepted Answer

Fix one person to remove the rotational freedom, then arrange the other 7 in the remaining seats: 7! = 5040 ways. M1 for fixing one person, A1 for 5040. Counting 8! would treat each arrangement as 8 different ones, once for each rotation.

Question 3

A set has 7 elements. Write down how many subsets it has altogether, and how many of those subsets have exactly 3 elements.

Accepted Answer

Each element is independently in or out of a subset, so there are 2⁷ = 128 subsets in all. Those with exactly 3 elements number ⁷C₃ = 35. B1 for 128, B1 for 35. Adding ⁷C_r over r = 0 to 7 gives 128 as well, which is the same count taken one size at a time.

Question 4

How many of the integers from 1 to 999 inclusive contain the digit 3 at least once?

Accepted Answer

Count the complement. Written with leading zeros allowed, the whole numbers from 000 to 999 are the 10³ = 1000 strings of three digits. A string avoiding the digit 3 has 9 choices in each place, so there are 9³ = 729 of them. That leaves 1000 − 729 = 271 strings carrying a 3, and 000 is not one of them, so all 271 correspond to integers from 1 to 999. M1 for counting the strings that avoid the digit, A1 for 729, A1 for 271. Counting directly means splitting into one-digit, two-digit and three-digit numbers and then handling the numbers with two or three 3s in them; the complement replaces all of that with one subtraction.

Question 5

How many distinct arrangements are there of the letters of STATISTICS?

Accepted Answer

There are 10 letters, with S appearing 3 times, T 3 times and I twice; A and C appear once each. Dividing the 10! orderings by the indistinguishable rearrangements gives 10!/(3! 3! 2!) = 3628800/72 = 50400. M1 for 10! over the repeats, A1 for the divisor, A1 for the total.

Question 6

A committee of 5 is chosen from 5 women and 7 men. How many committees contain at least 2 women?

Accepted Answer

Total committees: ¹²C₅ = 792. Count the complement instead. No women: ⁷C₅ = 21. Exactly one woman: 5 × ⁷C₄ = 5 × 35 = 175. So the answer is 792 − 21 − 175 = 596. M1 for a complete method, A1 for the no-women count, A1 for the one-woman count, A1 for 596. Adding the cases with 2, 3, 4 and 5 women gives the same total in four times the work.

Question 7

How many integers from 1 to 500 inclusive are divisible by 3 or by 5?

Accepted Answer

Multiples of 3: 166. Multiples of 5: 100. Multiples of 15, counted in both: 33. By inclusion and exclusion the answer is 166 + 100 − 33 = 233. M1 for the three counts, A1 for subtracting the overlap, A1 for 233. Forgetting the overlap gives 266 and counts every multiple of 15 twice.

Question 8

Explain why, among any seven integers, there must be two whose difference is a multiple of 6, and state whether six integers are enough to force this.

Accepted Answer

Sort the integers into boxes by their remainder on division by 6. There are only six possible remainders, 0 to 5, so the boxes number six. B1 for choosing remainders as the boxes. Seven integers into six boxes put two in the same box, by the pigeonhole principle. M1 for applying it. Two integers with the same remainder differ by a multiple of 6, which is the claim. A1 for the conclusion. Six integers are not enough: 0, 1, 2, 3, 4, 5 take one box each and no two differ by a multiple of 6. B1 for a counterexample.

Question 9

A student chooses 3 modules from a list of 7. Two of the seven, P and Q, are timetabled at the same time, and so are two others, R and S, so neither of those pairs may both be chosen. How many selections are possible?

Accepted Answer

Without restriction there are ⁷C₃ = 35 selections. Those containing both P and Q are fixed apart from one more module chosen from the remaining 5, so there are ⁵C₁ = 5 of them, and by the same count 5 contain both R and S. No selection of three can contain all four of P, Q, R and S, so the two forbidden sets do not overlap and nothing is subtracted twice. The answer is 35 − 5 − 5 = 25. B1 for 35, M1 for counting the selections that break one restriction, A1 for 5 in each case, A1 for 25. Checking that the two forbidden sets are disjoint is part of the method, not a formality: with 4 modules chosen from 7 instead, the selections holding both pairs would be counted twice and would have to be added back.

Question 10

The six letters of the word BANANA are arranged in a row at random, all distinct arrangements being equally likely. Find the probability that the arrangement begins and ends with the letter A.

Accepted Answer

The distinct arrangements number 6!/(3!2!) = 720/12 = 60, dividing by the rearrangements of the three A's and the two N's. If the first and last letters are A's, the remaining four places hold A, B, N and N, giving 4!/2! = 12 arrangements. The probability is 12/60 = 1/5. M1 for 60 arrangements in all, A1 for the 12 favourable ones, A1 for 1/5. Both counts must treat the letters the same way. Counting the 6! orderings on top and the 12 restricted arrangements underneath mixes two different sample spaces and gives the wrong probability.

Question 11

In how many arrangements of the eleven letters of MISSISSIPPI are the two P's not next to each other?

Accepted Answer

Deal with the other nine letters first: M, four I's and four S's arrange in 9!/(4!4!) = 362880/576 = 630 ways. Each such arrangement leaves 10 gaps, one at each end and eight between letters, and putting the two P's into two different gaps keeps them apart. The P's are identical, so the gaps are chosen and not ordered: ¹⁰C₂ = 45 ways. The total is 630 × 45 = 28350. M1 for arranging the other nine letters, A1 for 630, M1 for choosing two of the ten gaps, A1 for 28350. Checking by the other route: all eleven letters arrange in 11!/(4!4!2!) = 34650 ways, and gluing the two P's into a single block leaves ten objects arranging in 10!/(4!4!) = 6300 ways, and 34650 − 6300 = 28350.

Question 12

Show that a set of 10 elements has exactly 512 subsets with an even number of elements.

Accepted Answer

The total number of subsets is 2¹⁰ = 1024, since each element is independently in or out. Expanding (1 − 1)¹⁰ by the binomial theorem gives the alternating sum of the ¹⁰C_r, which is 0, so the even-sized and odd-sized subsets are equal in number. Each group therefore has 1024/2 = 512 members. B1 for the total number of subsets, M1 for the binomial expansion, A1 for the alternating sum being zero, M1 for concluding that the two groups are equal, A1 for the printed result.

Question 13

Use the recurrence S(n, k) = S(n − 1, k − 1) + kS(n − 1, k) to find S(6, 3), the number of partitions of a set of six objects into three non-empty parts, and check the value by counting the partitions by the sizes of their parts.

Accepted Answer

The recurrence gives S(6, 3) = S(5, 2) + 3S(5, 3) = 15 + 3 × 25 = 90. M1 for the recurrence with the right inputs, A1 for 90. Now the check. Three non-empty parts holding six objects have sizes 4, 1, 1 or 3, 2, 1 or 2, 2, 2, and no other pattern totals six. Sizes 4, 1, 1: choose the four that go together, ⁶C₄ = 15. Sizes 3, 2, 1: ⁶C₃ × ³C₂ = 20 × 3 = 60. Sizes 2, 2, 2: 6!/(2!2!2!) = 90 ordered triples of pairs, divided by the 3! orders of the three pairs, giving 15. M1 for the complete list of size patterns, A1 for the three counts, A1 for 15 + 60 + 15 = 90 agreeing with the recurrence. Forgetting to divide by 3! in the last case counts each split six times over, because the parts of a partition carry no order.

Question 14

Five letters are put at random into five addressed envelopes, one letter to each envelope. Let D(n) be the number of ways of placing n letters so that none reaches its own envelope. Show that D(n) = (n − 1)[D(n − 1) + D(n − 2)], and hence find the probability that none of the five letters reaches its own envelope.

Accepted Answer

Take the letter numbered 1. It may go into any of the n − 1 other envelopes, say envelope k. Now split on where letter k goes. If letter k goes into envelope 1, the pair has swapped and the remaining n − 2 letters must avoid their own envelopes, in D(n − 2) ways. If letter k does not go into envelope 1, then each of the remaining n − 1 letters has exactly one forbidden envelope: its own, except that letter k's forbidden envelope is envelope 1. That is the same problem for n − 1 letters, in D(n − 1) ways. Multiplying by the n − 1 choices for k gives the recurrence. M1 for the n − 1 choices, M1 for splitting on where letter k goes, A1 for the recurrence. With D(1) = 0 and D(2) = 1: D(3) = 2(0 + 1) = 2, D(4) = 3(2 + 1) = 9 and D(5) = 4(9 + 2) = 44. There are 5! = 120 placings in all, so the probability is 44/120 = 11/30. A1 for 44, A1 for 11/30. The second case is the one worth stating carefully: relabelling envelope 1 as letter k's own envelope turns it into the smaller problem unchanged.

Question 15

Explain why n people can be seated round a circular table in (n − 1)! ways when only their positions relative to each other matter, and hence find the number of ways of seating 7 people round such a table with two particular people not next to each other.

Accepted Answer

Seat one person first. That choice costs nothing, because the seats are told apart only by who sits where relative to everyone else, and any arrangement can be rotated until that person is in the chosen seat. The other n − 1 people then fill distinguishable places, in (n − 1)! ways. B1 for fixing one person, B1 for (n − 1)! with the rotation argument. For 7 people that is 6! = 720 seatings. Now count the seatings that break the condition. Glue the two particular people into one block: the block and the other 5 people make 6 objects round the table, seated in 5! = 120 ways, and the two inside the block may be either way round, giving 120 × 2 = 240. M1 for gluing the pair into a block, A1 for 5! × 2 = 240. Subtracting, 720 − 240 = 480 seatings keep them apart. M1 for subtracting from the total, A1 for 480. The block argument has to be run round the table too: treating the block as one of 6 objects in a line would give 6! × 2 = 1440, which is larger than the 720 seatings that exist.