# Combinatorics for RMO : some basics and examples: homogeneous products of r dimensions

Question:

Find the number of homogeneous products of r dimensions that can be formed out of the n letters a, b, c ….and their powers.

Solution:

By division, or by the binomial theorem, we have: $\frac{1}{1-ax} = 1 + ax + a^{2}x^{2} + a^{3}x^{3} + \ldots$ $\frac{1}{1-bx} = 1+ bx + b^{2}x^{2} + a^{3}x^{3} + \ldots$ $\frac{1}{1-cx} = 1 + cx + c^{2}x^{2} + c^{3}x^{3} + \ldots$

Hence, by multiplication, $\frac{1}{1-ax} \times \frac{1}{1-bx} \times \frac{1}{1-cx} \times \ldots$ $= (1+ax + a^{2}x^{2}+a^{3}x^{3}+ \ldots)(1+bx + b^{2}x^{2} + b^{3}x^{3}+ \ldots)(1+cx + c^{2}x^{2} + c^{3}x^{3}+ \ldots)\ldots$ $= 1 + x(a + b + c + \ldots) +x^{2}(a^{2}+ab+ac+b^{2}+bc + c^{2} + \ldots) + \ldots$ $= 1 + S_{1}x + S_{2}x^{2} + S_{3}x^{3} + \ldots$ suppose;

where $S_{1}$, $S_{2}$, $S_{3}$, $\ldots$ are the sums of the homogeneous products of one, two, three, … dimensions that can be formed of a, b, c, …and their powers.

To obtain the number of these products, put a, b, c, …each equal to 1; each term in $S_{1}$, $S_{2}$, $S_{3}$, …now becomes 1, and the values of $S_{1}$, $S_{2}$, $S_{3}$, …so obtained give the number of the homogeneous products of one, two, three, ….dimensions.

Also, $\frac{1}{1-ax} \times \frac{1}{1-bx} \times \frac{1}{1-cx} \ldots$

becomes $\frac{1}{(1-x)^{n}}$, or $(1-x)^{-n}$

Hence, $S_{r} =$ the coefficient of $x^{r}$ in the expansion of $(1-x)^{-n}$ $= \frac{n(n+1)(n+2)(n+3)\ldots (n+r-1)}{r!}= \frac{(n+r-1)!}{r!(n-1)!}$

Question:

Find the number of terms in the expansion of any multinomial when the index is a positive integer.

In the expansion of $(a_{1}+ a_{2} + a_{3} + \ldots + a_{r})^{n}$

every term is of n dimensions; therefore, the number of terms is the same as the number of homogeneous products of n dimensions that can be formed out of the r quantities $a_{1}$, $a_{2}$, $a_{3}$, … $a_{r}$, and their powers; and therefore by the preceding question and solution, this is equal to $\frac{(r+n-1)!}{n! (r-1)!}$

A theorem in combinatorics:

From the previous discussion in this blog article, we can deduce a theorem relating to the number of combinations of n things.

Consider n letters a, b, c, d, ….; then, if we were to write down all the homogeneous products of r dimensions, which can be formed of these letters and their powers, every such product would represent one of the combinations, r at a time, of the n letters, when any one of the letters might occur once, twice, thrice, …up to r times.

Therefore, the number of combinations of n things r at a time when repetitions are allowed is equal to the number of homogeneous products of r dimensions which can be formed out of n letters, and therefore equal to $\frac{(n+r-1)!}{r!(n-1)!}$, or ${{n+r-1} \choose r}$.

That is, the number of combinations of n things r at a time when repetitions are allowed is equal to the number of combinations of $n+r-1$ things r at a time when repetitions are NOT allowed.

Example 1:

Find the coefficient of $x^{r}$ in the expansion of $\frac{(1-2x)^{2}}{(1+x)^{3}}$

Solution 1:

The expression $= (1-4x+4x^{2})(1+p_{1}x+p_{2}x^{2}+ \ldots + p_{r}x^{r}+ \ldots)$, suppose.

The coefficients of $x^{r}$ will be obtained by multiplying $p_{r}$, $p_{r-1}$, $p_{r-2}$ by 1, -4, and 4 respectively, and adding the results; hence,

the required coefficient is $p_{r} - 4p_{r-1}+4p_{r-2}$

But, with a little work, we can show that $p_{r} = (-1)^{r}\frac{(r+1)(r+2)}{2}$.

Hence, the required coefficient is $= (-1)^{r}\frac{(r+1)(r+2)}{2} - 4(-1)^{r-1}\frac{r(r+1)}{2} + 4 (-1)^{r-2}\frac{r(r-1)}{2}$ $= \frac{(-1)^{r}}{2}\times ((r+1)(r+2) + 4r(r+1) + 4r(r-1))$ $= \frac{(-1)^{r}}{2}(9r^{2}+3r+2)$

Example 2:

Find the value of the series $2 + \frac{5}{(2!).3} + \frac{5.7}{3^{2}.(3!)} + \frac{5.7.9}{3^{3}.(4!)} + \ldots$

Solution 2:

The expression is equal to $2 + \frac{3.5}{2!}\times \frac{1}{3^{2}} + \frac{3.5.7}{3!}\times \frac{1}{3^{3}} + \frac{3.5.7.9}{4!}\times \frac{1}{3^{4}} + \ldots$ $= 2 + \frac{\frac{3}{2}.\frac{5}{2}}{2!} \times \frac{2^{2}}{3^{2}} + \frac{\frac{3}{2}.\frac{5}{2}.\frac{7}{2}}{3!} \times \frac{2^{3}}{3^{3}} + \frac{\frac{3}{2}.\frac{5}{2}.\frac{7}{2}.\frac{9}{2}}{4!} \times \frac{2^{4}}{3^{4}} + \ldots$ $= 1 + \frac{\frac{3}{2}}{1} \times \frac{2}{3} + \frac{\frac{3}{2}.\frac{5}{2}}{2!} \times (\frac{2}{3})^{2} + \frac{\frac{3}{2}.\frac{5}{2}.\frac{7}{2}}{3!} \times (\frac{2}{3})^{3} + \frac{\frac{3}{2}.\frac{5}{2}.\frac{7}{2}.\frac{9}{2}}{4!} \times (\frac{2}{3})^{4} + \ldots$ $= (1-\frac{2}{3})^{\frac{-3}{2}} = (\frac{1}{3})^{-\frac{3}{2}} = 3^{\frac{3}{2}} = 3 \sqrt{3}$.

Example 3:

If n is any positive integer, show that the integral part of $(3+\sqrt{7})^{n}$ is an odd number.

Solution 3:

Suppose I to denote the integral and f the fractional part of $(3+\sqrt{7})^{n}$.

Then, $I + f = 3^{n} + {n \choose 1}3^{n-1}\sqrt{7} + {n \choose 2}3^{n-2}.7 + {n \choose 3}3^{n-3}.(\sqrt{7})^{3}+ \ldots$…call this relation 1.

Now, $3 - \sqrt{7}$ is positive and less than 1, therefore $(3-\sqrt{7})^{n}$ is a proper fraction; denote it by $f^{'}$;

Hence, $f^{'} = 3^{n} - {n \choose 1}.3^{n-1}.\sqrt{7} + {n \choose 2}.3^{n-2}.7 - {n \choose 3}.3^{n-3}.(\sqrt{7})^{3}+ \ldots$…call this as relation 2.

Add together relations 1 and 2; the irrational terms disappear, and we have $I + f + f^{'} = 2(3^{n} + {n \choose 2}.3^{n-2}.7+ \ldots ) = an even integer$

But, since f and $f^{'}$ are proper fractions their sum must be 1;

Hence, I is an odd integer.