Multinomial Expansion

Medium

Combinatorics Counting

Problem

How many terms are there in the expansion of

(x_{1} + x_{2} + x_{3} + x_{4} + x_{5} + x_{6})^{18}

after all like terms have been combined?

Original Problem Link: Click here

Solution

Step 1: Understanding the Expansion

When expanding

(x_{1} + x_{2} + x_{3} + x_{4} + x_{5} + x_{6})^{18}

each term in the expansion will be of the form:

c \cdot x_{1}^{a_{1}} x_{2}^{a_{2}} x_{3}^{a_{3}} x_{4}^{a_{4}} x_{5}^{a_{5}} x_{6}^{a_{6}}

where $a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6}$ are non-negative integers that sum to 18:

a_{1} + a_{2} + a_{3} + a_{4} + a_{5} + a_{6} = 18.

Each unique term corresponds to a different way of assigning exponents to the six variables, regardless of order.

Step 2: Reduced Version - The Core Idea

Instead of thinking in terms of exponents, simply answer:

"In how many ways can I divide 18 objects amongst 6 people, if each person can get 0 at min?"

This is a direct application of the Stars and Bars method, which states that the number of ways to distribute $n$ identical objects among $k$ groups is:

(k - 1 n + k - 1) .

Setting $n = 18$ (total power) and $k = 6$ (number of variables), we get:

(6 - 1 18 + 6 - 1) = (5 23) .

Step 3: Compute the Binomial Coefficient

Using the formula:

(5 23) = \frac{23 !}{5 ! ( 23 - 5 )!} = \frac{23 !}{5 ! \cdot 18 !} .

Computing step-by-step:

\frac{23 \times 22 \times 21 \times 20 \times 19}{5 \times 4 \times 3 \times 2 \times 1}

= \frac{5173168}{120} = 33649.