$\begingroup$

Question: In how many ways can you select $r$ people from $y$ groups of people if the groups contain $\{x_1,x_2, \ldots,x_y\}$ people, respectively, where $x_1+x_2+ \ldots +x_y=n$, given that you cannot select more than one person from each group (every person is distinct).

I could only think of the most basic approach where, for example, if I have to select $2$ people from a group of $\{2,2,1\}$ people, my answer would be $2.(2+1)+2.1=8$.

$\endgroup$ 1

2 Answers

$\begingroup$

You need to select $r$ groups, and from each group 1 person, so if in every group $j$ there are $x_j$ people, you have $ \binom{y}{r}$ to choose $r$ groups from $y$. Denote each selected group $\gamma_j$, and the number of people in each group $x_{\gamma_{j}}$. You need to select exactly one person from each, so the total number of ways of selecting $r$ people from $r$ groups would be $x_{\gamma_{1}} x_{\gamma_2} \ldots x_{\gamma_{r}}$. Now put together these two expressions.

$\endgroup$ 0 $\begingroup$

I cannot see a direct formula.

In my humble opinion since you cannot select more than one person per group, selecting r person mean selecting r group. So using your notation (nbr of person per group) $\{x_1,x_2,…,x_y\}$ to name the groups.

We can find the $y\choose r$ subsets of the groups $\{x_1,x_2,…,x_y\}$ , for every subsets of size r, the number of possibilities is simply those r terms $x_i$ multiply together.Then you add all those probabilities to get the final answer.

Here is an example:

Let take 5 groups $\{x_1,x_2,x_3,x_4,x_5\}$ of respectively $\{4,3,2,2,1\}$ persons.

let select 3 persons from that. you have those $5\choose 3$=10 subsets:

$\{x_1,x_2,x_3\}=\{4,3,2\}$ so 4*3*2=24 possibilities

$\{x_1,x_2,x_4\}=\{4,3,2\}$ so 4*3*2=24 pos

$\{x_1,x_2,x_5\}=\{4,3,1\}$ so 4*3*1=12 pos

$\{x_1,x_3,x_4\}=\{4,2,2\}$ so 4*2*2=16 pos

$\{x_1,x_3,x_5\}=\{4,2,1\}$ so 4*2*1=8 pos

$\{x_1,x_4,x_5\}=\{4,2,1\}$ so 4*2*1=8 pos

$\{x_2,x_3,x_4\}=\{3,2,2\}$ so 3*2*2=12 pos

$\{x_2,x_3,x_5\}=\{3,2,1\}$ so 3*2*1=6 pos

$\{x_2,x_4,x_5\}=\{3,2,1\}$ so 3*2*1=6 pos

$\{x_3,x_4,x_5\}=\{2,2,1\}$ so 2*2*1=4 pos

now you can sum those possibilities 4+6+6+12+8+8+16+12+24+24=120.

Thus there is 120 ways to select 3 persons from those 5 groups with max one person from each group.

There might be a clever way to see this and thus find a faster way/formula to solve this but I don't see it right now.

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy