The binomial product sum \begin{align*} \sum\limits_{\substack{i_1> i_2> \cdots > i_k\\i_1, i_2, \cdots, i_k \in \{1, 2, \cdots, n-1\}}}\binom{n}{i_1}\binom{i_1}{i_2}\binom{i_2}{i_3}\cdots\binom{i_{k-1}}{i_k}\binom{i_k}{0} \end{align*} with the convention that if the summation is over an empty subset, then only $\binom{n}{0}$ occurs in the product. This formula gives the sequence of Fubini numbers on varying $n$ along $1,2,3,\ldots$. A justification for this appears in the page Closed form for a binomial product sum. Now I have a slightly modified question. The same binomial product sum with the following modification \begin{align*} \sum\limits_{\substack{i_1> i_2> \cdots > i_k\\i_1, i_2, \cdots, i_k \in \{1, 2, \cdots, n-1\}}}(-1)^{n+k+1}\binom{n}{i_1}\binom{i_1}{i_2}\binom{i_2}{i_3}\cdots\binom{i_{k-1}}{i_k}\binom{i_k}{0} \end{align*} gives the constant sequence $1,1,1,\ldots$ for $n=1,2,3,\ldots$ as verified using the sagemath code posted here. The cancellations in the summation is not very insightful if one check some concrete example. Is there any way to say that this sum is indeed going to give 1 all the times? What could be a justification for this?
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ It's simpler to state the summands as miltinomial coefficients. $\endgroup$– Max AlekseyevCommented Feb 3, 2022 at 2:12
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
Just as the Fubini numbers are the coefficients of the exponential generating function $$\sum_{k=0}^\infty (e^x-1)^k = \frac{1}{2-e^x},$$ the exponential generating function for the alternating sum is $$\sum_{k=0}^\infty (1-e^{-x})^k = e^x.$$
-
$\begingroup$ Can you please explain how did you arrive at this exponential function? I am asking this because I need to understand the binomial product sum \begin{align*} \sum\limits_{\substack{i_1> i_2> \cdots > i_k\\i_1, i_2, \cdots, i_k \in \{n-j+1,n-j+ 2, \cdots, n-1\}}}(-1)^{p+k+1}\binom{n}{i_1}\binom{i_1}{i_2}\binom{i_2}{i_3}\cdots\binom{i_{k-1}}{i_k}\binom{i_k}{n-j} \end{align*} with the convention that if the summation is over an empty subset, then only $\binom{n}{n-j}$ occurs in the product. Or otherwise, if I am not asking much, what could be the exponential generating function for this sum? $\endgroup$ Commented Feb 3, 2022 at 1:57
-
$\begingroup$ There is a $p$ appearing in the above expression in the comment (in the power to -1). It should be actually $n$. I am unable to edit and correct it. $\endgroup$ Commented Feb 3, 2022 at 2:11
-
1$\begingroup$ Your sum (for $n>0$) is equal to (or should be equal to) $$\sum_{k=1}^n \sum_{j_1+\cdots+j_k=n}(-1)^{n-k}\frac{n!}{j_1!\, j_2!\,\cdots j_k!}.$$ where $j_1,\dots, j_k$ must be positive. This is $n!$ times the coefficient of $x^n$ in $$\sum_{k=0}^\infty\left(\sum_{j=1}^\infty (-1)^{j-1}\frac{x^j}{j!}\right)^k.$$ $\endgroup$ Commented Feb 3, 2022 at 2:19