Question

Let \(r_{1}, r_{2}, \ldots, r_{n}\) be nonnegative integers such that $$r_{1}+r_{2}+\cdots+r_{n}=r \geq 0$$ (a) Show that $$\left(z_{1}+z_{2}+\cdots+z_{n}\right)^{r}=\sum_{r} \frac{r !}{r_{1} ! r_{2} ! \cdots r_{n} !} z_{1}^{r_{1}} z_{2}^{r_{2}} \cdots z_{n}^{r_{n}}$$ where \(\sum_{r}\) denotes summation over all \(n\) -tuples \(\left(r_{1}, r_{2}, \ldots, r_{n}\right)\) that satisfy the stated conditions. HINT: This is obvious if \(n=1,\) and it follows from Exercise 1.2 .19 if \(n=2 .\) Use induction on \(n\). (b) Show that there are $$\frac{r !}{r_{1} ! r_{2} ! \cdots r_{n} !}$$ ordered \(n\) -tuples of integers \(\left(i_{1}, i_{2}, \ldots, i_{n}\right)\) that contain \(r_{1}\) ones, \(r_{2}\) twos, ... and \(r_{n} n\) 's. (c) Let \(f\) be a function of \(\left(x_{1}, x_{2}, \ldots, x_{n}\right)\). Show that there are $$\frac{r !}{r_{1} ! r_{2} ! \cdots r_{n} !}$$ partial derivatives \(f_{x_{i} 1} x_{i_{2}} \cdots x_{i_{r}}\) that involve differentiation \(r_{i}\) times with respect to \(x_{i},\) for \(i=1,2, \ldots, n\).

Short answer

In summary, the given equality is proven using induction on \(n\), and we have established a combinatorial counting method to find the number of ordered \(n\)-tuples with certain properties. This logic was then applied to count the number of partial derivatives of a given function with respect to each variable in a certain order.

Step-by-step solution

When n = 1, we have \(\left(z_1\right)^r = z_1^{r}\), since there is only one possible nonnegative integer value for \(r\) and summation has only one term. It's obvious that the given equality holds for this case. For the n = 2 case, the given equality follows from the binomial theorem (Exercise 1.2.19): \(\left(z_1 + z_2\right)^r = \sum\limits_{r_1=0}^{r} \binom{r}{r_1} z_1^{r_1} z_2^{r-r_1}\) #Step 2: Induction Step#

Suppose the equality holds for \(n=k\): \(\left(z_{1}+\cdots+z_{k}\right)^r=\sum_{r} \frac{r !}{r_{1} ! \cdots r_{k} !} z_{1}^{r_{1}} \cdots z_{k}^{r_{k}}\) We want to prove it for \(n=k+1.\) Consider: \(\left(z_1 + \cdots + z_k + z_{k+1}\right)^r = \left(\left(z_1 + \cdots + z_k\right) + z_{k+1}\right)^r\) By applying the binomial theorem, we get: \(\sum\limits_{r_{k+1}=0}^r \binom{r}{r_{k+1}} \left(z_1 + \cdots + z_k\right)^{r-r_{k+1}} z_{k+1}^{r_{k+1}}\) Now let's substitute the induction hypothesis: \(\sum\limits_{r_{k+1}=0}^r \binom{r}{r_{k+1}} \sum_{r} \frac{r !}{r_{1} ! \cdots r_{k} !} z_{1}^{r_{1}} \cdots z_{k}^{r_{k}} z_{k+1}^{r_{k+1}}\) This gives us the required equality for \(n=k+1\): \(\sum_{r} \frac{r !}{r_{1} ! r_{2} ! \cdots r_{k+1} !} z_{1}^{r_{1}} z_{2}^{r_{2}} \cdots z_{k+1}^{r_{k+1}}\) So, by induction, the given equality holds for all \(n.\) (b) #Step 1: Count ordered n-tuples#

In this step, we are given r excess elements to distribute among n groups (with each group corresponding to an integer from 1 to n). We want to put \(r_1\) in group 1, \(r_2\) in group 2, and so forth. This is equivalent to distributing the r excess elements among n groups, which is a classical combinatorial counting problem. We can use the multinomial coefficient for this counting: \(\frac{r !}{r_{1} ! r_{2} ! \cdots r_{n} !}\) This gives us the total number of ordered \(n\)-tuples with the desired properties. (c) #Step 1: Count partial derivatives#

In this step, we need to count the number of partial derivatives that involve differentiating \(r_i\) times with respect to each variable \(x_i\). This is equivalent to counting distinct ordered \(n\)-tuples as in part (b), where \(r_i\) is the number of times we differentiate with respect to \(x_i\). Using the result from part (b), we have: \(\frac{r !}{r_{1} ! r_{2} ! \cdots r_{n} !}\) different partial derivatives.

Key concepts

Combinatorics

Combinatorics is the branch of mathematics concerned with counting, arranging, and grouping items. One of its key applications is in calculating the number of ways to arrange groups or items under certain conditions. A fundamental concept within combinatorics is the use of factorials, denoted as \(!\), which represent the product of all positive integers up to a specified number. For example, the factorial of a number \(r\) is defined as \(r! = r \times (r-1) \times \cdots \times 1\). In the exercise above, we use multinomial coefficients \(\frac{r!}{r_1! r_2! \cdots r_n!}\) to find the number of ways to distribute a total of \(r\) items into \(n\) groups, where each group has a specified count of items \(r_1, r_2, \ldots, r_n\).
This situation arises, for example, when determining the number of ordered \(n\)-tuples that can be formed which include specific numbers of ones, twos, etc., in a sequence. The multinomial theorem, which generalizes the binomial theorem, provides a structured way to compute such distributions, making it a powerful tool in combinatorics for problems involving multiple items and conditions.

Partial Derivatives

Partial derivatives are a fundamental concept in calculus, focusing on functions with multiple variables. When we discuss the derivative of a function, we often refer to its rate of change with respect to one variable while keeping others constant. For a function \(f(x_1, x_2, \ldots, x_n)\), the partial derivative with respect to \(x_i\) is denoted \(\frac{\partial f}{\partial x_i}\), and it measures how \(f\) changes as \(x_i\) is varied alone. This is crucial in understanding the behavior of multivariable functions.
In the context of the given exercise, the number of different partial derivatives involving differentiation \(r_i\) times with respect to each variable \(x_i\) can be calculated using multinomial coefficients \(\frac{r!}{r_1! r_2! \cdots r_n!}\). For instance, if a function needs to be differentiated a specified number of times with respect to several variables, multinomial expressions help determine the total number of distinct partial derivatives possible. This approach extends the core ideas of combinatorial counting to the realm of calculus and multivariable functions.

Induction

Induction is a powerful method of mathematical proof, often used to establish the validity of a statement for all natural numbers. It involves two critical steps:

• Base Case: Verifying the statement for an initial value, usually the smallest number like \(n = 1\).
• Inductive Step: Assuming the statement is true for \(n = k\), then proving it holds for \(n = k+1\).

The exercise employs induction to generalize a result from a simple case (like \(n=1\) or \(n=2\)) to any number \(n\).
By following the inductive technique, one shows that if a mathematical expression holds for smaller instances, it correctly extends to larger, more complex cases. In proving the multinomial theorem's formula, induction helps verify the theorem’s truth robustly from simple cases to arbitrary \(n\), demonstrating its soundness and applicability across various scenarios. This incremental approach, building from specific examples to a general rule, makes induction a cornerstone technique in proving general mathematical results.