How to count special sets?

35 Views Asked by At

Let $S$ be a set of $n$ objects. How many subsets are there such that $T_1,T_2,T_3$ are three subsets of $S$ such that $T_1 \subseteq T_2 \subseteq T_3$ ?

To me it looks like for two sets such that $T_1 \subseteq T_2$ is :

$n\choose 0 $ $2^{n}+$ $n\choose 1$ $2^{n-1} +..... $

2

There are 2 best solutions below

3
On

Hint:

Without loss of generality, let $S=\{1,2,3,4,\dots,n\}$

Consider the function $f(x)~:~S\to\{1,2,3,4\}$ defined as $f(x)=\begin{cases}1&\text{if}~x\in T_1\\2&\text{if}~x\in T_2\setminus T_1\\ 3&\text{if}~x\in T_3\setminus T_2\\4&\text{if}~x\in S\setminus T_3\end{cases}$

Confirm that $f$ truly is a function and consider what it has to do with your problem.

0
On

Such a configurations partitions $S$ into $4$ (not necessarily non-empty) parts: $T_1$, $T_2\setminus T_1$, $T_3\setminus T_2$ and $S\setminus T_3$. We can hence associate to any such configuration a unique assignment of each $k \in S$ to one of the $4$ parts.

It follows that there are $4^n$ such configurations.

EDIT: Oh well, guess I spoiled JMoravitz's answer.