# References/Proof of the conjectured identity for the Stirling permutation number $\left\{{n\atop n-k}\right\}$

While working with a combinatorics problem, I conjectured that

$$\left\{{n \atop n-k }\right\}=\sum_{p=0}^{k-1}\bigg\langle\!\!\bigg\langle{k\atop k-1-p}\bigg\rangle\!\!\bigg\rangle \binom{n+p}{2k},$$

where $$\left\{ {n \atop k} \right\}$$ is the Stirling permutation numbers and $$\big\langle\!\big\langle{n \atop k}\big\rangle\!\big\rangle$$ denotes the Eulerian numbers of the second kind.

• All of my motivation comes from the fact that this is known to hold for $$k = 1, 2, 3$$. (See this, for instance.)

• I have little background on this topic, and I was unable to find this one from DLMF.

• I numerically checked that this identity holds for $$n = 1, \cdots, 10$$ using CAS and OEIS A008517.

Although I hardly believe that this type of identity is not known, I could not find any proof or reference to this one. So any additional information will be appreciated!

• Given that you've got an '$n-p$' term multiplied by a '$p$' term, your sum looks like a convolution of appropriate terms, and so should be straightforwardly writeable as a product of generating functions; that's absolutely the first axis I would explore along. Commented Dec 22, 2018 at 23:42
• @StevenStadnicki Nice point! I will definitely try that. Commented Dec 22, 2018 at 23:59
• I've just posted an induction proof for this formula as well as its twin formula for the Stirling cycle numbers, see math.stackexchange.com/a/4814252/61691 Commented Nov 26, 2023 at 9:37

Eq. (6.43) therein gives $$\left\{ \matrix{ x \cr x - n \cr} \right\} = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left\langle {\left\langle \matrix{ n \cr k \cr} \right\rangle } \right\rangle } \binom{x+n-1-k}{2n} \quad \left| \matrix{ \;0 \le n \in Z \hfill \cr \;x \in C \hfill \cr} \right.$$ which easily reduce to yours, and can be extended to define Stirling No. of 2nd kind, of the indicated form, to complex values of $$x$$.
Interestingly, also given is a twin one for the Stirling No. of 1st kind $$\left[ \matrix{ x \cr x - n \cr} \right] = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left\langle {\left\langle \matrix{ n \cr k \cr} \right\rangle } \right\rangle } \binom{x+k}{2n} \quad \left| \matrix{ \;0 \le n \in Z \hfill \cr \;x \in C \hfill \cr} \right.$$