Closed form for a binomial product sum

Question

Is there any closed formula for 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\}}}\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.

When we take $n-j=0$ or equivalently $j=n$, by varying $n=1,2,3,\ldots$, we get the sequence of Fubini numbers (please see https://oeis.org/A000670) as the sum. I have verified this for first few natural numbers using SageMath software; and of course I do not have a theoretical justification even for this. For other values of $j$, the sum is not coming out in a nice closed form (or as a known sequence of numbers that could be located from OEIS) and I could not so far relate them to Fubini's numbers in any way.

Answer 1

For $j = 0$, the summand ${n \choose i_1} \cdots {i_{k - 1} \choose i_k}$ is counting the number of length $k+1$ chains $\{1, \ldots, n\} =: S_0 \supsetneq S_1 \supsetneq S_2 \supsetneq \cdots \supsetneq S_k$ of strictly nested subsets of $\{1, \ldots, n\}$ where $S_t$ has size $i_t$. Indeed, you can choose $S_1$ in ${n \choose i_1}$ many ways, $S_2$ in ${i_1 \choose i_2}$ many ways and so on. Summing over all of them, you get all the possible nested chains of subsets. A nested chain $S_0 \supsetneq S_1 \supsetneq \cdots \supsetneq S_k$ gives you an ordered partition $S_0 \setminus S_1, S_1 \setminus S_2, \ldots, S_k$. It's easy to see this correspondence is bijective. As Peter Taylor mentioned, this generalizes for $j < n$ to chains (and hence ordered partitions) where the last component has size $n - j$. It's unclear that this has a closed form.

Answer 2

Though it seems difficult to find a closed form for the above binomial sum, a simpler way to state it seems to come up from the hints given by @AstroNi and @peter-taylor. The first part in an ordered set partition with size $n-j$ can be chosen from $n$ in $\binom{n}{n-j} = \binom{n}{j}$ ways, and the remaining $j$ elements in the set can be chosen in any way giving ordered set partitions of a $j$ element set. Hence this number is equal to the Fubini number at $j$. The total sum is therefore $\binom{n}{j}\times \text{Fubini}(j)$. This is not an answer completely to my question above, but this observation seems to reduce the computational effort drastically. Thank you very much to both these hints.