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.

The Computer Laboratory

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 oi.foo[email protected]. Please do not write to this address regarding general admissions or course queries.