Binomial and multinomial coefficients

In what may seem an odd turnaround, we’ll start this week with some combinatorics. We have previously seen the binomial formula:

(a + b)^{k} = ∑_{i=0}^{k} \binom{k}{i}a^{i}b^{k−i}, \binom{k}{i} = \frac{k!}{i!(k − i)!}.

Whenever you see a factorial, it generally means you’re counting possibilities. In this case, the coefficient of the ith term in the expansion above is counting the number of ways that you could choose i factors of a and k − i factors of b to make a monomial of degree k. The thing about counting is that you can usually only count things that are in order.

Given n objects, there are n! = n(n−1)(n−2) ⋯ 2·1 ways to order them. The first thing we need to order is the factors of (a + b)^{k}:

(a + b)_{1}(a + b)_{2} ⋯ (a + b)_{n−1}(a + b)_{k}.

By changing the indices, we have changed the order of the factors, although the factors are themselves indistiguishable. We will give them a trait that distinguishes (some of) them: from the first i that appear, we choose the a factor to multiply out, and from the last k − i, we choose the b factor. This gives a term that will definitely appear in the expansion of (a + b)^{k}. But if we change the order of the first i terms and the order of the last k − i terms, without mixing them, we will get a “new” term, which in truth we have already counted because we chose the same term, a or b, from the same factors. So these changes in ordering reduce the number of terms. Thus we divide by the number of such orderings to get that there are k!/i!(k−i)! terms with a appearing i times and b appearing k−i times.

We’re now working with polynomials of more than two variables. We need a more general formula, called the multinomial formula:

(a_{1} + a_{2} + ⋯ + a_{n})^{k} = ∑_{b_{1}+···+b_{n}=k} \binom{k}{b_{1}, …, b_{n}} a_{1}^{b_{1}} ⋯ a_{n}^{b_{n}}, \binom{k}{b_{1}, …, b_{n}} = \frac{k!}{b_{1}! ⋯ b_{n}!}.

This formula makes an appearance in the proof of Taylor’s Theorem that I’ve posted online. One of your homework exercises asks you a related question: “What is the number of multi-indices of total degree k, with n entries?” (Hint: it’s not any number that appears in the above formula.) At this point, parts of this expression should look familiar. Specifically, if we collect all the b_{i}s into a single object β = (b_{1}, …, b_{n}), then the denominatorof the multinomial coefficient becomes β!, and the monomial part becomes a^{β}, where a is the vector with entries a_{i}. All we’re missing is a few derivatives for this to look exactly like the Taylor polynomial of a function f.

Taylor polynomials

Let’s go back to the expression for the kth-order Taylor polynomial of a function f, expanded around a (we’ll not worry here about the error term):

f(a + h) ≈ ∑_{|I|≤k} \frac{D^{I}f(a)}{I!}h^{I}.

If f : ℝ^{n} → ℝ is a polynomial of degree ≤ k, and we expand around 0, then this should of course just equal f. Can we see why that’s true? If D^{I} is applied to a term where some entry in I surpasses the degree of the corresponding variable in ℝ^{n}, then D^{I} kills that term. Conversely, if some entry of I is less than the degree of the corresponding variable, then that variable will still appear in the differentiated form, and evaluating at 0 will eliminate it. So the only time a term of f contributes to the sum is when I matches exactly the exponents of the term. For example,

D^{(2,0,1)}xyz|_{[ \begin{matrix}x \\ y \\ z \end{matrix} ]=[ \begin{matrix}0 \\ 0 \\ 0 \end{matrix} ]} = 0|_{[ \begin{matrix}x \\ y \\ z \end{matrix} ]=[ \begin{matrix}0 \\ 0 \\ 0 \end{matrix} ]} = 0  (too hot)
D^{(2,0,1)}x^{2}yz|_{[ \begin{matrix}x \\ y \\ z \end{matrix} ]=[ \begin{matrix}0 \\ 0 \\ 0 \end{matrix} ]} = 2y|_{[ \begin{matrix}x \\ y \\ z \end{matrix} ]=[ \begin{matrix}0 \\ 0 \\ 0 \end{matrix} ]} = 0  (too cold)
D^{(2,0,1)}x^{2}z|_{[ \begin{matrix}x \\ y \\ z \end{matrix} ]=[ \begin{matrix}0 \\ 0 \\ 0 \end{matrix} ]} = 2|_{[ \begin{matrix}x \\ y \\ z \end{matrix} ]=[ \begin{matrix}0 \\ 0 \\ 0 \end{matrix} ]} = 2  (just right)

Each time we differentiate with respect to a variable, we pick up a factor equal to the old exponent of the variable; this means D^{I} of the term will be I! times the term’s original coefficient. Hence we must divide out by I!.

Likewise, if we have a power series for a function, then the kth Taylor polynomial for the function should just be the first k terms of the series. For example, the kth order Taylor polynomial of x ↦ (1 − x)^{−1} centered at 0 is 1 + x + ⋯ + x^{k}, because

\frac{1}{1 − x} = 1 + x + x^{2} + x^{3} + ⋯ = ∑_{i=0}^{∞} x^{i} for |x| < 1.

This last observation, along with the following (loosely stated) proposition, make computing Taylor series for certain functions quite easy.

Proposition. The power series of a composition equals the composition of the power series. (Chain rule is in effect; see second example for explanation.)

Example 1. The function (\begin{matrix}x \\ y \\ z \end{matrix}) ↦ e^{x+xy^{2}+z^{2}} is the composition of a function g : ℝ^{3} → ℝ

and exp : ℝ → ℝ, each of which is expressible by a power series. Recall that

e^{x} = 1 + x + \frac{x^{2}}{2} + \frac{x^{3}}{6} + ⋯ + \frac{x^{k}}{k!} + · · · .

Suppose we want to compute the degree 3 Taylor polynomial of the composition. At most, we’ll have to consider the terms up to degree 3 in each of the power series, because composing will only increase the exponents. g is its own degree 3 Taylor polynomial, and P_{exp}^{3}(x) = 1 + x + x^{2}/2 + x^{3}/6. So we compose these polynomials and take just the terms of degree 3 or lower:

P_{exp ∘g}^{3} (\begin{matrix}x \\ y \\ z \end{matrix}) = cubic [1 + (x + xy^{2} + z^{2}) + \frac{(x + xy^{2} + z^{2})^{2}}{2} + \frac{(x + xy^{2} + z^{2})^{3}}{6} ]

= 1 + x + xy^{2} + z^{2} + \frac{1}{2}(x^{2} + 2xz^{2}) + \frac{1}{6}x^{3}.

Example 2. The binomial formula and the series for (1 − x)^{−1} are special cases of a more general formula:

(1 + x)^{p} ≈ 1 + px + \frac{p(p − 1)}{2!}x^{2} + \frac{p(p − 1)(p − 2)}{3!}x^{3} + ⋯ + \frac{p(p − 1) ⋯ (p − (k − 1))}{k!}x^{k},

where p is not necessarily an integer. Let’s use this to compute the degree 4 Taylor polynomial of x ↦ \sqrt{cos x} at 0. At a certain point we must be careful, because we have the Taylor polynomials for cosine and (1 + x)^{1/2} computed at 0. Once we’ve run x through the cosine, however, we’re no longer at 0, and we have to think about what terms we should use in the composition.

P_{√\overline{cos}}^{4}(x) = quartic [\sqrt{1 − \frac{x^{2}}{2!} + \frac{x^{4}}{4!}} ]

= quartic [1 + \frac{1}{2} (−\frac{x^{2}}{2!} + \frac{x^{4}}{4!} ) + \frac{1}{2!} (\frac{1}{2}) (−\frac{1}{2}) (−\frac{x^{2}}{2!} + \frac{x^{4}}{4!} )^{2}]

= 1 − \frac{x^{2}}{4} + \frac{x^{4}}{48} − \frac{1}{8} (\frac{x^{4}}{4} ) = 1 − \frac{x^{2}}{4} − \frac{x^{4}}{96}.

Covariant tensors

Let’s return to a discussion of the information that the Taylor polynomial holds. The terms of degree 1 add up to

∑_{|I|=1} D^{I}f(a) · h^{I} = (D_{1}f(a))h_{1} + (D_{2}f(a))h_{2} + ⋯ + (D_{n}f(a))h_{n} = [Df(a)]h.

Recall from long ago, when derivatives were being introduced, that this is exactly the directional derivative in the direction of h, i.e.,

D_{h}f(a) = [Df(a)]h.

Thus the degree 1 Taylor polynomial of f at a can be written

P_{f}^{1}(h) = f(a) + D_{h}f(a).

The directional derivative is a covariant tensor of rank 1.

Now suppose we’ve chosen k vectors h_{1}, …, h_{k} in ℝ^{n}. Then we can compute

[D^{k}f(a)](h_{1}, …, h_{k}) := D_{h_{1}}(D_{h_{2}}(⋯ (D_{h_{k}}f) ⋯))(a).

As you saw in yesterday’s lecture, this function (ℝ^{n})^{k} → ℝ is linear in each of its components. Moreover, because f is C^{k}, its mixed partial derivatives of order ≤ k commute, which implies that D^{k}f(a) is a symmetric multilinear form; switching the order of the h_{i} doesn’t change the resulting value. This function is a covariant tensor of rank k. Essentially, it has k “slots” for vectors in ℝ^{n}, and requires each of these slots to be filled before it evaluates to a real number. If we set h_{1} = ⋯ = h_{k} = h, then we obtain a homogeneous polynomial of degree k from ℝ^{n} to ℝ, defined by

h ↦ [D^{k}f(a)]h^{⊗k}, where h^{⊗k} := (h, …, h) ∈ (ℝ^{n})^{k}.

The k-linear function [D^{k}f(a)] captures all of the information about the kth-order partial derivatives of f at a, as a higher-order generalization of the way the Jacobian captures the first partials and the Hessian captures the second partials. Because of this, we can rewrite the Taylor polynomial of f in terms of these multilinear forms:

f(a + h) ≈ ∑_{i=0}^{k} \frac{1}{i!}[D^{i}f(a)]h^{⊗i}.

The presence of the 1/i! coefficient shouldn’t be surprising: D^{i}f(a) is a rank i tensor, and we’re plugging in i copies of h. “Shuffling the order” of these i identical copies has no effect, so we should take the i! possible orders into account. Let’s see if we can understand this more precisely.

Simply put, this is the reappearance of the multinomial formula in the guise of differential operators. Recall that partial derivatives are precisely directional derivatives, taken in the direction of a standard basis vector; i.e.,D_{j}f(a) = D_{e_{j}}f(a). Now we use the fact that h is a linear combination of the e_{j}, and that covariant tensors are linear in each of their slots. For example,

[D^{2}f(a)] (\begin{matrix}1 \\ 1 \\ 1 \end{matrix})^{⊗2}=D_{e_{1}+e_{2}+e_{3}}(D_{e_{1}+e_{2}+e_{3}}f)(a)
=D_{e_{1}+e_{2}+e_{3}}(D_{1}f + D_{2}f + D_{3}f)(a)
=D_{1}(D_{1}f + D_{2}f + D_{3}f)(a) + D_{2}(D_{1}f + D_{2}f + D_{3}f)(a)
+ D_{3}(D_{1}f + D_{2}f + D_{3}f)(a)
=D_{1}D_{1}f(a) + D_{1}D_{2}f(a) + D_{1}D_{2}f(a) + D_{2}D_{1}f(a) + D_{2}D_{2}f(a) + D_{2}D_{2}f(a)
+ D_{3}D_{1}f(a) + D_{3}D_{2}f(a) + D_{3}D_{2}f(a),

which is the sum of all of the second-order partial derivatives for a function of three variables. If we have different coordinates, as in h = h_{1}e_{1} + h_{2}e_{2} + h_{3}e_{3}, then the h_{j} in each term simply come out as the appropriate monomial (e.g., D_{h_{1}e_{1}}D_{h_{1}e_{1}}D_{h_{2}e_{2}}f(a) = h_{1}^{2}h_{2}D_{1}D_{1}D_{2}f(a)). But, thanks to equality of mixed partials, some of these terms are duplicated. The multinomial formula accounts for all of this.

Thus the more general question is: how many times does each ith-order partial derivative appear in D^{i}f(a)? Suppose we’re looking for the partial derivative D^{(b_{1},...,b_{n})}, where b_{1}+⋯+b_{n} = i. We evaluate this rank i tensor on i copies of h, which now plays the rôle of the multinomial in the multinomial formula. The coefficient D^{(b_{1},...,b_{n})}f(a) appears whenever we choose to look at the jth element of h b_{j} times. As in the multinomial formula, we thus have that

[D^{(b_{1},...,b_{n})}f(a)]h_{1}^{b_{1}} ⋯ h_{n}^{b_{n}} appears \binom{i}{b_{1}, …, b_{n}} = \frac{i!}{b_{1}! ⋯ b_{n}!} times in [D^{i}f(a)]h^{⊗i}.

This is the right extra factor in the Taylor polynomial as we saw it before, except for the i! in the numerator. Once we divide out that extra factor, we’re back to our original expression for Taylor polynomials.