Find a formula for $card(A)=n$

Question

Let $A$ be a finite set with $card(A)=n$, define a set $${\mathcal{S} }= \{(U,T) \in \mathcal{P}(A) \times \mathcal{P}(A)|U \subseteq T\}$$. Find a formula for $card({\mathcal{S} })$ in terms of n and prove it.

I tried to write down $\mathcal{S} $ explicitly when A has a small number of element but didn’t find anything.

Thanks for any help!!

Answer 1

In $A$ there exists $\binom{n}{k}$ subsets of size $k$, and each subset of size $k$ has $2^k$ subsets, so $$ card(S)=\sum_{k=0}^n\binom{n}{k}2^k=(1+2)^n=3^n $$ By binomial theorem.

Answer 2

Hint:

$$\mathcal{S}=\bigcup_{T\in\mathcal{P}(A)}\{(S,T)\mid S\in\mathcal{P}(T)\} $$

Answer 3

You can also answer it using combinatorics with an element-wise view. The solution is equivalent to finding the number of ways that one can form two subsets $S$ and $T$ of $A$ (with $n$ elements), where $S\subseteq T$. To form such subsets, for any single element $x\in A$ there are three choices:

• $x\notin T, x\notin S$
• $x\in T, x\notin S$
• $x\in T, x\in S$

Since there are total $n$ elements, the number of ways to form subsets $S$ and $T$ would be $3^n$.