For every $N ∈ r, n$
$P(n,r) = \sum_{k=0}^{r}\binom{r}{k}P(n-m,k)P(m,r-k)$
Prove this combinatorially.
Answer:
The class has m boys and n - m girls. In what ways can r students be selected for different roles? On the one hand, the answer is P(n , r) because the order of choice is important and there are no repetitions
On the other hand, all options divide into 1 + r types: choosing k girls and r - k boys,
where $0\leq $ k $\leq $ r.
Now, choosing k roles for k girls in $\binom{r}{k}$ ways.
And then the roles for the boys are unequivocally determined (the boys will occupy k − r roles remaining).
Now, given in k roles for girls, there are P(n - m, k) options to choose girls with importance for roles. And for k - r roles for boys, there are P(m, r-k) ways choosing options for boys with importance to roles
According to multiplication rule, for k girls there are $\binom{r}{k}P(n-m,k)P(m,r-k)$ ways
According to the addition rule, $\sum_{k=0}^{r}\binom{r}{k}P(n-m,k)P(m,r-k)$
My question:
Why all the possibilities fall into r+1 types?
And can someone elaborate the answer in an easy way, or numeric example or different story
You can classify the selections according to the number of girls chosen. If we’re choosing $r$ students altogether, there can be any number of girls from $0$ through $r$; that’s one category for each number of girls from $1$ through $r$, plus one extra for no girls at all, for a total of $r+1$ different categories.
Suppose, for instance, that there are $4$ boys, $5$ girls, and we are selecting $3$ students for $3$ different roles. We can choose a group of $3$ students that contains $0$ girls, or $1$ girl, or $2$ girls, or $3$ girls: those are $3+1=4$ different types of group.
Then we count the number of groups of each type. Imagine picking the $3$ students in sequence, so that there is a first student (who gets the first role), a second student (who gets the second role), and a third student (who gets the third role). If for now we look only at the sex of each student, we see that just $\binom30=1$ sequence is possible with with $0$ girls: BBB. There are $\binom31=3$ possible sequences with $1$ girl: BBG, BGB, GBB. There are $\binom32=3$ possible sequences with $2$ girls: BGG, GBG, GGB. And there is $\binom33=1$ possible sequence with $3$ girls: GGG.
When we actually choose specific girls and boys, we have to take into account the individual identities of the students. For instance, there are $4$ boys, so there are $4\cdot3\cdot2=P(4,3)$ ways to choose $3$ of them in a specific order. What about a sequence like BGB? We’re choosing a single girl, which can be done in $5=P(5,1)$ ways, and we’re choosing $2$ boys in a specific order, which can be done in $4\cdot 3=P(4,2)$ ways, so the whole BGB sequence can be chosen in $P(5,1)P(4,2)$ ways. The same goes for the BBG sequence and the GBB sequence, so there are altogether $3P(5,1)P(4,2)$ ways to select a group with $1$ girl.
If we do this for each of the four possible numbers of girls chosen, we find that there are
$$\begin{align*} &\binom30P(5,0)P(4,3)\text{ groups with }0\text{ girls,}\\ &\binom31P(5,1)P(4,2)\text{ groups with }1\text{ girl,}\\ &\binom32P(5,2)P(4,1)\text{ groups with }2\text{ girls, and}\\ &\binom33P(5,3)P(4,0)\text{ groups with }3\text{ girls.} \end{align*}$$
In compact form, each line is
$$\binom3kP(5,k)P(4,3-k)\text{ groups with }k\text{ girls}\;,$$
and the total is therefore
$$\sum_{k=0}^3\binom3kP(5,k)P(4,3-k)\;.$$