0
$\begingroup$

Please help with this combinatorial problem.

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

Thanks in advance.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Tad Nov 3 '15 at 5:42
  • 1
    $\begingroup$ I see that the second part of @6005's answer completes this hint. $\endgroup$ – Tad Nov 4 '15 at 2:58
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.