# Probability that exactly k men are chosen by 5 women

Five young women and three young men are friends. One night, each of the women calls one of the men, whom she chooses at random. Find the probability that exactly k men are called for k = 1,2, and 3.

I'm having trouble understanding why I got this answer, which apparently is correct.

This is what I did:

The number of ways to choose 1 man from 3 men is 3. Now, the number of ways for 5 women to choose the same man from 3 is 243 (from 3^5). So then, choosing the same man is 3c1 or 3. So probability that exactly 1 man is called is 3/243.

Now, if anyone could explain me how this answer is correct, that would be great. The largest part I am having trouble understanding is why do we use 3 choose 1 on top of 243?

Also how would you do this for k=2 or 3? Thank you

For the case $k=1$:

$P(\text{exactly one man is chosen})=P(\text{only man #1 is chosen})+P(\text{only man #2 is chosen})+P(\text{only man #3 is chosen})$

(The above equation is where there are ${3\choose 1}$ terms).

For all $i=1,2,3$, $P(\text{only man #i is chosen})=P(\text{woman #1 chose man #i})\times P(\text{woman #2 chose man #i})\times\dots\times P(\text{woman #5 chose man #i})=1/3^5$

Since each of the terms in the first equation works out to be $1/3^5$, the result is ${3\choose 1}/3^5$.

Try the other cases, and see if you can get the right logic.

Hint: You can get the probability that exactly men #1 and #2 are selected by finding the probability that only #1 and #2 can be selected and then subtracting the cases when only #1 is selected or #2 is selected. The general case is actually an application of the general principle for inclusion exclusion.

• Thanks for the hint - that actually helped me the most. So I can take the probability that exactly 2 men are chosen, which came out to 30/243 then multiplied that by 3 since there are 3 different possibilities of choosing exactly 2 people. – rrpking Mar 20 '15 at 6:50
• @rrpking Yes, exactly what Graham described. – user1537366 Mar 20 '15 at 6:56
• @rrpking See my other answer for the general case. – user1537366 Mar 20 '15 at 7:21

Each of $5$ women has $1/3$ chance of choosing a particular man, and there are $3$ men to so choose from.   So the probability of all $5$ women choosing the same man is, the ways to select a particular man times the probability of all women choosing that particular man: $$\binom 3 1\times \frac{1^5}{3^5}$$

Similarly the probability they will choose exactly two of the men is: the ways to choose two particular men times the probability of all women choosing either of those particular men, but excluding the cases where all women choose the same man of that pair.

$$\binom 3 2\times\frac{(2^5-\binom{2}{1}\times 1^5)}{3^5}$$

Can you do the third?

• Are you sure about the $\binom21$ there? – barak manos Mar 20 '15 at 7:06
• @barakmanos Yes. There are $2^5-2$ ways $5$ choices can be made between $2$ options such that they are not all the same option. – Graham Kemp Mar 20 '15 at 7:30

The total number of combinations is:

$$C=3^5$$

The number of combinations with at least $k$ men is:

$$C_{k}={\binom{3}{k}}\cdot{k^5}$$

The number of combinations with exactly $k$ men is:

$$C_{k}-C_{k-1}={\binom{3}{k}}\cdot{k^5}-{\binom{3}{k-1}}\cdot{(k-1)^5}$$

So the probability of choosing exactly $k$ men is:

$$P(k)=\frac{{\binom{3}{k}}\cdot{k^5}-{\binom{3}{k-1}}\cdot{(k-1)^5}}{3^5}$$

Therefore:

• $P(1)=\dfrac{ 1}{81}\approx 1.23\%$

• $P(2)=\dfrac{31}{81}\approx38.27\%$

• $P(3)=\dfrac{49}{81}\approx60.50\%$

Count the functions $f:\{1,2,...,n\}\to\{1,2,...,m\}$ which are surjective.

Let $M=\{1,2,...,m\}$. Let $U$ be the set of functions $f:\{1,2,...,n\}\to M$. Let $Q$ be the set of such functions which are surjective. Let $A_k$ be the functions $f$ s.t. $\text{Range}(f)$ does not cover $k$. Then $Q=U\setminus\bigcup_{k\in M} A_k$, so $|Q|=|U|-|\bigcup_{k\in M} A_k|$.

Now $|\bigcup_{k\in m} A_k|=\sum_{k\in M} |A_k|-\sum_{\text{distinct }j,k \in M}|A_j\cap A_k|+\cdots$.

• $=\sum_{i=1}^m (-1)^{i-1} {m\choose i}(m-i)^n$

So $|Q|=\sum_{i=0}^m (-1)^i {m\choose i}(m-i)^n$. Let this be $T_{n,m}$.

Now the number of such functions that cover exactly $k$ elements is ${m\choose k}T_{n,k}$.

Alternatively, $T_{n,m}=m!\times S_{n,m}$ where $S_{n,m}$ is the number of partitions of $n$ elements into exactly $m$ groups (some Stirling's number; I can't remember which). Try to see why this is so.