Multinomial theorem

Suppose you have an expression of the form (a + b + c + d + e + f)^2 squared , and you need to expand the square in order to solve some larger equation. How do you actually do that? More generally, is there an approach we can use to expand any group of added-together terms with any exponent?

Yes. It's called the multinomial theorem.

Let's get started

The multinomial theorem can be used to expand any expression of the form (x₁ + x₂ + ... + x_m)^n to the nth power . Let's take a look at the equation:

Oh. Uh...

Well, to start with, those values below the summation symbol (Σ) represent conditions. We have m variables named k_something, named k₁ through k_m, and we have two conditions that apply to the lot of them. We are going to take every possible combination of values that meets these conditions, feed those values into the summation "body," and then compute the results and sum them all.

The summation "body," meanwhile, has us multiply a collection of values — that's the capital-pi (Π) symbol; it's the multiplication version of Σ — and then multiply that by something else. The result is then added as part of the summation loop.

The first condition on our summation loop is that the values must all add up to n, and the second condition is that they must all be greater than or equal to zero. This in turn implies that no one single value can be greater than n, as otherwise we'd need at least one of the others to be negative in order for this to work.

See the large parentheses, with the two rows and no symbol dividing them? Hear that one bit with the word "choose?" That's the notation for binomial coefficients. If we call the top number n and the bottom number k, then given the expression (1 + x)^k to the kth power , we can compute the coefficient of x^k to the kth power  as follows:

Wikipedia offers one example: (1 + x)^4 to the 4th power  is:

Apparently, that generalizes to larger "multinomials;" if your multinomial has r terms in it, then you'd do:

Given a multinomial with r terms, the variable k_i is defined below — and as a reminder, this is summation, not a single variable:

This is all getting pretty out-there, so let's come back to Earth by actually using this.

An example

We'll go with the example I led in with: (a + b + c + d + e + f)^2 squared . We have a multinomial that we want to square, so n is 2. Our multinomial has six terms, so m is 6.

This equation is a nested loop. The outermost loop has six iterator variables, and the innermost loop just goes over those. It's a bit like this:

int[...][6] all_possible_k_arrays = ...;

int[6] k;

// summation (big weird "E" symbol):
sum = 0;
for each k[1], k[2], k[3], k[4], k[5], k[6] matching conditions, do:

   // capital-pi thing:
   product = 1;
   for t = 1 to k.length do
      product *= ...;
   end
   
   // multiply by factorial fraction:
   product *= ...;
   
   sum += product;
end

We need to start at the innermost loop and work our way outward to understand this, but the innermost loop uses the six "loop index" variables, k_i, that belong to our outer loop. That means that we need to figure out what those variables are.

Computing our outer loop variables

Let's compute the values of all possible combinations of k_i for our 6-term monomial. We know that there must be six of these values, they must sum to 2, and none of them can be negative.

Here's a list of every possible combination of numbers (between zero and 2, inclusive) that can add up to 2:

• 2
• 1 + 1

Of course, we need to distribute those possibilities across sets of six total numbers, where any extra numbers just get set to zero. This means we'll have a lot of repeats — the same numbers being added together, but with the numbers in different slots among the six we have available. Here's what that looks like:

Dealing with the inner loop

That's a lot of combinations up there, but let's actually use them and see how that shakes out. The k_i variables are used in two ways:

• For each k_i in any valid set of values, we compute x_i^k_i to the k_ith power . We then multply all of these together; this is the inner loop, called a sequence of products and indicated with the capital pi (Π).
• After the inner loop is done, we compute the multinomial coefficient (the fraction with the factorials in it), and multiply that with the sequence of products.

So let's start by substituting in our x_i^k_i to the k_ith power  values. We'll keep things simple: instead of using the actual terms from our multinomial (for x_i), we'll represent the whole multinomial as a + b + c + d + e + f.

Now, if you take any value to the zeroth power, then you get 1, so we can strike a lot of terms from that table and just replace them with ones. Similarly, a term to the first power is just itself, so we can strip the exponent.

Now let's add the multinomial coefficients to the table:

Putting it all together

Remember that each row represents a valid set of possible values for the k₁ through k₆ variables. Each row represents the values we'll use in this part of the formula:

If we multiply all the items in a row together, then we'll get the result of that expression for that given set of k_i values. Let's see what that looks like. We can skip every cell in the table that's just the number 1, so in practice, 90% of that table is gone:

So those are all the possible values of that one expression. Where were we using it again?

Right! We were going to add those final items together. Let's see what that looks like:

Conclusion

This overall process can be followed for a multinomial of any size m, being raised to any exponent n. You want to create a table like the ones above, listing out every combination of m many numbers (each between 0 and n) that add up to n. You can then mimic the process above, and get your result.