For given natural numbers $n,k$, how many are there $k$-tuples $(A_1,A_2,\cdots ,A_k)$ such that $$A_1\subseteq A_2\subseteq\cdots \subseteq A_k\subseteq \{1,2,3,\cdots ,n\}$$ I've thought to prove by induction on $k$ that the number of $k$-tuples is equal to $$\sum_{t=0}^n{n\choose t}k^t=(k+1)^n$$ Though I have no idea what happens when you add another subset,my idea was when I add another subset to let it be $A_1$ and shift every other subset index by $1$.Then split it into $n+1$ cases such that $|A_2|=t$ for each $t$ from $0$ to $n$.

Maybe there is a better way.

  • $\begingroup$ Which one ???$$A_1\subseteq A_2\subseteq\cdots \subseteq A_k\subseteq \{1,2,3,\cdots ,n\}\\ A_1\subset A_2\subset\cdots \subset A_k\subseteq \{1,2,3,\cdots ,n\}$$? $\endgroup$
    – Khosrotash
    Feb 3 '17 at 18:30
  • $\begingroup$ @Khosrotash The first one $\endgroup$
    – kingW3
    Feb 3 '17 at 18:31
  • 3
    $\begingroup$ $(k+1)^n$ is the right answer. Hint: assign to each element of $\{1,\dots,n\}$ a number from $0$ to $k$ according to the sequence $A_1\subseteq\dots\subseteq A_k$. $\endgroup$
    – zhoraster
    Feb 3 '17 at 19:06
  • $\begingroup$ @zhoraster Oh this seems too easy,thanks. $\endgroup$
    – kingW3
    Feb 3 '17 at 20:23

The easiest solution is certainly the one in the comments, but we can approach the problem using induction in the following way:

The first observation is that the only important property of the set $\lbrace 1, 2, \dots, n \rbrace$ in the problem is that it has $n$ elements. We would have the same answer if we replaced it with any other set with $n$ elements.

We now use induction on $k$. For the base case, we consider $k = 1$. If we only want a single subset

$$ A_1 \subseteq \lbrace 1, 2, \dots, n \rbrace $$

then $A_1$ can be any of the $2^n = {(1+1)}^n$ subsets of $\lbrace 1, 2, \dots, n \rbrace$, and so the number of subsets in this case is indeed ${(k+1)}^n$.

Now suppose that the result is true for some $k$ and for every $n$. We wish to then prove that the number of ways of choosing sets $A_1, A_2, \dots, A_{k+1}$ such that

$$ A_1 \subseteq A_2 \subseteq \dots \subseteq A_{k+1} \subseteq \lbrace 1, 2, \dots, n \rbrace $$

is equal to ${(k+2)}^n$.

We count the number of ways of choosing the subsets by considering the number of elements in $A_{k+1}$. Let this number be $m$. Then there are $\binom{n}{m}$ ways to choose the elements in $A_{k+1}$.

Now $A_{k+1}$ is a set with $m$ elements, so by our earlier observation that the set $\lbrace 1, 2, \dots, n \rbrace$ is arbitrary, we can see that once we have chosen $A_{k+1}$, the number of ways of choosing sets $A_1, A_2, \dots, A_k$ such that

$$ A_1 \subseteq A_2 \subseteq \dots \subseteq A_k \subseteq A_{k+1} $$

is equal to ${(k+1)}^m$.

Thus the number of ways of choosing sets $A_1, A_2, \dots, A_{k+1}$ such that $$ A_1 \subseteq A_2 \subseteq \dots \subseteq A_{k+1} \subseteq \lbrace 1, 2, \dots, n \rbrace $$ and such that $A_{k+1}$ has $m$ elements is equal to $$ \binom{n}{m} {(k+1)}^m. $$

We see that the total number of ways of choosing the sets $A_1, A_2, \dots, A_{k+1}$ is then equal to

$$ \sum_{m=0}^{n} \binom{n}{m} {(k+1)}^m $$

which by the binomial theorem is equal to ${(k+2)}^n$.

  • $\begingroup$ Thanks for posting your answer (I hope it will be accepted), sparing me the necessity to turn my comment into an answer :) $\endgroup$
    – zhoraster
    Feb 4 '17 at 19:42

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.