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

From ProofWiki
Jump to navigation Jump to search

Theorem

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.


Let:

\(\ds h_m\) \(=\) \(\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} }\)
\(\ds \) \(=\) \(\ds \sum_{a \mathop \le j_1 \mathop \le \mathop \cdots \mathop \le j_m \mathop \le b} x_{j_1} \cdots x_{j_m}\)


That is, $h_m$ is the product of all $m$-tuples of elements of $U$ taken $m$ at a time, allowing for repetition.


For $r \in \Z_{> 0}$, let:

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


Then:

\(\ds h_m\) \(=\) \(\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} } \paren {\prod_{j \mathop = 1}^m \dfrac { {S_j}^{k_j} } {j^{k_j} k_j !} }\)
\(\ds \) \(=\) \(\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} } \dfrac { {S_1}^{k_1} } {1^{k_1} k_1 !} \dfrac { {S_2}^{k_2} } {2^{k_2} k_2 !} \cdots \dfrac { {S_m}^{k_m} } {m^{k_m} k_m !}\)


Recurrence Formula

A recurrence relation for $h_n$ can be given as:

\(\ds h_n\) \(=\) \(\ds \sum_{k \mathop = 1}^n \dfrac {S_k h_{n - k} } n\)
\(\ds \) \(=\) \(\ds \dfrac 1 n \paren {S_1 h_{n - 1} + S_2 h_{n - 2} + \cdots S_n h_0}\)

for $n \ge 1$.


Inverse Formula

Let $S_m$ be expressed in the form:

$S_m = \ds \sum_{k_1 \mathop + 2 k_2 \mathop + \mathop \cdots \mathop + m k_m \mathop = m} A_m {h_1}^{k_1} {h_2}^{k_2} \cdots {h_m}^{k_m}$

for $k_1, k_2, \ldots, k_m \ge 0$.


Then :

$A_m = \paren {-1}^{k_1 + k_2 + \cdots + k_m - 1} \dfrac {m \paren {k_1 + k_2 + \cdots + k_m - 1}! } {k_1! \, k_2! \, \cdots k_m!}$


Corollary

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

Lemma 1

Let $\map G z$ be the generating function for the sequence $\sequence {h_m}$.

Then:

\(\ds \map G z\) \(=\) \(\ds \prod_{k \mathop = a}^b \dfrac 1 {1 - x_k z}\)
\(\ds \) \(=\) \(\ds \dfrac 1 {\paren {1 - x_a z} \paren {1 - x_{a + 1} z} \cdots \paren {1 - x_b z} }\)


Lemma 2

\(\ds \map \ln {\map G z}\) \(=\) \(\ds \sum_{k \mathop \ge 1} \dfrac {S_k z^k} k\)


Then:

\(\ds e^{\map \ln {\map G z} }\) \(=\) \(\ds \map \exp {\sum_{k \mathop \ge 1} \dfrac {S_k z^k} k}\) Lemma 2
\(\ds \leadsto \ \ \) \(\ds \map G z\) \(=\) \(\ds \prod_{k \mathop \ge 1} e^{S_k z^k / k}\) Exponential of Sum
\(\ds \) \(=\) \(\ds \paren {1 + S_1 z + \dfrac { {S_1}^2 z^2} {2!} + \cdots} \paren {1 + \dfrac {S_2 z^2} 2 + \dfrac { {S_2}^2 z^4} {2^2 \times 2!} + \cdots} \cdots\) Definition of Exponential Function
\(\ds \) \(=\) \(\ds \sum_{m \mathop \ge 0} \paren {\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} } \dfrac { {S_1}^{k_1} } {1^{k_1} k_1 !} \dfrac { {S_2}^{k_2} } {2^{k_2} k_2 !} \cdots \dfrac { {S_m}^{k_m} } {m^{k_m} k_m !} } z^m\)



This needs considerable tedious hard slog to complete it.
In particular: It still needs to be demonstrated that $\paren {1 + S_1 z + \dfrac { {S_1}^2 z^2} {2!} + \cdots} \paren {1 + \dfrac {S_2 z^2} 2 + \dfrac { {S_2}^2 z^4} {2^2 \times 2!} + \cdots} \cdots = \sum_{m \mathop \ge 0} \paren {\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} } \dfrac { {S_1}^{k_1} } {1^{k_1} k_1 !} \dfrac { {S_2}^{k_2} } {2^{k_2} k_2 !} \cdots \dfrac { {S_m}^{k_m} } {m^{k_m} k_m !} } z^m$
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Finish}} from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.



Thus, by definition of generating function:

$h_m = \ds \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} } \dfrac { {S_1}^{k_1} } {1^{k_1} k_1 !} \dfrac { {S_2}^{k_2} } {2^{k_2} k_2 !} \cdots \dfrac { {S_m}^{k_m} } {m^{k_m} k_m !}$


Examples

Order 2

$\ds \sum_{i \mathop = a}^b \sum_{j \mathop = a}^i x_i x_j = \dfrac 1 2 \paren {\paren {\sum_{i \mathop = a}^b x_i}^2 + \paren {\sum_{i \mathop = a}^b {x_i}^2} }$


Order 3

$\ds \sum_{i \mathop = a}^b \sum_{j \mathop = a}^i \sum_{k \mathop = a}^j x_i x_j x_k = \dfrac { {S_1}^3} 6 + \dfrac {S_1 S_2} 2 + \dfrac {S_3} 3$

where:

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


Order 4

$\ds \sum_{a \mathop \le j_1 \mathop \le j_2 \mathop \le j_3 \mathop \le j_4 \mathop \le b} x_{j_1} x_{j_2} x_{j_3} x_{j_4} = \dfrac { {S_1}^4} {24} + \dfrac { {S_1}^2 S_2} 4 + \dfrac { {S_2}^2} 8 + \dfrac {S_1 S_3} 3 + \dfrac {S_4} 4$

where:

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


Also presented as

When usually presented, set $U$ is usually defined to be either $\set {x_0, x_1, \ldots, x_n}$ or $\set {x_1, x_2, \ldots, x_n}$.

This leads to the summation $h_m$ to be defined either as:

$h_m = \ds \sum_{0 \mathop \le j_1 \mathop \le \mathop \cdots \mathop \le j_m \mathop \le n} \paren {\prod_{k \mathop = 1}^m x_{j_k} }$

or:

$h_m = \ds\sum_{1 \mathop \le j_1 \mathop \le \mathop \cdots \mathop \le j_m \mathop \le n} \paren {\prod_{k \mathop = 1}^m x_{j_k} }$

and for the summations $S_r$ to be defined as either $\ds \sum_{k \mathop = 0}^n {x_k}^r$ or $\ds \sum_{k \mathop = 1}^n {x_k}^r$ accordingly.


However, this may cause confusion when the indices are presented differently between separate invocations of this general result.

For example, in Donald E. Knuth's The Art of Computer Programming: Volume 1: Fundamental Algorithms, 3rd ed. of $1997$:

in $\S 1.2.3$, $\ds \sum_{k \mathop = 0}^n$ is used for the cases $m = 2$ and $n = 3$

while:

in $\S 1.2.9$, the same result has been taken over $\ds \sum_{k \mathop = 1}^n$

without explanatory comment.


Hence the decision has been made on $\mathsf{Pr} \infty \mathsf{fWiki}$ to choose to define the set of indices over the general interval $\closedint a b$, to emphasise their essentially arbitrary nature.


Sources

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