Social promotion distributions

Relevant wiki: Distinct Objects into Distinct Bins

This problem can be modeled as $6$ distinct objects distributed into $3$ distinct bins, with none of the bins left empty.

Let $U$ be the set of distributions of these objects, disregarding the restriction that each bin receives one object. $|U|=3^6=729$ .

Let $A$ be the set of distributions of the 6 objects into the 2nd and 3rd bins, let $B$ be the set of distributions of the objects into the 1st and 3rd bins, and let $C$ be the distribution of the objects into the 1st and 2nd bins. Without loss of generality, $|A|=|B|=|C|=2^6=64$

$A\cap B$ is the set of distributions of the 6 objects into the 3rd bin. There is only one way to distribute all 6 objects into 1 bin, so $|A\cap B|=1$ . Without loss of generality, $|A\cap B|=|A\cap C|=|B\cap C|$ .

It is not possible for all three bins to be empty, so $|A\cap B\cap C|=0$ .

$A \cup B \cup C$ is the set of all distributions of the objects in which at least one of the bins is empty. $A \cup B \cup C$ can be found using the principle of inclusion and exclusion :

$|A\cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$ $|A\cup B \cup C| = 64+64+64-1-1-1+0=189$

The problem asks for the size of the complement of this set, $|U|-|A\cup B\cup C|$ . Therefore, there are $729-189=\boxed{540}$ ways to distribute the awards to the students.

Answer : 3! S(6,3) = 6 x 90 = 540

(Watch my previous question answer and come here)