# In how many ways can $5$ students be chosen such that at least one student is chosen from each state?

There are $3$ states and $3$ students representing each state. In how many ways can $5$ students be chosen such that at least one student is chosen from each state?

According to me, the answer should be $3C1 \cdot 3C1 \cdot 3C1 \cdot 6C2$, but this answer is wrong.

• It is easier to count the complement. Find how many ways you can leave out one of the states (you can not leave out two states since each state has only 3 representative). – user348749 Sep 21 '17 at 8:59

Hint. Think to the complement. How many ways can 5 students be chosen such that no student is chosen from state $i\in \{1,2,3\}$? Note that in a group of $5$ students we always have the representatives of at least two distinct states. Hence the result should be $$\binom{9}{5}-3\cdot \binom{?}{5}.$$

• Thanks. Got the answer as 108. – Zephyr Sep 21 '17 at 9:20
• Can you tell me why is the approach which I mentioned in the question wrong ? @Robert Z – Zephyr Sep 21 '17 at 9:20
• @Zephir It is wrong because you count some cases multiple times (this gives a result greater than 108). – Robert Z Sep 21 '17 at 9:32

Suppose the representatives of state $A$ are $a, b, c$, the representatives of state $B$ are $d, e, f$, and the representatives of state $C$ are $g, h, i$. You count the selection $\{a, b, c, d, g\}$ three times, once for each of the ways we could choose a representative of state $A$.

$a, d, g, \qquad b, c$

$b, d, g, \qquad a, c$

$c, d, g, \qquad a, b$

and the selection $\{a, b, d, e, g\}$ four times, once for each of the ways we could pick a representative of state $A$ and once for each of the ways we could pick a representative of state $B$.

$a, d, g, \qquad b, e$

$a, e, g, \qquad b, d$

$b, d, g, \qquad a, e$

$b, e, g, \qquad a, d$

If we do a direct count, the number of permissible selections is $$\binom{3}{3}\binom{3}{1}\binom{3}{1} + \binom{3}{1}\binom{3}{3}\binom{3}{1} + \binom{3}{1}\binom{3}{1}\binom{3}{3} + \binom{3}{2}\binom{3}{2}\binom{3}{1} + \binom{3}{2}\binom{3}{1}\binom{3}{2} + \binom{3}{1}\binom{3}{2}\binom{3}{2} = 3\binom{3}{3}\binom{3}{1}^2 + 3\binom{3}{2}^2\binom{3}{1}$$ Your answer $\binom{3}{1}\binom{3}{1}\binom{3}{1}\binom{6}{2}$ counts each of the first three terms three times and each of the last three terms four times. Notice that $$3 \cdot 3\binom{3}{3}\binom{3}{1}^2 + 4 \cdot 3 \binom{3}{2}^2\binom{3}{1} = \binom{3}{1}^3\binom{6}{2}$$

As RobertZ and Muralidharan indicated, it is easier to subtract the number of cases in which exactly two states are represented from the total number of ways of selecting five representatives from the nine available people.

Consider the following ways of choosing 5 students such that at least one student is chosen from each state : (each of the ways are mutually exclusive from one another)

2 [state 1] | 2 [state 2] | 1 [state 3] : 3C2 * 3C2 * 3C1 = 3 * 3 * 3 = 27

2 [state 1] | 1 [state 2] | 2 [state 3] : 3C2 * 3C1 * 3C2 = 3 * 3 * 3 = 27

1 [state 1] | 2 [state 2] | 2 [state 3] : 3C1 * 3C2 * 3C2 = 3 * 3 * 3 = 27

3 [state 1] | 1 [state 2] | 1 [state 3] : 3C3 * 3C1 * 3C1 = 1 * 3 * 3 = 9

1 [state 1] | 3 [state 2] | 1 [state 3] : 3C1 * 3C3 * 3C1 = 3 * 1 * 3 = 9

1 [state 1] | 1 [state 2] | 3 [state 3] : 3C1 * 3C1 * 3C3 = 3 * 3 * 1 = 9

So total number of ways are : 27 * 3 + 9 * 3 = 108.

Consider the following situation :

• State 1 has student number 1, 2 and 3.
• State 2 has student number 4, 5 and 6.
• State 3 has student number 7, 8 and 9.

Now your method will consider these two ways different :

a) choose(1) choose(4) choose(7) choose(2,3).

b) choose(2) choose(4) choose(7) choose(1,3).

But in actual they are same. Therefore, Your intended solution over calculates number of ways.

• @Zephyr : Consider the following : state 1 has student number 1, 2 and 3. state 2 has student number 4, 5 and 6. state 3 has student number 7, 8 and 9. Now your method will consider these two ways different : a) choose(1) choose(4) choose(7) choose(2,3) b) choose(2) choose(4) choose(7) choose(1,3), but in actual they are same. Therefore, your solution over calculates number of ways. – JVJ Sep 21 '17 at 9:27