2
$\begingroup$

Suppose you have a set $S$ of $n$ elements. If you fix some positive integer $\ell$, how many sequences of subsets $X_i\subset S$ can one make such that $X_1\subseteq X_2\subseteq\cdots X_\ell$?

My hunch is that if for any $s\in S$, there is a least $X_i$ such that $s\in X_i$, that is, if $s$ is in any of the $X_i$ at all. Does this somehow describe all such sequences for a total of $(\ell+1)^n$? I guess I don't see why that would give the total of such nested sequences, if it indeed does.

1 Answers 1

3

Yes, for each $s\in S$ there is a least $i$ such that $s\in X_i$, unless $s\not\in X_i$ for all $i$. This is because every nonempty subset of $\{1,2,3,\ldots, \ell\}$ has a least element. Your observation can be used to proved that the number is $(\ell+1)^n$ by induction. Let's call the number in question $A_n$.

Suppose $s\in S$ (so for now we're assuming n>0). For $i\in\{1,2,\ldots,\ell\}$, let $C_i$ be the set of those sequences such that $s$ first appears in the $i^\text{th}$ set, and let $C_{\ell+1}$ be the set of those sequences in which $s$ never appears. Each $C_i$, with $i\in\{1,2,\ldots,\ell+1\}$, is in bijection with the set of nested sequences of subsets of $S\setminus\{s\}$ of length $\ell$. If $X_1\subseteq X_2\subseteq\cdots\subseteq X_\ell$ is a sequence of subsets of $S\setminus\{s\}$, then

$X_1\subseteq X_2\subseteq\cdots\subseteq X_{i-1}\subseteq X_i\cup\{s\}\subseteq X_{i+1}\cup\{s\}\subseteq\cdots\subseteq X_\ell\cup\{s\}$ is in $C_i$, and this indicates how the bijection is established. This implies that the number of such sequences is $A_n=|C_1|+|C_2|+\cdots +|C_{\ell+1}|=(\ell+1)|C_{\ell+1}|$. But note that $|C_{\ell+1}|=A_{n-1}$, so we have the recursive formula $A_n=(\ell+1)A_{n-1}$ for all $n>0$. Together with the fact that $A_0=1$, we conclude by induction that $A_n=(\ell+1)^n$ for all $n$.


Here's another way to think of it. For each $s\in S$, you have a choice of $\ell+1$ places $s$ can appear in each sequence, including not appearing at all. There are $n$ such choices, they are independent, and they uniquely determine the sequence, so multiplying gives $(\ell+1)^n$ sequences.

  • 0
    Thank you very much for the explanation. :)2012-01-29