Closed formula for the sums $\sum\limits_{1 \le i_1 < i_2 < \dots < i_k \le n} i_1 i_2 \cdots i_k $?

Question

I've worked out a few summation formulas, and I am hoping to find a pattern. Unless I have made a mistake somewhere, we have the following identities:

$$\sum_{1 \le i \le n} i = \frac{(n+1)n}{2} $$

$$\sum_{1 \le i < j \le n} ij = \frac{(3n+2)(n+1) \, n \, ( n-1)}{24}$$

$$\sum_{1 \le i < j < k \le n} ijk = \frac{(n+1)^2 \, n^2 \, (n-1)(n-2) }{48}$$

It seems clear that $$p_k(n)= \sum_{1 \le i_1 < i_2 < \dots < i_k \le n} i_1 i_2 \cdots i_k $$ is a polynomial in $n$ of degree $2k$. But is there a nice closed-form formula for it? Maybe in terms of its factorization?

Comment: I realize that what I am looking for is the coefficient of $t^k$ in the expansion $$(1+t)(1+2t) \dots (1+nt),$$ so maybe generating function techniques could be helpful. But the main way I know to extract the coefficient of $t^k$ is to take derivatives $k-1$ times and on the surface of things that looks like a huge mess.

Answer 1

Starting from your generating function we have

$$p_k(n) = [t^k] \prod_{q=1}^n (1+qt).$$

This is $$[t^k] t^n \prod_{q=1}^n (1/t+q) = [t^{k-n}] \prod_{q=1}^n (1/t+q).$$

Set $t=1/v$ to get

$$[v^{n-k}] \prod_{q=1}^n (v+q) = [v^{n-k+1}] \prod_{q=0}^n (v+q).$$

Now the RHS is precisely the generating function of the Stirling numbers of the first kind and we get

$$\left[n+1\atop n+1-k\right].$$

Answer 2

$$p_{k}(n) = S_1(n+1, n-k+1)$$ where $S_1$ are the unsigned Stirling numbers of the first kind.

EDIT: We then have $$p_k(x) = {x \choose k} S_k(x)$$ where $S_k(x)$ are the Stirling polynomials and $${x \choose k} = \dfrac{1}{k!} \prod_{j=0}^{k-1} (x - j)$$

Answer 3

$$Define:{\nabla ^0}f(n) = f(n),f(N) = \sum\limits_{n = 0}^{N - 1} {{\nabla ^1}f(n + 1)} ,{\nabla ^{ - 1}}f(N) = \sum\limits_{n = 0}^{N - 1} {f(n + 1)} $$ $${\mathop{\rm Re}\nolimits} {\rm{cursive}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} define{\kern 1pt} {\kern 1pt} {\kern 1pt} {\nabla ^p},p \in Z$$

---

$$Define:SUM(N,[{K_1}],[{T_1} = 1]) = \sum\limits_{n = 0}^{N - 1} {({K_1} + } n)$$ $$SUM(N,[{K_1},{K_2}],[{T_1} = 1,{T_2} = {T_1} + 2 - p]) = \sum\limits_{n = 0}^{N - 1} {({K_2} + } n){\nabla ^p}SUM(n + 1,[{K_1}],[{T_1}])$$ $${\rm{Re}}cursive\,\,\,define\,{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} SUM(N,[{K_1},{K_2}...{K_M}],[{T_1},{T_2}...{T_M}])$$

---

They are nested sums: $$SUM(N,[{K_1},{K_2},{K_3}],[1,2,3]) = \sum\limits_{n = 0}^{N - 1} {({K_1} + } n)({K_2} + n)({K_3} + n)$$ $$SUM(N,[{K_1},{K_2},{K_3}],[1,3,5]) = \sum\limits_{{n_3} = 0}^{N - 1} {({K_3} + } {n_3})\sum\limits_{{n_2} = 0}^{{n_2}} {({K_2} + } {n_2})\sum\limits_{{n_1} = 0}^{{n_2}} {({K_1} + } {n_1})$$

---

$$SUM(N,[1,1,1...1],[1,2,3...M]) = {1^M} + {2^M} + ... + {N^M}$$ $$SUM(N,[1,1,1...1],[1,3,5...2M - 1]) = {S_2}(N + M,N) = \sum\limits_{1 \le {i_1} \le {i_2} \le ... \le {i_M} \le N} {{i_1}{i_2}...{i_M}} $$ $$SUM(N,[1,2,3...M],[1,3,5...2M - 1]) = {S_1}(N + M,N) = \sum\limits_{1 \le {i_1} \prec {i_2} \prec ... \prec {i_M} \le N + M - 1} {{i_1}{i_2}...{i_M}} $$

$${\rm{SUM}}(n - k + 1,[1,2,3...k],[1,3,5...2k - 1]){\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} can{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} do{\kern 1pt} {\kern 1pt} {\kern 1pt} this{\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{calculation}}{\kern 1pt} {\kern 1pt} {\kern 1pt} $$

---

The calculation result is： $$SUM(N,[{K_1},{K_2}...{K_M}],[{T_1},{T_2}...{T_M}]) = \sum\limits_{g = 0}^M {H(g)\left( {_{{T_M} - M + 1 + g}^{N + {T_M} - M}} \right)} $$ To obtain H(g), use an auxiliary form to calculate. $$({K_1} + {T_1})({K_2} + {T_2})...({K_M} + {T_M}) = \sum {\coprod\limits_{i = 1}^M {{X_i}} } ,{X_i} = {K_i}{\kern 1pt} {\kern 1pt} or{\kern 1pt} {\kern 1pt} {\kern 1pt} {T_i}$$ Define: $$X(T) = count{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} of{\kern 1pt} {\kern 1pt} {\kern 1pt} {X_i} \in \{ {T_1},{T_2},{T_3}...{T_M}\} $$ $${X_{T - 1}} = count{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} of\{ {X_1},{X_2}...{X_{i - 1}}\} \in \{ {T_1},{T_2}...{T_{i - 1}}\} $$ $${X_{K - 1}} = count{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} of\{ {X_1},{X_2}...{X_{i - 1}}\} \in \{ {K_1},{K_2}...{K_{i - 1}}\} $$ $${X_{T - 1}} + {X_{K - 1}} = i - 1$$

Don't swap the factors in the ∏X_i,then each ∏X_i corresponds to one expression in the sum. $$H(g) = \sum\limits_{X(T) = g} {\prod\limits_{i = 1}^M {{B_i}} } .If{\kern 1pt} {\kern 1pt} {X_i} = {T_i}{\kern 1pt} {\kern 1pt} {\kern 1pt} then{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {B_i} = {T_i} - {X_{K - 1}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} else{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {B_i} = {K_i} + {X_{T - 1}}$$

---

For example,SUM(N,[1,2,3],[1,3,5]): $$Form = ({K_1} + {T_1})({K_2} + {T_2})({K_3} + {T_3}) = (1 + {T_1})(2 + {T_2})(3 + {T_3})$$ $$\sum\limits_{X(T) = 0} {\prod {{X_i}} } = {K_1}{K_2}{K_3} \to H(0) = 1 \times 2 \times 3 = 6$$ $$\sum\limits_{X(T) = 1} {\prod {{X_i}} } = {T_1}{K_2}{K_3} + {K_1}{T_2}{K_3} + {K_1}{K_2}{T_3} \to $$ $$\eqalign{ & H(1) = {T_1}(2 + {X_{T - 1}})(3 + {X_{T - 1}}) + {K_1}({T_2} - {X_{K - 1}})({K_3} + {X_{T - 1}}) + {K_1}{K_2}({T_3} - {X_{T - 1}}) \cr & = 1 \times (2 + 1) \times (3 + 1) + 1 \times (3 - 1) \times (3 + 1) + 1 \times 2 \times (5 - 2) = 26 \cr} $$ $$SUM(N,[1,2,3],[1,3,5]) = 15\left( {_6^{N + 2}} \right) + 35\left( {_5^{N + 2}} \right) + 26\left( {_4^{N + 2}} \right) + 6\left( {_3^{N + 2}} \right)$$

Answer 4

There is also a basic proof by induction based on the recursion formula $$\left[n \atop k\right] = \left[n-1\atop k-1\right] + (n-1)\left[n-1\atop k\right]$$ for the Stirling cycle numbers, which holds for all $k\in\mathbb Z$ and $n \geq 0$.

To get simpler expressions, we shift $n$ by one and show for all $n,k\geq 0$ the equation $$ \sum_{0 < i_1 < i_2 < \ldots < i_k < n} i_1 i_2 \cdots i_k = \left[n\atop n-k\right] $$

We use induction over $n$.

For $n=0$ and $k=0$, on the right hand side we have $[{0\atop 0}] = 1$, and on the left hand side there is a single summand (namely the empty sequence of $k_i$s), which is an empty product and thus has the value $1$. For $n=0$ and $k > 0$, on the right hand side we have $[{0\atop k}] = 0$, and on the left hand side we have an emtpy sum, which has the value $0$. (If this is too esoteric, start with $n=1$ instead.)

Now let $n\geq 1$. We split the set of all Summands into those with $i_k < n-1$ and those whith $i_k = n$. We get $$\sum_{0 < i_1 < i_2 < \ldots < i_k < n} i_1 i_2 \cdots i_k = \sum_{0 < i_1 < i_2 < \ldots < i_k < n-1} i_1 i_2 \cdots i_k + \sum_{0 < i_1 < i_2 < \ldots < i_{k-1} < n-1} i_1 i_2 \cdots i_{k-1} \cdot (n-1)$$ By the induction hypothesis, this equals $$\left[n-1\atop k\right] + (n-1)\left[n-1\atop k-1\right]$$ Which by the recursion formula finally equals $$\left[n \atop n-k\right].$$