Summation of product of combination and Stirling numbers In finite algebra, there is an important case that is how to counting some types of elements such , idempotent, nilpotent, zero-divisors and so on. So i got a result in my problem which is
\begin{equation}
 \sum_{k=0}^{n-1}\binom{n}{n-k-1}S(n-k,2) 
\end{equation}
where, $$ n\in \mathbb {N} $$  and 
$$S(n-k,2)=2^{n-k-1}-1$$
I would like to simplify the expansion (1) and obtain the value of the product
\begin{equation}
 \binom{n}{n-k-1}S(n-k,2) 
\end{equation}
I think the result of expansion (1) is equal to\
\begin{equation}
 2S(n+1,3)
 \end{equation}
By using the identity
\begin{equation}
 S(n+1,m+1)=\sum_{k=m}^{n}\binom{n}{k}S(k,m)\\
  \qquad where, \qquad k\leq m\leq n.
\end{equation}
Indeed I am not sure. For instance if I put $n=6$, then
\begin{equation}
 \sum_{k=0}^{5}\binom{6}{n-k-1}S(n-k,2)=
 \binom{6}{5}S(6,2)+
 \binom{6}{4}S(5,2)+
 \binom{6}{3}S(4,2)+
 \binom{6}{2}S(3,2)+
 \binom{6}{1}S(2,2)+ \binom{6}{0}S(1,2)\\
 \nonumber
\end{equation}
\begin{equation}
 =602=2S(6+1,2+1)
 \nonumber 
\end{equation}
I need your help and notations about this problem and any sources such books and articles.
 A: Another simplification is
\begin{align*}
\color{blue}{\sum_{k=0}^{n-1}}&\color{blue}{\binom{n}{n-k-1}{n-k \brace 2}}\\
&=\sum_{k=0}^{n-1}\binom{n}{n-k-1}\left(2^{n-k-1}-1\right)\tag{1}\\
&=\sum_{k=0}^{n-1}\binom{n}{k}\left(2^k-1\right)\tag{2}\\
&=\sum_{k=0}^{n}\binom{n}{k}\left(2^k-1\right)-\left(2^n-1\right)\tag{3}\\
&=\sum_{k=0}^{n}\binom{n}{k}2^k-\sum_{k=0}^{n}\binom{n}{k}-2^n+1\tag{4}\\
&=3^n-2^n-2^n+1\tag{5}\\
&\,\,\color{blue}{=3^n-2^{n+1}+1}
\end{align*}
Comment:

*

*In (1) we use the identity ${n \brace 2}=2^{n-1}-1$.


*In (2) we change the order of summation $k\to n-1-k$.


*In (3) we set the upper limit of the sum to $n$ and subtract accordingly for compensation.


*In (4) we multiply out.


*In (5) we apply the binomial theorem twice.
A: So you want to compute
$$\sum _{k=0}^{n-1}\binom{n}{n-k-1}{n-k\brace 2},$$
I am using Knuth's notation for $S(n,k)={n\brace k}$.
Hint:
Do the change of variable $n=n-k$ and notice that ${n\brace 2}={n-1\brace 1}+2{n-1\brace 2}$ which for $n>1$ is $1+2{n-1\brace 2}$.
Using the formula you presented, the result is obtained.

 $\sum _{k=0}^{n-1}\binom{n}{n-k-1}{n-k\brace 2}=\sum _{k=1}^{n-1}\binom{n}{k}{k+1\brace 2}=\sum _{k=1}^{n-1}\binom{n}{k}(1+2{k\brace 2})=2^n-2+2{n+1\brace 3}-2{n\brace 2}=2{n+1\brace 3}$

