# The number of increasing sequences of $S_0, S_1, \ldots, S_k$ such that $S_0 = \varnothing$ and $S_k = \{1,2, 3, \ldots, n\}$

For any given $k$ and $n$, find the number of sequence of subsets $S_0, S_1, \ldots, S_k$ such that $$\varnothing = S_0 \subseteq S_1 \subseteq S_2 \subseteq \dots \subseteq S_k = \{1,2, \dots ,n\}.$$

• Hint: for each $i\in\{1,\cdots,n\}$, let $f(i)$ denote the smallest $j$ such that $i\in S_j$. This function uniquely determines the sequence of subsets, and the functions which can arise are easy to count. – Tad Nov 3 '15 at 5:42
Let $a_{n,k}$ be this value. Then, doing cases on $S_{k-1}$, we have (for $k \ge 1$) $$a_{n,k} = \sum_{i=0}^n {n \choose i} a_{i,k-1} \implies \frac{a_{n,k}}{n!} = \sum_{i=0}^n \frac{a_{i,k-1}}{i!} \frac{1}{(n-i)!}$$ We also have that $$a_{n,0} = \begin{cases} 1 & \text{if } n = 0 \\ 0 &\text{otherwise}.\end{cases}$$ Therefore, the generating function $A(x,y) = \sum a_{n,k} \frac{x^n}{n!} y^k$ satisfies $$A(x,y) = ye^x A(x,y) + 1.$$ We then get \begin{align*} A(x,y) &= \frac{1}{1 - ye^x} \\ &= \sum_{k=0}^\infty y^k e^{kx} \\ &= \sum_{n=0}^\infty \sum_{k=0}^\infty y^k \frac{(kx)^n}{n!} \end{align*} So that $$a_{n,k} = \boxed{k^n}.$$
Now that we have the value of $a_{n,k}$, how could we have come to this value quickly? We immediately see that for each $j = 1, 2, \ldots, n$, all we have to choose is at which point in the sequence of subsets we start including it. For example, maybe we include it in $S_3, S_4, \ldots$ but not in $S_0, S_1,$ or $S_2$. We can start including it at any point from $S_1$ to $S_k$, so there are $k$ possible choices for each $j = 1, 2 \ldots, n$. So the number of sequences of subsets is, by this combinatorial argument, again $k^n$.