We seek to show that with $0\le k\le n$ the following identity holds:
$$\sum_{j=0}^k (-1)^{k-j} {2n+1\choose k-j} {n+j\brace j} =
\sum_{j=0}^{n-k} (-1)^j {2n+1\choose j} {2n-k-j+1\brack n-k-j+1}.$$
We will start with the LHS. The chapter 6.2 on Eulerian Numbers
of Concrete Mathematics by Knuth et al. proposes the formula
$${n\brace m} = (-1)^{n-m+1} \frac{n!}{(m-1)!} \sigma_{n-m}(-m)$$
where $\sigma_n(x)$ is a Stirling polynomial and we have the identity
$$\left(\frac{1}{z} \log\frac{1}{1-z}\right)^x
= x \sum_{n\ge 0} \sigma_n(x+n) z^n.$$
We get
$$[z^{n-m}] \left(\frac{1}{z} \log\frac{1}{1-z}\right)^x
= x \sigma_{n-m}(x+n-m)$$
and hence
$$[z^{n-m}] \left(\frac{1}{z} \log\frac{1}{1-z}\right)^{-n}
= -n \sigma_{n-m}(-m)$$
which implies that for $n\ge m\ge 1$
$$\bbox[5px,border:2px solid #00A000]{
{n\brace m} = (-1)^{n-m} \frac{(n-1)!}{(m-1)!}
[z^{n-m}] \left(\frac{1}{z} \log\frac{1}{1-z}\right)^{-n}.}$$
This gives for the LHS
$$\sum_{j=1}^k (-1)^{k-j} {2n+1\choose k-j}
(-1)^n \frac{(n+j-1)!}{(j-1)!} [z^n]
\left(\frac{1}{z} \log\frac{1}{1-z}\right)^{-n-j}
\\ = (-1)^{n-k+1} n! [z^n]
\left(\frac{1}{z} \log\frac{1}{1-z}\right)^{-n-1}
[w^{k-1}] (1+w)^{2n+1}
\\ \times \sum_{j=1}^k {n+j-1\choose n} (-1)^{j-1} w^{j-1}
\left(\frac{1}{z} \log\frac{1}{1-z}\right)^{-j+1}.$$
Now the coefficient extractor in $w$ enforces the upper limit of the
sum and we may extend $j$ to infinity, getting
$$(-1)^{n-k+1} n! [z^n]
\left(\frac{1}{z} \log\frac{1}{1-z}\right)^{-n-1}
[w^{k-1}] (1+w)^{2n+1}
\frac{1}{(1+w/(\frac{1}{z} \log\frac{1}{1-z}))^{n+1}}
\\ = (-1)^{n-k+1} n! [z^n]
[w^{k-1}] (1+w)^{2n+1}
\frac{1}{(w+\frac{1}{z} \log\frac{1}{1-z})^{n+1}}.$$
Continuing,
$$ (-1)^{n-k+1} n! [z^n]
[w^{n+k}] (1+w)^{2n+1}
\frac{1}{(1+\frac{1}{w} \frac{1}{z} \log\frac{1}{1-z})^{n+1}}
\\ = (-1)^{n-k+1} n! [z^n]
[w^{n+k}] (1+w)^{2n+1}
\sum_{q\ge 0} {n+q\choose n} (-1)^q \frac{1}{w^q}
\left(\frac{1}{z} \log\frac{1}{1-z}\right)^q
\\ = (-1)^{n-k+1} n! [z^n]
\sum_{j=n+k}^{2n+1} {2n+1\choose j}
{n+j-(n+k)\choose n} (-1)^{j-(n+k)}
\\ \times
\left(\frac{1}{z} \log\frac{1}{1-z}\right)^{j-(n+k)}
\\ = (-1)^{n-k+1} n! [z^n]
\sum_{j=0}^{n-k+1} {2n+1\choose j+n+k}
{n+j\choose n} (-1)^{j}
\left(\frac{1}{z} \log\frac{1}{1-z}\right)^{j}
\\ = (-1)^{n-k+1} n!
\sum_{j=0}^{n-k+1} {2n+1\choose j+n+k}
{n+j\choose n} (-1)^{j} [z^{n+j}]
\left(\log\frac{1}{1-z}\right)^{j}
\\ = (-1)^{n-k+1} n!
\sum_{j=0}^{n-k+1} {2n+1\choose j+n+k}
{n+j\choose n} (-1)^{j}
\\ \times \frac{j!}{(n+j)!} \times (n+j)! [z^{n+j}]
\frac{1}{j!} \left(\log\frac{1}{1-z}\right)^{j}
\\ = (-1)^{n-k+1} \sum_{j=0}^{n-k+1}
{2n+1\choose j+n+k} (-1)^j {n+j\brack j}
\\ = (-1)^{n-k+1} \sum_{j=0}^{n-k+1}
{2n+1\choose 2n-j+1} (-1)^{n-k-j+1} {2n-k-j+1\brack n-k-j+1}
\\ = \sum_{j=0}^{n-k+1}
{2n+1\choose j} (-1)^j {2n-k-j+1\brack n-k-j+1}.$$
The Stirling number is zero for $j=n-k+1$ and we get at last
$$\sum_{j=0}^{n-k}
{2n+1\choose j} (-1)^j {2n-k-j+1\brack n-k-j+1}.$$
This is the RHS and we have the claim.
We seek to show that with $0\le k\le n$ the following identity holds:
$$ \sum_{j=0}^{k} (-1)^{k-j} {n-j \choose k-j}
\left\{ \!\! \left\{ n+j\atop j\right\} \!\! \right\} =
\sum_{j=0}^{n-k+1} (-1)^{n-k-j+1} {n-j\choose k-1}
\left[\! \left[ n+j\atop j\right] \! \right] $$
where we have associated Stirling numbers of the first and second kind.
Now from the combinatorial meaning of these numbers (cancel fixed
points resp. singleton sets) we have that
$$\left[\! \left[ n\atop k\right] \! \right] =
\sum_{q=0}^k (-1)^q {n\choose q} {n-q\brack k-q}$$
and
$$\left\{ \!\! \left\{ n\atop k\right\} \!\! \right\} =
\sum_{q=0}^k (-1)^q {n\choose q} {n-q\brace k-q}.$$
Consult OEIS A008306 and OEIS
A008299 for more information. We will only
use the second of these but we show the pair to illustrate the
similarity in their construction (PIE). The combinatorial classes for
these are $\def\textsc#1{\dosc#1\csod}\def\dosc#1#2\csod{{\rm
#1{\small #2}}} \textsc{SET}(\mathcal{U}\times\textsc{CYC}_{\ge
2}(\mathcal{Z}))$ and $\textsc{SET}(\mathcal{U}\times\textsc{SET}_{\ge
2}(\mathcal{Z})).$
We start with the LHS and obtain
$$\sum_{j=0}^{k} (-1)^{k-j} {n-j \choose k-j}
\sum_{q=0}^j (-1)^q {n+j\choose q} {n+j-q\brace j-q}.$$
With $n\ge 1$ this is
$$(-1)^k \sum_{j=1}^{k} {n-j \choose k-j}
\sum_{q=1}^j (-1)^q {n+j\choose j-q} {n+q\brace q}.$$
Recall e.g. from Concrete Mathematics chapter 6.2. that
$$\bbox[5px,border:2px solid #00A000]{
{n\brace m} = (-1)^{n-m} \frac{(n-1)!}{(m-1)!}
[z^{n-m}] \left(\frac{1}{z} \log\frac{1}{1-z}\right)^{-n}.}$$
We find for the LHS
$$(-1)^k \sum_{j=1}^{k} {n-j \choose k-j}
\sum_{q=1}^j (-1)^q {n+j\choose j-q}
(-1)^n \frac{(n+q-1)!}{(q-1)!} [z^n]
\left(\frac{1}{z} \log\frac{1}{1-z}\right)^{-n-q}
\\ = (-1)^{n-k+1} n! [z^n]
\left(\frac{1}{z} \log\frac{1}{1-z}\right)^{-n-1}
\sum_{j=1}^{k} {n-j \choose k-j}
\\ \times
\sum_{q=1}^j (-1)^{q-1} {n+j\choose j-q}
{n+q-1\choose q-1}
\left(\frac{1}{z} \log\frac{1}{1-z}\right)^{-q+1}
\\ = (-1)^{n-k+1} n! [z^n]
\left(\frac{1}{z} \log\frac{1}{1-z}\right)^{-n-1}
\sum_{j=1}^{k} {n-j \choose k-j}
\\ \times [w^{j-1}] (1+w)^{n+j}
\sum_{q=1}^j (-1)^{q-1} w^{q-1}
{n+q-1\choose q-1}
\left(\frac{1}{z} \log\frac{1}{1-z}\right)^{-q+1}.$$
Now the coefficient extractor enforces the upper limit of the inner sum
and we may extend $q$ to infinity, getting
$$(-1)^{n-k+1} n! [z^n]
\left(\frac{1}{z} \log\frac{1}{1-z}\right)^{-n-1}
\sum_{j=1}^{k} {n-j \choose k-j}
\\ \times [w^{j-1}] (1+w)^{n+j}
\frac{1}{(1+w/(\frac{1}{z}\log\frac{1}{1-z}))^{n+1}}
\\ = (-1)^{n-k+1} n! [z^n]
\sum_{j=1}^{k} {n-j \choose k-j}
[w^{j-1}] (1+w)^{n+j}
\frac{1}{(\frac{1}{z}\log\frac{1}{1-z}+w)^{n+1}}.$$
The inner term is
$$[w^{j-1}] (1+w)^{n+j}
\frac{1}{(\frac{1}{z}(\log\frac{1}{1-z}-z)+1+w)^{n+1}}
\\ = [w^{j-1}] (1+w)^{j-1}
\frac{1}{(1+\frac{1}{1+w} \frac{1}{z}(\log\frac{1}{1-z}-z))^{n+1}}.$$
Re-expanding the series,
$$(-1)^{n-k+1} n! [z^n]
\sum_{j=1}^{k} {n-j \choose k-j}
[w^{j-1}] (1+w)^{j-1} \\ \times
\sum_{q=j}^n {n+q\choose n} (-1)^q \frac{1}{(1+w)^q}
\left(\frac{1}{z}(\log\frac{1}{1-z}-z)\right)^q.$$
The upper limit on the inner sum results from $[z^n]$ because
$\frac{1}{z} (\log\frac{1}{1-z}-z) = \frac{1}{2} z + \cdots$ and the
lower one from the fact that $[w^{j-1}] (1+w)^{j-1-q} = 0$ when $1\le
q\le j-1$; $q=0$ produces a constant. Continuing,
$$(-1)^{n-k+1} n! [z^n]
\sum_{j=1}^{k} {n-j \choose k-j}
[w^{j-1}] \\ \times
\sum_{q=j}^n {n+q\choose n} (-1)^q \frac{1}{(1+w)^{q-(j-1)}}
\left(\frac{1}{z}(\log\frac{1}{1-z}-z)\right)^q
\\ = (-1)^{n-k} n! [z^n]
\sum_{j=1}^{k} {n-j \choose k-j}
\sum_{q=j}^n {n+q\choose n} (-1)^{q-j} {q-1\choose q-j}
\left(\frac{1}{z}(\log\frac{1}{1-z}-z)\right)^q
\\ = (-1)^{n-k} n!
\sum_{j=1}^{k} {n-j \choose k-j}
\sum_{q=j}^n {n+q\choose n} (-1)^{q-j} {q-1\choose q-j}
[z^{n+q}] \left(\log\frac{1}{1-z}-z\right)^q
\\ = (-1)^{n-k} n!
\sum_{j=1}^{k} {n-j \choose k-j}
\sum_{q=j}^n {n+q\choose n} (-1)^{q-j} {q-1\choose q-j}
\\ \times \frac{q!}{(n+q)!}
\times (n+q)! [z^{n+q}] \frac{1}{q!}
\left(\log\frac{1}{1-z}-z\right)^q
\\ = (-1)^{n-k}
\sum_{j=1}^{k} {n-j \choose k-j}
\sum_{q=j}^n (-1)^{q-j} {q-1\choose q-j}
\left[\! \left[ n+q\atop q\right] \! \right].$$
It remains to simplify the binomial coefficients:
$$(-1)^{n-k}
\sum_{j=1}^{k} [u^k] u^j (1+u)^{n-j}
\sum_{q=j}^n (-1)^{q-j} {q-1\choose q-j}
\left[\! \left[ n+q\atop q\right] \! \right].$$
We see that we may raise $j$ to $n$ owing to $[u^k]$:
$$(-1)^{n-k}
\sum_{j=1}^{n} [u^k] u^j (1+u)^{n-j}
\sum_{q=j}^n (-1)^{q-j} {q-1\choose q-j}
\left[\! \left[ n+q\atop q\right] \! \right]
\\ = (-1)^{n-k}
\sum_{q=1}^n \left[\! \left[ n+q\atop q\right] \! \right]
[u^k] (1+u)^n \sum_{j=1}^q {q-1\choose q-j} (-1)^{q-j}
u^j (1+u)^{-j}.$$
The inner term is
$$[u^k] (1+u)^n \frac{u^q}{(1+u)^q}
\sum_{j=0}^{q-1} {q-1\choose j} (-1)^{j}
\frac{(1+u)^j}{u^j}
\\ = [u^k] (1+u)^{n-q} u^q
\left(1-\frac{1+u}{u}\right)^{q-1}
\\ = [u^k] (1+u)^{n-q} u (-1)^{q-1}
= (-1)^{q-1} [u^{k-1}] (1+u)^{n-q}.$$
This yields
$$\sum_{q=0}^{n-k+1} (-1)^{n-k-q+1} {n-q\choose k-1}
\left[\! \left[ n+q\atop q\right] \! \right]$$
which is the claim. (Here we must have $n-q\ge k-1$ or $n-k+1\ge q$
else the binomial coefficient vanishes and we may lower the upper
limit from $n$ to $n-k+1.$)
Best Answer
"Concrete Mathematics (what else?) - Eulerian Numbers" - says:
"Second-order Eulerian numbers are important chiefly because of their connection with Stirling numbers"
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. $$