10
$\begingroup$

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?

$\endgroup$

3 Answers 3

12
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ Note that $e_4(j)=\frac{j(j-1)(j-2)(j-3)}{5760} (15 j^4 + 30 j^3 + 5 j^2 - 18 j - 8)$ so there should be much more to it. $\endgroup$
    – Wolfgang
    Sep 5, 2017 at 6:59
  • 1
    $\begingroup$ @Wolfgang: It is clear from the definition that $e_k(j)=0$ if $0\leq j\leq k-1$, since then we cannot have $k$ distinct integers between $1$ and $j$. $\endgroup$ Sep 5, 2017 at 16:50
  • $\begingroup$ Yes, and maybe the signs of the irreducible part have an easy pattern? E.g. some sort of "double unimodality" like a sinus curve? Just speculating based on the k=4 case... $\endgroup$
    – Wolfgang
    Sep 5, 2017 at 20:50
  • $\begingroup$ @Wolfgang: you are right in your supposition, there is a scheme for that, as reported in my answer $\endgroup$
    – G Cab
    Sep 12, 2017 at 23:16
  • $\begingroup$ @RichardStanley: you may be interested to know that such polynomials have a defined structure, as reported in my answer. $\endgroup$
    – G Cab
    Sep 14, 2017 at 11:23
10
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ The OP asked about the coefficients of this polynomial, not its values. $\endgroup$ Sep 4, 2017 at 18:27
  • 2
    $\begingroup$ For some information on coefficients of the closely related analogous polynomials for Stirling numbers of the second kind, see my paper "On Miki's identity for Bernoulli numbers", J. Number Theory, 110 (2005), 75–82, people.brandeis.edu/~gessel/homepage/papers/miki2.pdf $\endgroup$
    – Ira Gessel
    Sep 4, 2017 at 23:30
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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