Difference of the Stirling cycle numbers and the Stirling set numbers Denote by $\left\langle\!\! \left\langle k\atop  j\right\rangle\!\! \right\rangle$ the second-order Eulerian numbers A340556. Define
$$ \left| n\atop  k\right| = \sum_{j=0}^k \left( \binom{n + j - 1}{2k} - \binom{n + k - j}{2k} \right) \left\langle\!\! \left\langle k\atop  j\right\rangle\!\! \right\rangle .$$
Observe that the difference between the Stirling cycle numbers and the Stirling set numbers can be expressed as:
$$ \left[ n\atop k\right] -  \left\{ n\atop  k\right\} = \left| n\atop n- k\right| \quad (0 \le k \le n)$$
It is surprising that the difference between the two Stirling numbers had no entry in the OEIS -- until today! Now they are A341102. But what we still need is an independent combinatorial interpretation of these numbers. Who knows one?
Who is willing to delight the combinatorists among us with a proof of this identity?
 A: 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) $$
A: 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.
