$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?
-
- 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?
- You have a bag of
-
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!.$ - Consider the bucket containing