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.

Answer:

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.

We conclude this article with a few miscellaneous examples:

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.

Hope you had fun,

Nalin Pithwa.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.