Sum of increasing integer numbers 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.
 A: 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}.$$
A: 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$
A: 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}.$$
