The CSAT and Practice[+] are designed by the Climb Foundation to help candidates. We are advocates for more opportunity to shine and less opportunity to fail, and we strive to level the playing field. # 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?

The above links are provided as is. They are not affiliated with the Climb Foundation unless otherwise specified.

## Warm-up Questions

1. You have a bag of $$13$$ sweets, each of different flavours. How many combinations of $$5$$ sweets can you form?
2. 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?
3. $$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 1
For part $$\textit{(i)},$$ how many balls should be placed in each bucket?
• Hint 2
For part $$\textit{(ii)},$$ what is the maximum number of balls in a bucket?
• Hint 3
How many buckets must contain the maximum number of balls?
• Hint 4
How many combinations of balls are there for the bucket containing $$2$$ balls?
• Hint 5
How many possible choices are there for the bucket containing $$2$$ balls?
• Hint 6
Once $$2$$ balls are placed into an arbitrary bucket, what is the distributions (or configuration) for the remaining balls in the remaining buckets?
• Hint 7
How many ways are there to distribute $$(n-2)$$ balls in $$(n-1)$$ buckets, with at most $$1$$ ball per bucket?
• Hint 8
Consider the first ball of the remaining $$(n-2)$$ balls that you place. How many buckets are there to choose from?
• Hint 9
After 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 . Please do not write to this address regarding general admissions or course queries.