Summation of Products of n Numbers taken m at a time with Repetitions/Corollary

From ProofWiki
Jump to navigation Jump to search

Corollary to Summation of Products of n Numbers taken m at a time with Repetitions

Let $a, b \in \Z$ be integers such that $b \ge a$.

Let $U$ be a set of $n = b - a + 1$ numbers $\set {x_a, x_{a + 1}, \ldots, x_b}$.

Let $m \in \Z_{>0}$ be a (strictly) positive integer.


Consider the result Summation of Products of n Numbers taken m at a time with Repetitions:

$\ds \sum_{a \mathop \le j_1 \mathop \le \mathop \cdots \mathop \le j_m \mathop \le b} \paren {\prod_{k \mathop = 1}^m x_{j_k} } = \sum_{\substack {k_1, k_2, \ldots, k_m \mathop \ge 0 \\ k_1 \mathop + 2 k_2 \mathop + \mathop \cdots \mathop + m k_m \mathop = m} } \paren {\prod_{j \mathop = 1}^m \dfrac { {S_j}^{k_j} } {j^{k_j} k_j !} }$

where:

$S_r = \ds \sum_{k \mathop = a}^b {x_k}^r$

for $r \in \Z_{> 0}$


The number of terms in the summation on the right hand side is equal to the number of partitions of the integer $m$.


Proof

Let $m$ be the sum of a number of instances of (strictly) positive integers between $1$ and $m$.

Let the count of instances of $r$ be $k_r$.

Then:

$m = k_1 \times 1 + k_2 \times 2 + \cdots + k_m \times m$

Thus $k_1 + 2 k_2 \times 2 + \cdots + m k_m$ defines a partition of $m$.


By definition of summation, $\ds \sum_{\substack {k_1, k_2, \ldots, k_m \mathop \ge 0 \\ k_1 \mathop + 2 k_2 \mathop + \mathop \cdots \mathop + m k_m \mathop = m} }$ should run over all instances of $k_1, k_2, \ldots, k_m$ that fulfil the conditions.

That is, there is a summand for every partition of $m$.

$\blacksquare$


Examples

Example: $m = 12$

Let $m = 12$.

Then one of the summands on the right hand side is:

$\dfrac {S_1 {S_2}^3 S_5} {240}$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Summation_of_Products_of_n_Numbers_taken_m_at_a_time_with_Repetitions/Corollary&oldid=647890"