How many sequences of subsets are there such that $T_1 \subseteq T_2 \subseteq \cdots\subseteq T_k$? 
Problem: Given a positive integer $k$ and a set $S$ with $|S| = n$, how many sequences $(T_1, T_2, ... , T_k)$ of subsets $T_i$ of $S$ are there such that $T_1 \subseteq T_2 \subseteq \cdots\subseteq T_k$? 

Hint: Suppose $x \in S$. If I tell you $x \in T_5$ for one particular sequence of subsets, what do you know about $x$’s inclusion in the other subsets?
My thought (or lack thereof) process: I don't think I understand what the question is asking. What exactly is in set $S$? And are we asked to count the number of times $T_i$ appears in each sequence? If so, I think we need to use the binomial theorem or some deviation of it to count the number.
 A: Without loss of generality, let $S=\{1,2,\dots,n\}$.  (In the case that $S$ contains more exotic elements, since it is finite we may define an order on the elements of $S$.)
Recognize that the set of chains of length $k$ of subsets (sequences with the property that each set is a subset of the next in the chain) of an $n$ element set are in direct bijection with the set of sequences of length $n$ with each entry one of $\{0,1,2,\dots,k\}$.
The bijection is straightforward.  Described in words: given a specific chain $T_1\subseteq T_2\subseteq \dots \subseteq T_k$ it shall map to the sequence $(a_1,a_2,\dots,a_n)$ where $a_i$ is the index where element $i$ first appears as an element in the chain or $0$ if it never appears as an element in the chain.  Conversely, given a sequence $(a_1,a_2,\dots,a_n)$ define the sets in the chain $T_1\subseteq\dots \subseteq T_k$ as $T_j = \{i~:~0<a_i\leq j\}$.
The number of sequences in $\{0,1,\dots,k\}^n$ is $|\{0,1,\dots,k\}|^n=(k+1)^n$

Alternatively, describe this using multiplication principle.  For element $i\in S$, choose which value is the index of the set which first contains it or if it is not contained in any such set.  As there are $k+1$ options for each and $n$ elements which we need to make such a selection for, there are then $(k+1)^n$ such chains of length $k$.
A: Let $S$ be a set of $n$ elements, in our case, let's assume it is $S=\{1,2,\dots,n\}$ and let $k$ be a positive integer. Let, also, $a_{n,k}$ be the number of sequences of subsets $T_1,T_2,\dots,T_k$ of $S$, such that $T_1\subseteq T_2\subseteq\dots\subseteq T_k$. Then we notice that, after we choose the first set $T_1$, we have to choose any other subset of $S$ with at least $|T_1|$ elements, that includes $T_1$, or, in other words, we have to choose any sequance of $k-1$ subsets of $S\setminus T_1$, which means that we have $a_{n-|T_1|,k-1}$ choices. Since $|T_1|$ can take any value from $1$ to $n$ and there are $\binom{n}{i}$ subsets of $S$ with exactly $i$ elements, by the additive principle, we get:
$$a_{n,k}=\sum_{i=0}^n\binom{n}{i}a_{n-i,k-1}$$
which seems pretty messy! However, we can change the counter $i$ to $j=n-i$, and we will get - since $\binom{n}{k}=\binom{n}{n-k}$:
$$a_{n,k}=\sum_{j=0}^n\binom{n}{n-j}a_{j,k-1}=\sum_{j=0}^n\binom{n}{j}a_{j,k-1}$$
which is nicer.
No, we will prove, by induction to $k$, that $a_{n,k}=(k+1)^n$ for every $n\in\mathbb{N}$.


*

*For $k=1$, we actually have to choose just a subset of $S$, so we have $a_{n,1}=2^n=(1+1)^n$ ways to do it.

*Let's assume that the statement stands for $k-1$, hence, $a_{n,k-1}=k^n$ for every $n\in\mathbb{N}$. By our inductive formula, we have:
$$a_{n,k}=\sum_{j=0}^{n}\binom{n}{j}a_{j,k-1}=\sum_{j=0}^n\binom{n}{j}k^j\overset{\text{binomial}}{\underset{\text{theorem}}{=}}(k+1)^n$$
which completes the proof.

A: Hint: To each element, we can associate the index of the smallest set it's in (let's give it the number $k+1$ if it's not in any of the sets); this is a number between $1$ and $k+1$. Conversely, given any function from $S\to\{1,2,\dots,k+1\}$, can we associate a unique sequence of such sets?
