Please help me to calculate this sum: $$ \sum\limits_{1\leq i_1 < i_2 <\ldots i_k \leq n} (i_1+i_2+\ldots+i_k). $$
Here $n$ and $k$ are positive integer numbers, and all the numbers $i_1, i_2, \ldots, i_k$ are positive integers.
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this communityPlease help me to calculate this sum: $$ \sum\limits_{1\leq i_1 < i_2 <\ldots i_k \leq n} (i_1+i_2+\ldots+i_k). $$
Here $n$ and $k$ are positive integer numbers, and all the numbers $i_1, i_2, \ldots, i_k$ are positive integers.
Double-counting is the key. Given any $m\in[1,n]$, it belongs to exactly $\binom{n-1}{k-1}$ $k$-tuples $(i_1,\ldots,i_k)$ with $1\leq i_1<i_2\ldots<i_{n-1}<i_n\leq n$, hence:
$$ \sum_{1\leq i_1<\ldots<i_n\leq n}(i_1+\ldots+i_k) = \sum_{m=1}^{n}m\binom{n-1}{k-1}=\binom{n+1}{2}\binom{n-1}{k-1}.$$
Using the Gauss method for sums: $$2S= \sum_{1\leq i_1<\ldots<i_n\leq n}(i_1+\ldots+i_k)+\sum_{1\leq i_1<\ldots<i_n\leq n}((n+1-i_1)+\ldots+(n+1-i_k))=(n+1)k \dbinom{n}{k} $$
because there is exactly $\binom{n}{k}$ $k$-tuples $(i_1,\ldots,i_k)$ with $1\leq i_1<i_2\ldots<i_{n-1}<i_n\leq n$
The reader may be surprised to learn that this can be solved with cycle indices.
Suppose we seek to evaluate $$\sum_{1\le q_1 \lt q_2 \lt \cdots \lt q_k \le n} (q_1+q_2+\cdots+q_k).$$
Using the cycle index $Z(P_k)$ of the unlabeled set operator $\mathfrak{P}_{=k}$ this is $$\left. \frac{d}{dz} Z(P_k)(z+z^2+\cdots+z^n)\right|_{z=1}.$$
The OGF of the set operator is $$G(w) = \exp\left(a_1 w - a_2 \frac{w^2}{2} + a_3 \frac{w^3}{3} - \cdots\right).$$
Doing the substitution we obtain $$H(w, z) = \exp\left(\sum_{q\ge 1} \frac{(-1)^{q-1} w^q}{q} \sum_{p=1}^n z^{pq}\right).$$
Differentiate to get $$\frac{d}{dz} H(w,z) = \exp\left(\sum_{q\ge 1} \frac{(-1)^{q-1} w^q}{q} \sum_{p=1}^n z^{pq}\right) \sum_{q\ge 1} \frac{(-1)^{q-1} w^q}{q} \sum_{p=1}^n pq z^{pq-1}$$
and set $z=1$ to obtain $$\left.\frac{d}{dz} H(w,z)\right|_{z=1} = \exp\left(n\log(1+w)\right) \sum_{q\ge 1} (-1)^{q-1} w^q \sum_{p=1}^n p \\ = {n+1\choose 2} (1+w)^n \frac{w}{1+w} = {n+1\choose 2} w (1+w)^{n-1}.$$
Extracting coefficients from this we finally obtain $$[w^k] {n+1\choose 2} w (1+w)^{n-1} = {n+1\choose 2} [w^{k-1}] (1+w)^{n-1} = {n+1\choose 2} {n-1\choose k-1}.$$