Number of $3$-tuples $(A,B,C)$ if $A\subseteq B\subseteq C\subseteq S$ with $|S|=n$ 
What is the number of $3$-tuples $(A,B,C)$ if $A\subseteq B\subseteq C\subseteq S$ with $|S|=n$?

I imagine I can solve this by defining 4 possibilities for each element in $\{1,\dots,n\}$:

*

*$e\in A$

*$e\in B\setminus A$

*$e\in C\setminus B$

*$e\in S\setminus C$
and then the answer would be $4^n$. But how can I prove this by using more appropriate mathematical techniques?
 A: If you want to be very formal about what you're doing, you can define a bijection between the number of triples $(A,B,C)$ in the problem, and the number of functions $f : S \to \{1,2,3,4\}$. There are $4^n$ such functions almost by definition, so this would tell you that there are $4^n$ triples $(A,B,C)$ with $A \subseteq B \subseteq C \subseteq S$.
The bijection is this. Given $(A,B,C)$ with $A \subseteq B \subseteq C \subseteq S$, define $$f(x) = \begin{cases}1 & x \in A \\ 2 & x \in B\setminus A \\ 3 & x \in C \setminus B \\ 4 & x \in S \setminus C\end{cases}$$ Going the other way, given $f : S \to \{1,2,3,4\}$, define $A = \{x \in S : f(x) = 1\}$, $B = \{x \in S : f(x) \le 2\}$, and $C = \{x \in S : f(x) \le 3\}$.

But in my opinion, this is not really adding anything to what you've already done. The key thing is to realize that there are $4$ possibilities for each element of $S$; making a $4$-way choice for each of $n$ elements means $4^n$ choices total, and uniquely specifies $(A,B,C)$.
