Summation of Products of n Numbers taken m at a time with Repetitions/Lemma 1
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 \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 \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.
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} }\) |
Proof
For each $k \in \set {a, a + 1, \ldots, b}$, the product of $x_k$ taken $m$ at a time is simply ${x_k}^m$.
Thus for $n = 1$ we have:
- $h_m = {x_k}^m$
Let the generating function for such a $\sequence {h_m}$ be $\map {G_k} z$.
From Generating Function for Sequence of Powers of Constant:
- $\map {G_k} z = \dfrac 1 {1 - x_k z}$
By Product of Summations, we have:
- $\ds \sum_{a \mathop \le j_1 \mathop \le \cdots \mathop \le j_m \mathop \le b} x_{j_1} \cdots x_{j_m} = \prod_{k \mathop = a}^b \sum_{j \mathop = 1}^m x_j$
Hence:
\(\ds \map G z\) | \(=\) | \(\ds \sum_{k \mathop \ge 0} h_k z^k\) | Definition of Generating Function | |||||||||||
\(\ds \) | \(=\) | \(\ds \prod_{k \mathop = a}^b \dfrac 1 {1 - x_k z}\) | Product of Generating Functions: General Rule | |||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac 1 {\paren {1 - x_a z} \paren {1 - x_{a + 1} z} \dotsm \paren {1 - x_b z} }\) |
$\blacksquare$
This article needs proofreading. Please check it for mathematical errors. If you believe there are none, please remove {{Proofread}} from the code.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 {{Proofread}} from the code. |
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.9$: Generating Functions: Exercise $7$