Explicit formula for elementary symmetric sum

Question

For $k\ge1$, $j\ge1$, Let $$e_k(j)=\sum_{1\le i_1<...<i_k\le j}i_1\cdot\cdot\cdot i_k.$$ We know that $e_k(j)$ is a polynomial in $j$ with coefficients depending on $k$. I am curious about whether there is an explicit formula for the coefficients?

Answer 1

More specifically, $e_k(j)=c(j+1,j+1-k)$, where $c(j+1,j+1-k)$ is a signless Stirling number of the first kind. For a discussion of this polynomial see http://math.mit.edu/~rstan/pubs/pubfiles/29.pdf. In particular, Theorem 2.1 gives a combinatorial interpretation of the coefficients of the polynomial $(1-x)^{2k+1}\sum_j e_k(j)x^j$, but I am unaware of a combinatorial interpretation of the coefficients of $e_k(j)$ themselves. For instance, $$ e_4(j) = \frac{1}{384}j^8-\frac{1}{96}j^7-\frac{1}{576}j^6+\frac{1}{30}j^5-\frac{5}{1152}j^4 $$ $$ \qquad -\frac{1}{32}j^3+\frac{1}{288}j^2+\frac{1}{120}j. $$ Even the signs of the coefficients don't seem very regular.

Answer 2

Yes. What you ask about are Stirling numbers of the first kind $s(j,j-k)$. Formula (21) http://mathworld.wolfram.com/StirlingNumberoftheFirstKind.html is an explicit expression for fixed $k$.

Answer 3

So we have $$ e_m (n) = \sum\limits_{\matrix{ {} \cr {1\, \le \,k_{\,1} \, < \,k_{\,2} \, < \, \cdots \, < \,k_{\,m} \, \le \,n} \cr } } {\prod\limits_{1\, \le \,j\, \le \,m} {k_{\,j} } } = \left[ \matrix{ n + 1 \cr n + 1 - m \cr} \right] $$ (as can be deducted from the recurrence $$ e_m (n) = \sum\limits_{0\, \le \,\left( {1\, \le } \right)\,j\, \le \,n} {j\;e_{m - 1} (j - 1)} + \left[ {0 = m} \right] $$ where $[P]$ is the Iverson bracket ).

and we want to express $e_m(n)$ as a polynomial in $n$ $$ e_m (n) = \left[ \matrix{ n + 1 \cr n + 1 - m \cr} \right] = \sum\limits_k {a_{\,k,\,m} \,n^k } $$

To this purpose we recall the relation among Stirling Numbers and Binomials provided by the Eulerian Number of 2nd order. These relations are explained, e.g., in the renowned Concrete Mathematics at page 271, and for the (unsigned) Stirling N. - 1st kind it reads $$ \left[ \matrix{ x \cr x - m \cr} \right] = \sum\limits_{\left( {0\, \le } \right)\,\,k\,\left( { \le \,m} \right)} {\left\langle {\left\langle \matrix{ m \cr k \cr} \right\rangle } \right\rangle \left( \matrix{ x + k \cr 2m \cr} \right)} \quad \left| {\;0 \le {\rm integer }m} \right. $$ which holds whenever $x$ is an integer, but can be extended to real or even complex values.

Each binomial in the sum at the RHS is already a polynomial in $x$ of degree $2m$, and we can convert the whole into standard power series as $$ \bbox[lightyellow] { \eqalign{ & \left[ \matrix{ n + 1 \cr n + 1 - m \cr} \right] = \sum\limits_{\left( {0\, \le } \right)\,\,k\,\left( { \le \,m} \right)} {\left\langle {\left\langle \matrix{ m \cr k \cr} \right\rangle } \right\rangle \left( \matrix{ n + 1 + k \cr 2m \cr} \right)} = \cr & = \sum\limits_{\left( {0\, \le } \right)\,\,j\,\left( { \le \,k + 1\, \le \,m + 1} \right)} {\left( {\sum\limits_{\left( {0\, \le } \right)\,\,k\,\left( { \le \,m} \right)} {\left\langle {\left\langle \matrix{ m \cr k \cr} \right\rangle } \right\rangle \left( \matrix{ k + 1 \cr j \cr} \right)} } \right)\left( \matrix{ n \cr 2m - j \cr} \right)} = \cr & = \sum\limits_{\left( {0\, \le } \right)\,\,k\,\left( { \le \,m} \right)} {{1 \over {\left( {2m} \right)!}}\left\langle {\left\langle \matrix{ m \cr k \cr} \right\rangle } \right\rangle \left( {n + 1 + k} \right)^{\,\underline {\,2m\,} } } = \cr & = {1 \over {\left( {2m} \right)!}}\sum\limits_{\left( {0\, \le } \right)\,\,j\,\left( { \le \,2m} \right)} {\left( {\left( \matrix{ 2m \cr j \cr} \right)\sum\limits_{\left( {0\, \le } \right)\,\,k\,\left( { \le \,m} \right)} {\left\langle {\left\langle \matrix{ m \cr k \cr} \right\rangle } \right\rangle \left( {1 + k} \right)^{\,\underline {\,2m - j\,} } } } \right)n^{\,\underline {\,j\,} } } \cr & = \sum\limits_{\left( {0\, \le } \right)\,\,l\,\left( { \le \,2m} \right)} {\left( {\sum\limits_{\left( {0\, \le \,l\, \le } \right)\,\,j\,\left( { \le \,2m} \right)} {\left( {\sum\limits_{\left( {0\, \le } \right)\,\,k\,\left( { \le \,m} \right)} {\left\langle {\left\langle \matrix{ m \cr k \cr} \right\rangle } \right\rangle \left( \matrix{ 1 + k \cr 2m - j \cr} \right)} } \right)\left( { - 1} \right)^{\,j - l} {1 \over {j!}}\left[ \matrix{ j \cr l \cr} \right]} } \right)n^{\,l} } \cr} } \tag{1}$$

Another formula to consider, that does not involve Eulerian N. but Stirling N. 2nd kind, is the following $$ \bbox[lightyellow] { \eqalign{ & \left[ \matrix{ n + 1 \cr n + 1 - m \cr} \right] = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,m} \right)} {\left\{ \matrix{ m + k \cr k \cr} \right\}\left( \matrix{ m - 1 - n \cr m + k \cr} \right)\left( \matrix{ m + 1 + n \cr m - k \cr} \right)} = \cr & = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,m} \right)} {\left( { - 1} \right)^{\,m + k} \left\{ \matrix{ m + k \cr k \cr} \right\}\left( \matrix{ n + k \cr m + k \cr} \right)\left( \matrix{ m + 1 + n \cr m - k \cr} \right)} \cr} } \tag{2}$$ however, the computation of the coefficients of the normal power series is more complicated.

Finally note that $$ \bbox[lightyellow] { \left[ \matrix{ n + 1 \cr n + 1 - m \cr} \right] = \left( {n + 1} \right)^{\,\underline {\,m + 1\,} } \;\sigma _{\,m} (n + 1) } $$ where $\sigma _{\,m} (x)$ are the Stirling convolution polynomials