The Value of Certain Combinatorics Sum

Abstract

In this paper we analyze the values and the properties of the function $S(n,l):=\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n-k)^{l}\ \
(n,l\in \mathbb{N\cup }\left\{ 0\right\} ),$ for $n<l.$ At first, we obtain two recurrence relations. Namely, we prove that for
every $n\in \mathbb{N\cup } \left\{ 0\right\} $ and every $l\in \mathbb{N}$ such that $l>n,$ we have
\begin{equation*}
S(n+1,l)=\sum_{k=1}^{l-n}\binom{l}{k}S(n,l-k),
\end{equation*}
and also, for every $n\in \mathbb{N\cup }\left\{ 0\right\} $and every $l\in \mathbb{N}$, we have
\begin{equation*}
S(n+1,l)=(n+1)S(n,l-1)+(n+1)S(n+1,l-1).
\end{equation*}
Further, we conclude that for every $n\geq 2$ and every $l\geq n$ the following representation formula holds
\begin{multline*}
S(n,l) =\sum\limits_{k_{1}=1}^{l-(n-1)}\binom{l}{k_{1}}\sum
\limits_{k_{2}=1}^{l-k_{1}-(n-2)}\binom{l-k_{1}}{k_{2}}\\
\cdot\sum\limits_{k_{3}=1}^{l-k_{1}-k_{2}-(n-3)}\binom{l-k_{1}-k_{2}}{k_{3}}\dots
\sum\limits_{k_{n-1}=1}^{l-\sum\limits_{i=1}^{n-2}k_{i}-1}\binom{
l-\sum\limits_{i=1}^{n-2}k_{i}}{k_{n-1}}.
\end{multline*}
We obtain an explicit formula for the calculation $S(n,l),$ especially for $ l=n+1,\dots,n+5,$ and later we give a general result.

2000 Mathematics Subject Classification. 40B05, 11Y55, 05A10