Exercise 1.4.10* (Number of orders pairs $(\mathscr{A}, \mathscr{B})$ such that $\mathscr{A} \subseteq\mathscr{B} \subseteq{S}$)

Question

Let $\mathscr{S}$ be a set of $n$ elements. Count the number of ordered pairs $(\mathscr{A},\mathscr{B})$ of subsets such that $\varnothing \subseteq \mathscr{A} \subseteq \mathscr{B} \subseteq \mathscr{S}$. Let $c(j,k)$ denote the number of such ordered pairs for which $\mathscr{A}$ contains $j$ elements and $\mathscr{B}$ contains $k$ elements. Show that
$$(1+y+xy)^n = \sum_{0 \leq j \leq k \leq n} c(j,k) x^j y^k.$$
What does this give if $x=y=1$?

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

\begin{proof} 
\begin{enumerate}
\item[(a)] Let 
$$\mathscr{U}_{j,k}= \{(\mathscr{A},\mathscr{B}) \in \mathscr{P}_j(\mathscr{S}) 	imes \mathscr{P}_k(\mathscr{S}) \mid \mathscr{A} \subseteq \mathscr{B}\}.$$
Then $c(j,k) = |\mathscr{U}_{j,k}|$. Note that $\mathscr{U}_{j,k} = \varnothing$ and $c(j,k) = 0$ if $j>k$.

Informally, to count the elements of $\mathscr{U}_{j,k}$, we choose the $k$ elements of $\mathscr{B}$, among the $n$ elements of $\mathscr{S}$, in  $\binom{n}{k}$ ways. Then we choose the $j$ elements of $\mathscr{A}$, among the $k$ elements of $\mathscr{B}$, in $\binom{k}{j}$ ways. Thus
$$c(j,k) = \binom{n}{k} \binom{k}{j}.$$
(If we choose first the $j$ elements of $\mathscr{A}$, and then the $k-j$ elements of $\mathscr{B}\setminus \mathscr{A}$, we obtain
$$c(j,k) = \binom{n}{j} \binom {n-j}{k-j} = \frac{n!}{j!(n-k)!(k-j)!} = \binom{n}{k} \binom{k}{j}.)$$

I give now a more formal proof. Consider the map
$$\varphi
\left\{
\begin{array}{ccl}
\mathscr{U}_{j,k} &	o &\mathscr{P}_k(\mathscr{S})\
(\mathscr{A},\mathscr{B}) & \mapsto & \mathscr{B}
\end{array}
ight.
$$
For every $\mathscr{B} \in \mathscr{P}_k(\mathscr{S})$, we count the number of elements of the pre-image $\varphi^{-1}(\{\mathscr{B}\})$, with the help of the maps
$$\psi
\left\{
\begin{array}{ccl}
\varphi^{-1}(\{\mathscr{B}\}) & 	o & \mathscr{P}_j(\mathscr{B})\
(\mathscr{A}, \mathscr{B}) & \mapsto & \mathscr{A}
\end{array}
ight.
\qquad
\chi
\left\{
\begin{array}{ccl}
 \mathscr{P}_j(\mathscr{B})  & 	o & \varphi^{-1}(\{\mathscr{B}\})\
 \mathscr{A}   & \mapsto &(\mathscr{A}, \mathscr{B}).
\end{array}
ight.
$$
Since $\psi \circ \chi$ and $\chi \circ \psi$ are identities, $\psi$ is bijective, thus for every $\mathscr{B} \in \mathscr{P}_k(\mathscr{S})$,
$$|\varphi^{-1}(\{\mathscr{B}\}) | =  |\mathscr{P}_j(\mathscr{B})| = \binom{j}{i}.$$
Therefore
$$ |\mathscr{U}_{j,k}| = \binom{j}{i} |\mathscr{P}_k(\mathscr{S})|,$$
so
$$c(j,k) =  \binom{n}{k} \binom{k}{j}.$$

\item[b)] Moreover
\begin{align*}
(1+y+xy)^n &= (1 + (1+x)y)^n\
&=\sum_{k=0}^n \binom{n}{k} (1+x)^k y^k\
&=\sum_{k=0}^n  \binom{n}{k}  \sum_{j=0}^k \binom{k}{j} x^jy^k\
&= \sum_{k=0}^n  \sum_{j=0}^k \binom{n}{k} \binom{k}{j} x^jy^k\
&=\sum_{0 \leq j \leq k \leq n} \binom{n}{k} \binom{k}{j} x^jy^k,
\end{align*}
so
$$(1+y+xy)^n = \sum_{0 \leq j \leq k \leq n} c(j,k) x^jy^k.$$

\item[c)] If we apply this identity to $x=y=1$, we obtain
$$3^n = \sum_{0 \leq j \leq k \leq n} c(j,k) .$$

Let 
$$\mathscr{U}= \{(\mathscr{A},\mathscr{B}) \in \mathscr{P}(\mathscr{S}) 	imes \mathscr{P}(\mathscr{S}) \mid \mathscr{A} \subseteq \mathscr{B}\}.$$
Then
$$\mathscr{U} = \bigcup_{0 \leq j \leq k \leq n} \mathscr{U}_{j,k} \qquad 	ext{(disjoint union)}.$$
Therefore
$$|\mathscr{U}| =  \sum_{0 \leq j \leq k \leq n} c(j,k)  = 3^n.$$
If $\mathscr{S}$ contains $n$ elements, the number of ordered pairs $(\mathscr{A},\mathscr{B})$ of subsets of $\mathscr{S}$ such that $\mathscr{A} \subseteq \mathscr{B}$, is $3^n$.

(This can also be proved directly).

\end{enumerate}
\end{proof}

Exercise 1.4.10* (Number of orders pairs $(\mathscr{A}, \mathscr{B})$ such that $\mathscr{A} \subseteq\mathscr{B} \subseteq{S}$)

Answers

Comments

Exercise 1.4.10* (Number of orders pairs $(\mathscr{A}, \mathscr{B})$ such that $\mathscr{A} \subseteq\mathscr{B} \subseteq{S}$)

Answers

Comments

Add answer