Summation of Products of n Numbers taken m at a time with Repetitions/Corollary/Examples/12
Jump to navigation
Jump to search
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