Combinatorics and counting of subsets

Question

from set $S=${$1,2,3.....n$} in how many ways can we select two subsets $A$, $B$ such that $B$ is non empty and is contained in $A$ which is contained in $S$ And the number of cases in which the containment is proper. I dont need the answer just now but just hints I want to try the question myself. The basic issue is that i am not able to understand the question can anybody just give an example of $A$ and $B$ set and whats asked here. can somebody check my answer it is in the comments. should the answer be $n\choose k$×$k\choose r$ where summation is over $r$ from $1$ to $k$ and $k$ is fixed from $1$ to $n$

Answer 1

Identify an ordered pair of sets $\langle B,A\rangle$ satisfying $B\subseteq A\subseteq S$ with a function $f:S\to \{0,1,2\}$.

This by stating that $B:=f^{-1}(\{0\})$ and $A:=f^{-1}(\{0,1\})$.

We are dealing with a one-to-one correspondence between these ordered pairs and these functions.

Let $W$ denote the set of functions $S\to\{0,1,2\}$ and define $U,V\subset W$ by:

• $U:=\{f\in W\mid0\notin\text{im} f\}$
• $V:=\{f\in W\mid1\notin\text{im} f\}$

Then $U$ corresponds with $\{\langle\varnothing,B\rangle\mid B\subseteq S\}$ and $V$ corresponds with $\{\langle B,B\rangle\mid B\subseteq S\}$.

It is obvious that $|W|=3^n$ and $|U|=|V|=2^n$ and $|U\cap V|=1$.

Observe that $\{\langle B,A\rangle\mid\varnothing\neq B\subseteq A\subseteq S\}$ corresponds with $U^c=\{f\in W\mid0\in\text{im} f\}$.

Observe that $\{\langle B,A\rangle\mid\varnothing\neq B\subsetneq A\subseteq S\}$ corresponds with $U^c\cap V^c=\{f\in W\mid0,1\in\text{im} f\}$.

It remains to find the cardinality of these sets and for the first we find :$$|U^c|=|W|-|U|=3^n-2^n$$

This agrees with your answer in the comment on the answer of David.

Can you find the cardinality of $|U^c\cap V^c|$ yourself? If not then you can take a look here:

$$|U^c\cap V^c|=|W|-|U\cup V|=|W|-|U|-|V|+|U\cap V|=3^n-2^{n+1}+1$$

Answer 2

suppose $A$ has $k$ elements ($0 \le k \le n$).

there are $\binom n k$ possible choices for such an $A$.

To get a $B$ which contains this $A$ we require $B = A \cup C$ where $C$ is any of the $2^{n-k}$ subsets of the complement of $A$.

thus you require the sum of $\binom n k 2^{n-k}$ over the permissible values of $k$.

hint: $\binom n k = \binom n {n-k}$