Argue thatnn1, n2, ........ , nr=n-1n1-1, n2, ........ , nr+n-1n1, n2-1, ........ , nr+......+n-1n1, n2, ........ , nr-1Hint: Use an argument similar to the one used to establish Equation (4.1).

It is proved thatnn1, n2, ........ , nr=n-1n1-1, n2, ........ , nr+n-1n1, n2-1, ........ , nr+......+n-1n1, n2, ........ , nr-1

Q. 1.18 - A First Course in Probability

Q. 1.18

Question

Argue that

$(\begin{matrix} n \\ n_{1}, n_{2}, . . . . . . . ., n_{r} \end{matrix}) = (\begin{matrix} n - 1 \\ n_{1} - 1, n_{2}, . . . . . . . ., n_{r} \end{matrix}) + (\begin{matrix} n - 1 \\ n_{1}, n_{2} - 1, . . . . . . . ., n_{r} \end{matrix}) + . . . . . . + (\begin{matrix} n - 1 \\ n_{1}, n_{2}, . . . . . . . ., n_{r} - 1 \end{matrix})$

Hint: Use an argument similar to the one used to establish Equation (4.1).

Step-by-Step Solution

Verified

Answer

It is proved that

1Step 1. Given information.

We have to prove that $(\begin{matrix} n \\ n_{1}, n_{2}, . . . . . . . ., n_{r} \end{matrix}) = (\begin{matrix} n - 1 \\ n_{1} - 1, n_{2}, . . . . . . . ., n_{r} \end{matrix}) + (\begin{matrix} n - 1 \\ n_{1}, n_{2} - 1, . . . . . . . ., n_{r} \end{matrix}) + . . . . . . + (\begin{matrix} n - 1 \\ n_{1}, n_{2}, . . . . . . . ., n_{r} - 1 \end{matrix})$

2Step 2. Prove that n n 1 ,   n 2 ,   . . . . . . . .   ,   n r = n - 1 n 1 - 1 ,   n 2 ,   . . . . . . . .   ,   n r + n - 1 n 1 ,   n 2 - 1 ,   . . . . . . . .   ,   n r + . . . . . . + n - 1 n 1 ,   n 2 ,   . . . . . . . .   ,   n r - 1

$(\begin{matrix} n \\ n_{1}, n_{2}, . . . . . . . ., n_{r} \end{matrix})$ represents the no. of possible divisions of $n$ distinct objects into $r$ distinct groups of respective sizes $n_{1}, n_{2}, . . . . . . . . ., n_{r}$ .

Now, let's concentrate on one object, suppose it is grouped in $n_{1}$ group, it can be done in $(\begin{matrix} n - 1 \\ n_{1} - 1, n_{2}, . . . . . . . ., n_{r} \end{matrix})$ ways.

If it is not grouped in $n_{1}$ group but it is grouped in $n_{2}$ group, it can be done in $(\begin{matrix} n - 1 \\ n_{1}, n_{2} - 1, . . . . . . . ., n_{r} \end{matrix})$ ways.

Similarly, if it is grouped in $n_{r}$ group, it can be done in $(\begin{matrix} n - 1 \\ n_{1}, n_{2}, . . . . . . . ., n_{r} - 1 \end{matrix})$ ways.

Hence, it is proved that $(\begin{matrix} n \\ n_{1}, n_{2}, . . . . . . . ., n_{r} \end{matrix}) = (\begin{matrix} n - 1 \\ n_{1} - 1, n_{2}, . . . . . . . ., n_{r} \end{matrix}) + (\begin{matrix} n - 1 \\ n_{1}, n_{2} - 1, . . . . . . . ., n_{r} \end{matrix}) + . . . . . . + (\begin{matrix} n - 1 \\ n_{1}, n_{2}, . . . . . . . ., n_{r} - 1 \end{matrix})$

Q. 1.17

Q. 1.19

Other exercises in this chapter

Q. 1.16

Consider a tournament of n contestants in which the outcome is an ordering of these contestants, with ties allowed. That is, the outcome partitions the pla

View solution

Q. 1.17

Present a combinatorial explanation of whynr=nr, n-r

View solution

Q. 1.19

Prove the multinomial theorem.

View solution

Q. 1.20

In how many ways can n identical balls be distributed into r urns so that the ith urn contains at least mi balls, for each i = 1,&

View solution