# Practice Paper 2 Question 17

You have \(n\) balls numbered \(1,2,\ldots,n\) that you are placing in \(n\) distinct buckets. In how many ways can you do this such that: \(\textit{(i)}\) no bucket remains empty? \(\textit{(ii)}\) exactly one bucket remains empty?

## Related topics

## Warm-up Questions

- You have a bag of \(13\) sweets, each of different flavours. How many combinations of \(5\) sweets can you form?
- A mixed lacrosse team is to consist of \(6\) boys and \(6\) girls. In how many ways can this team be assembled given the coach has \(8\) boys and \(10\) girls to choose from?
- \(10\) athletes run a race, but one particular athlete had an accident and will be last on the scoreboard. How many possible rankings are there?

## Hints

- Hint 1For part \(\textit{(i)},\) how many balls should be placed in each bucket?
- Hint 2For part \(\textit{(ii)},\) what is the maximum number of balls in a bucket?
- Hint 3How many buckets must contain the maximum number of balls?
- Hint 4How many combinations of balls are there for the bucket containing \(2\) balls?
- Hint 5How many possible choices are there for the bucket containing \(2\) balls?
- Hint 6Once \(2\) balls are placed into an arbitrary bucket, what is the distributions (or configuration) for the remaining balls in the remaining buckets?
- Hint 7How many ways are there to distribute \((n-2)\) balls in \((n-1)\) buckets, with at most \(1\) ball per bucket?
- Hint 8Consider the first ball of the remaining \((n-2)\) balls that you place. How many buckets are there to choose from?
- Hint 9After the above first 3 balls are placed, what about the number of possible choices for the next ball?

## Solution

\(\textit{(i)}\) All buckets must each contain one ball. For the first bucket, there are \(n\) balls that we may choose from. In the second bucket, there are \((n-1),\) and so on. We therefore get \(n!\) permutations.

\(\textit{(ii)}\) The condition is equivalent to exactly one bucket having \(2\) balls, one bucket having \(0\) balls, and the rest having \(1\) ball each.

- Consider the bucket containing \(2\) balls. There are \(n\) choices for this bucket, and \(\binom{n}{2}\) possible combinations to select 2 out of \(n\) balls.
- We are then left with \((n-2)\) balls to distribute between \((n-1)\) buckets, with no more than \(1\) ball per bucket. For our first ball, there are \((n-1)\) buckets to choose from. For our second ball, there are \((n-2)\) buckets to choose from, and so on until the last ball, which has \(2\) buckets as possible choices.
- This leaves us with \(1\) empty bucket, as required.

Multiplying, we get \(\binom{n}{2} \cdot n \cdot (n-1)!= \binom{n}{2}n!.\)

If you have queries or suggestions about the content on this page or the CSAT Practice Platform then you can write to us at oi.. Please do not write to this address regarding general admissions or course queries. tasc@sulp.ecitcarp