Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
Thank you very much for the explanation. :) –  Tiomi Jan 29 '12 at 9:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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