# 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$?

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.

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

$$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)$$

• Could you elaborate on how to derive the polynomials then? As far as I understand, the Stirling numbers are defined recursively – theREALyumdub Sep 15 '16 at 20:31