Q. 1.20 - A First Course in Probability

Question

Verify that the equality

$\sum _{x_1+....+x_r=n, x_i\ge 0} \frac{n!}{x_1!x_2!....x_r!}=r^n$

when $n = 3, r = 2$, and then show that it always valid. (The sum is over all vectors of $r$ nonnegative integer values whose sum is $n$.)

Hint: How many different n letter sequences can be formed from the first $r$ letters of the alphabet? How many of them use letter $i$ of the alphabet a total of $x_i$ times for each $i = 1, . . . , r$?

Step-by-Step Solution

Answer

It is verified that

$\sum _{x_1+....+x_r=n, x_i\ge 0} \frac{n!}{x_1!x_2!....x_r!}=r^n$

Step 1. Verify the given equality for n   =   3 ,   r   =   2 .

The given equality is $\sum _{x_1+....+x_r=n, x_i\ge 0} \frac{n!}{x_1!x_2!....x_r!}=r^n$

and $n=3 \text{and} r=2$

$x_1+x_2=n$, so the values of $x_1 \text{and} x_2$ are

$\left(x_1=0, x_2=3\right), \left(x_1=1, x_2=2\right), \left(x_1=2, x_2=1\right), \left(x_1=3, x_2=0\right)$

Substituting the values in the equality $\sum _{x_1+....+x_r=n, x_i\ge 0} \frac{n!}{x_1!x_2!....x_r!}=r^n$ we get.

$$\begin{gathered} \frac{3!}{0!3!}+\frac{3!}{1!2!}+\frac{3!}{2!1!}+\frac{3!}{3!0!}=2^3 \\ 1+3+3+!=8 \\ 8=8 \end{gathered}$$

Hence, it is proved that $\sum _{x_1+....+x_r=n, x_i\ge 0} \frac{n!}{x_1!x_2!....x_r!}=r^n$.

Step 2. Verify the given equality for n = 3 ,   and   r = 3

The given equality is $\sum _{x_1+....+x_r=n, x_i\ge 0} \frac{n!}{x_1!x_2!....x_r!}=r^n$

$n=3, r=3$

Consider, $x_1+x_2+x_3=n$, so the values are

$$\begin{gathered} \left(x_1=0, x_2=1, x_3=2\right), \left(x_1=1, x_2=2, x_3=0\right), \left(x_1=2, x_2=1, x_3=0\right), \left(x_1=3, x_2=0, x_3=0\right), \\ \left(x_1=0, x_2=2, x_3=1\right), \left(x_1=0, x_2=3, x_3=0\right), \left(x_1=0, x_2=1, x_3=2\right), \left(x_1=0, x_2=0, x_3=3\right), \\ \left(x_1=1, x_2=0, x_3=2\right), \left(x_1=2, x_2=0, x_3=1\right) \end{gathered}$$

Substituting the values in the equality $\sum _{x_1+....+x_r=n, x_i\ge 0} \frac{n!}{x_1!x_2!....x_r!}=r^n$, we get

$$\begin{gathered} \frac{3!}{0!1!2!}+\frac{3!}{1!2!0!}+\frac{3!}{2!1!0!}+\frac{3!}{3!0!0!}+\frac{3!}{0!2!1!}+\frac{3!}{0!3!0!}+\frac{3!}{0!1!2!}+\frac{3!}{0!0!3!}+\frac{3!}{1!0!2!}+\frac{3!}{2!0!1!}=3^3 \\ 27=27 \end{gathered}$$

Step 3. Verify the given equality for n = 5 ,   r = 2

The given equality is $\sum _{x_1+....+x_r=n, x_i\ge 0} \frac{n!}{x_1!x_2!....x_r!}=r^n$ and

$n=5, r=2$

Consider $x_1+x_2=n$, so the values are

$\left(x_1=0, x_2=5\right), \left(x_1=1, x_2=4\right), \left(x_1=2, x_2=3\right), \left(x_1=3, x_2=2\right), \left(x_1=4, x_2=1\right), \left(x_1=5, x_2=0\right)$

$$\begin{gathered} \frac{5!}{0!5!}+\frac{5!}{1!4!}+\frac{5!}{2!3!}+\frac{5!}{3!2!}+\frac{5!}{4!1!}+\frac{5!}{5!0!}=2^5 \\ 32=32 \end{gathered}$$

Therefore, it is proved that $\sum _{x_1+....+x_r=n, x_i\ge 0} \frac{n!}{x_1!x_2!....x_r!}=r^n$.