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.

  • 2
    $\begingroup$ Have you tried the easiest cases, like $k=1,k=2,k=n-1$ or $k=n$? $\endgroup$ – Arthur Mar 30 '15 at 20:16

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$

  • $\begingroup$ +1, nicely following a Master, or, should we say a Prince? $\endgroup$ – Did Mar 30 '15 at 21:17
  • $\begingroup$ I think that it's preferable to say master As we are here to find our own rich mathematical life, an share that life with others, and masters are always a part of that life! $\endgroup$ – Elaqqad Apr 1 '15 at 9:25
  • 1
    $\begingroup$ Search for "Princeps mathematicorum" in there. $\endgroup$ – Did Apr 1 '15 at 13:37

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}.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.