Difference of the Stirling cycle numbers and the Stirling set numbers

Solution 1:

We can start from Concrete Mathematics, page 271, Equations (6.43) and (6.44). They are said to be obtained by induction on $n$, the second order Eulerian numbers are supposed to be defined by their basic recursion. With a slight modification, accounting for the difference in the definition of the second order Eulerian numbers between Concrete Mathematics and the OEIS, we have $${x \brace x-k}= \sum_j \Big<\Big< \begin {align*} &k\\ j&+1 \end{align*} \Big>\Big>{x+k-1-j\choose 2k} $$ $${x \brack x-k}= \sum_j \Big<\Big< \begin {align*} & k\\ j&+1 \end{align*} \Big>\Big>{x+j\choose 2k} $$ Then $$ \left| x\atop k\right| = {x \brack x-k}-{x \brace x-k}= \sum_j \Big<\Big< \begin {align*} &k\\ j&+1 \end{align*} \Big>\Big>\left({x+j\choose 2k}-{x+k-j-1\choose 2k} \right) $$ Then $$ \left| x\atop k\right| = \sum_j \Big<\Big< \begin {align*} &k\\ &j \end{align*} \Big>\Big>\left({x+j-1\choose 2k}-{x+k-j\choose 2k} \right) $$

Solution 2:

We seek to show that with $0\le k\le n$ the following identity holds:

$${n\brack n-k} - {n\brace n-k} = \sum_{j=0}^k \left({n+j-1\choose 2k} - {n+k-j\choose 2k}\right) \left\langle\!\! \left\langle k\atop j \right\rangle\!\! \right\rangle.$$

We will use the following two representations of the Eulerian numbers of the second order in terms of associated Stirling numbers (consult MSE link 4037172):

$$ \sum_{j=0}^{k} (-1)^{k-j} {n-j \choose k-j} \left\{ \!\! \left\{ n+j\atop j\right\} \!\! \right\} = \left\langle\!\! \left\langle n\atop k\right\rangle\!\! \right\rangle =\sum_{j=0}^{n-k+1} (-1)^{n-k-j+1} {n-j\choose k-1} \left[\! \left[ n+j\atop j\right] \! \right] $$

We get for the first piece

$$\sum_{j=1}^k {n+j-1\choose 2k} \sum_{p=0}^{k-j+1} (-1)^{k-j-p+1} {k-p\choose j-1} \left[\! \left[ k+p\atop p\right] \! \right] \\ = \sum_{p=0}^k \left[\! \left[ k+p\atop p\right] \! \right] (-1)^{k-p+1} \sum_{j=1}^{k+1-p} (-1)^j {n+j-1\choose 2k} {k-p\choose j-1} \\ = \sum_{p=0}^k \left[\! \left[ k+p\atop p\right] \! \right] (-1)^{k-p} [z^{2k}] (1+z)^n \sum_{j=1}^{k+1-p} (-1)^{j-1} (1+z)^{j-1} {k-p\choose j-1} \\ = \sum_{p=0}^k \left[\! \left[ k+p\atop p\right] \! \right] (-1)^{k-p} [z^{2k}] (1+z)^n (1-(1+z))^{k-p} \\ = \sum_{p=0}^k \left[\! \left[ k+p\atop p\right] \! \right] [z^{k+p}] (1+z)^n = \sum_{p=0}^k \left[\! \left[ k+p\atop p\right] \! \right] {n\choose k+p}.$$

Now this last piece evaluates combinatorially to ${n\brack n-k}$ when written as $\left[\! \left[ k+p\atop p\right] \! \right] {n\choose n-k-p}$ namely we choose $n-k-p$ fixed points and split the remaining $k+p$ elements into $p$ cycles of size at least two for a total of $n-k$ cycles. Here we must have $k+p\ge 2p$ or $p\le k.$ (We have classified by the number of fixed points).

We get for the second piece

$$\sum_{j=1}^k {n+k-j\choose 2k} \sum_{p=0}^{j} (-1)^{j-p} {k-p\choose j-p} \left\{\! \left\{ k+p\atop p\right\} \! \right\} \\ = \sum_{p=0}^k \left\{\! \left\{ k+p\atop p\right\} \! \right\} (-1)^p \sum_{j=p}^k (-1)^j {n+k-j\choose 2k} {k-p\choose j-p} \\ = \sum_{p=0}^k \left\{\! \left\{ k+p\atop p\right\} \! \right\} \sum_{j=0}^{k-p} (-1)^j {n+k-j-p\choose 2k} {k-p\choose j} \\ = \sum_{p=0}^k \left\{\! \left\{ k+p\atop p\right\} \! \right\} [z^{2k}] (1+z)^{n+k-p} \sum_{j=0}^{k-p} (-1)^j (1+z)^{-j} {k-p\choose j} \\ = \sum_{p=0}^k \left\{\! \left\{ k+p\atop p\right\} \! \right\} [z^{2k}] (1+z)^{n+k-p} \left(1-\frac{1}{1+z}\right)^{k-p} \\ = \sum_{p=0}^k \left\{\! \left\{ k+p\atop p\right\} \! \right\} [z^{2k}] (1+z)^{n} z^{k-p} = \sum_{p=0}^k \left\{\! \left\{ k+p\atop p\right\} \! \right\} {n\choose k+p}.$$

With this piece we get exactly the same reasoning as with the first one, namely it evaluates to ${n\brace n-k}$. We write it as $\left\{\! \left\{ k+p\atop p\right\} \! \right\} {n\choose n-k-p}$ in choosing the number of singletons, of which there are $n-k-p.$ The remaining $k+p$ elements are distributed into $p$ disjoint sets of at least two elements for a total of $n-k$ sets. We once more have the condition that $k+p\ge 2p$ or $p\le k.$ (We have classified by the number of singleton sets.)

This concludes the argument.