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?
  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?

For part $\textit{(i)},$ how many balls should be placed in each bucket?

For part $\textit{(ii)},$ what is the maximum number of balls in a bucket?

How many buckets must contain the maximum number of balls?

How many combinations of balls are there for the bucket containing $2$ balls?

How many possible choices are there for the bucket containing $2$ balls?

Once $2$ balls are placed into an arbitrary bucket, what is the distributions (or configuration) for the remaining balls in the remaining buckets?

How many ways are there to distribute $(n-2)$ balls in $(n-1)$ buckets, with at most $1$ ball per bucket?

Consider the first ball of the remaining $(n-2)$ balls that you place. How many buckets are there to choose from?

After the above first 3 balls are placed, what about the number of possible choices for the next ball?

$\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!.$