Summation of product of combination and Stirling numbers

Question

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.

Answer 1

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}$

Answer 2

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.