I forgot how to do stars and bars (1 Viewer)

[leehuan]

^

In how many ways can five students be placed in three distinct rooms so that no room is empty?


Please demo, thanks

 

[InteGrand]

^

In how many ways can five students be placed in three distinct rooms so that no room is empty?


Please demo, thanks

Stars and bars would be if the five objects to be placed (students here) were identical, which is not the case here. One way to do it is as follows.

Call the rooms 1, 2, 3. Let U be the set of all possible arrangements without restrictions, and let S_k be the set of all arrangements if room k is empty (k = 1, 2, 3). Then we are after the value of |S₁^c ∩ S₂^c ∩ S₃^c|, which is equal to |U| – |S₁ ∪ S₂ ∪ S₃|.

Since the students and rooms are distinct, we have |U| = 3⁵ (each student could go in any of three rooms).

Now, note |S₁| = 2⁵ (if room 1 is empty, each of the five students can go in one of two rooms). By symmetry, |S₂| = |S₃| = 2⁵.

Now, |S₁ ∩ S₂| = 1 (if rooms 1 and 2 are to be empty, only one way to arrange the students, namely by putting them all in the last room). By symmetry, the other two pairwise intersections have cardinality 1.

Also, |S₁ ∩ S₂ ∩ S₃| = 0 (if all rooms are empty, 0 ways to arrange the students).

So

Answer = |U| – |S₁ ∪ S₂ ∪ S₃|

= |U| – (3|S₁| – 3|S₁ ∩ S₂| + |S₁ ∩ S₂ ∩ S₃|) (using the inclusion/exclusion principle)

= 3⁵ – (3×2⁵ – 3×1 + 0)

= 150.

 

[leehuan]

Far out. Forgot about the identical condition. (Thanks lol I needed it for some other things)