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

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

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 \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 + \cdots \mathop + m k_m \mathop = m} } \paren {\prod_{j \mathop = 1}^m \dfrac { {S_j}^{k_j} } {j^{k_j} k_j !} }$

where:

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

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

Let $m = 12$.

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

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

Proof

$12$ can thus be expressed as

$12 = 5 + 2 + 2 + 2 + 1$

We have that $k_j$ is the number of instances of $j$ in the partition.

Thus setting $k_1 = 1, k_2 = 3, k_5 = 5$:

\(\ds k_1 + 2 k_2 + k_5\)

\(=\)

\(\ds 1 + 2 \times 3 + 5 \times 1\)

\(\ds \)

\(=\)

\(\ds 12\)

Hence the summand:

\(\ds \dfrac { {S_1}^1} {1^1 1!} \dfrac { {S_2}^3} {2^3 3!} \dfrac { {S_5}^1} {5^1 1!}\)

\(=\)

\(\ds \dfrac {S_1 {S_2}^3 S_5} {240}\)

$\blacksquare$

Sources

• 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.9$: Generating Functions