| Exam Board | OCR |
|---|---|
| Module | Further Discrete (Further Discrete) |
| Year | 2020 |
| Session | November |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Permutations & Arrangements |
| Type | Correct ordering probability |
| Difficulty | Challenging +1.2 This is a multi-part Further Maths question on combinatorics requiring knowledge of Stirling numbers, derangements, and systematic counting. Part (a) requires the Stirling number formula S(8,2), parts (b-c) are straightforward counting/listing, but part (d) requires combining binomial selection with derangement counting. While conceptually accessible, the derangement formula and multi-step reasoning place it moderately above average difficulty for A-level, though standard for Further Maths discrete topics. |
| Spec | 5.01a Permutations and combinations: evaluate probabilities7.01b Set notation: basic language and notation of sets, partitions7.01e Permutations: ordered subsets of r from n elements7.01g Arrangements in a line: with repetition and restriction7.01m Derangements: enumeration by ad hoc methods |
| Answer | Marks | Guidance |
|---|---|---|
| 4 | (a) | 28 = 256 ways to assign 8 items to 2 sets |
| Answer | Marks |
|---|---|
| Total = 127 (as given) | M1 |
| Answer | Marks |
|---|---|
| A1 | 28 (or 256) and later dividing by 2 |
| Answer | Marks |
|---|---|
| Alternative method | M1 |
| Answer | Marks |
|---|---|
| 1 | 8 ways to partition as a set of size 1 and a set of size 7 |
| Answer | Marks |
|---|---|
| 2 | (or any other 8C evaluated, where r = 2, 3, 4, 5 or 6) |
| Answer | Marks | Guidance |
|---|---|---|
| 4 | M1 | Dividing by 2, including 8C ÷ 2 = 35 |
| Answer | Marks | Guidance |
|---|---|---|
| Total = 127 (as given) | A1 | To achieve 127 from valid reasoning |
| Answer | Marks | Guidance |
|---|---|---|
| 4 | (b) | 8 × 7 × 6 × 5 |
| =1680 | M1 |
| Answer | Marks |
|---|---|
| [2] | Or attempt at 8P or (4! × 8C ) |
| Answer | Marks | Guidance |
|---|---|---|
| 4 | (c) | Seat 5 F H G F G H F G H |
| Answer | Marks |
|---|---|
| Seat 8 G G F G F F E E E | M1 |
| Answer | Marks |
|---|---|
| [3] | All nine columns completed |
| Answer | Marks | Guidance |
|---|---|---|
| 4 | (d) | 8C = 70 ways to choose four people to be in correct seats |
| Answer | Marks |
|---|---|
| 70 × 9 = 630 | M1 |
| Answer | Marks |
|---|---|
| [2] | Appropriate use of 8C |
| Answer | Marks | Guidance |
|---|---|---|
| Seat 5 | F | H |
| Seat 6 | E | E |
| Seat 7 | H | F |
| Seat 8 | G | G |
Question 4:
4 | (a) | 28 = 256 ways to assign 8 items to 2 sets
Order does not matter so divide by 2
Cannot have a set of size 0 and a set of size 8
Total = 127 (as given) | M1
M1
A1 | 28 (or 256) and later dividing by 2
Dealing with the case(s) where one set is empty
To achieve 127 from valid reasoning
Alternative method | M1
Set of 1 and set of 7 = 8C = 8 ways
1 | 8 ways to partition as a set of size 1 and a set of size 7
Set of 2 and set of 6 = 8C = 28 ways
2 | (or any other 8C evaluated, where r = 2, 3, 4, 5 or 6)
r
Set of 3 and set of 5 = 8C = 56 ways
3
Two sets of 4 = 8C ÷ 2 = 35 ways
4 | M1 | Dividing by 2, including 8C ÷ 2 = 35
4
Total = 127 (as given) | A1 | To achieve 127 from valid reasoning
[3]
4 | (b) | 8 × 7 × 6 × 5
=1680 | M1
A1
[2] | Or attempt at 8P or (4! × 8C )
4 4
1680
4 | (c) | Seat 5 F H G F G H F G H
Seat 6 E E E H H G G H G
Seat 7 H F H E E E H F F
Seat 8 G G F G F F E E E | M1
M1
A1
[3] | All nine columns completed
Each column contains all four letters, even if people are in
their designated seat(s) or there are repeated columns
At least three different columns
At least three different correct derangements
All nine correct (in any order)
4 | (d) | 8C = 70 ways to choose four people to be in correct seats
4
9 derangements of the other four people
70 × 9 = 630 | M1
A1
[2] | Appropriate use of 8C
4
630
M1
Seat 5 | F | H | G | F | G | H | F | G | H
Seat 6 | E | E | E | H | H | G | G | H | G
Seat 7 | H | F | H | E | E | E | H | F | F
Seat 8 | G | G | F | G | F | F | E | E | E4
\begin{enumerate}[label=(\alph*)]
\item Show that there are 127 ways to partition a set of 8 distinct elements into two non-empty subsets.
A group of 8 people ( $\mathrm { A } , \mathrm { B } , \ldots$ ) have 8 reserved seats ( $1,2 , \ldots$ ) on a coach. Seat 1 is reserved for person A , seat 2 for person B , and so on. The reserved seats are labelled but the individual people do not know which seat has been reserved for them.
The first 4 people, $\mathrm { A } , \mathrm { B } , \mathrm { C }$ and D , choose their seats at random from the 8 reserved seats.
\item Determine how many different arrangements there are for the seats chosen by $\mathrm { A } , \mathrm { B } , \mathrm { C }$ and D .
The group organiser moves $\mathrm { A } , \mathrm { B } , \mathrm { C }$ and D to their correct seats (A in seat $1 , \mathrm {~B}$ in seat $2 , \mathrm { C }$ in seat 3 and D in seat 4).\\
The other 4 people ( $\mathrm { E } , \mathrm { F } , \mathrm { G }$ and H ) then choose their seats at random from the remaining 4 reserved seats ( $5,6,7$ and 8 ).
\item List the 9 derangements of $\{ \mathrm { E } , \mathrm { F } , \mathrm { G } , \mathrm { H } \}$, where none of these four people is in the seat that has been reserved for them.
Suppose, instead, that the 8 people had chosen their seats at random from the 8 reserved seats, without the organiser intervening.
\item Determine the total number of ways in which the seats can be chosen so that 4 of the people are in their correct seats and 4 are not in their correct seats.
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete 2020 Q4 [10]}}