Counting pairs of subsets satisfying certain conditions For a positive integer $n$, define $[n] = \{1,\dots,n\}$ and $\mathcal{P}([n])^* = \{A \subset [n] : A \ne [n] \text{ and } A \ne \emptyset\}$.
I want to count the number of sets $\{S,T\}$ ($S,T \in \mathcal{P}([n])^*$) satisfying

*

*$S \cap T = \emptyset$,


*$S \cap T \ne \emptyset$ and $S \cup T \subsetneq [n]$, and


*$S \cap T \ne \emptyset$ and $S \cup T = [n]$.
Answers:

*

*The cardinality of $\mathcal{P}([n])^*$ is equal to $2^n-2$. For each $S \in \mathcal{P}([n])^*$, we can take $T$ to be any non-empty subset of $S^c$. So for the first question the answer is $\sum_{S \in \mathcal{P}([n])^*}(2^{n-|S|}-1)$.


*Let $A \subsetneq [n]$ be a proper subset of $[n]$. I thought I can count $\{S,T\}$ satisfies $S \cap T \ne \emptyset$ and $S \cup T = A$ for various choices of $A$. In this case, I think $T$ should be $(A \backslash S) \cup B$ for various choices of $B \subset S$. But unable to proceed further.


*By taking $A$ to be $[n]$ in second problem we can get the answer to this question.
Kindly help me with filling up the gaps. Thank you.
 A: Your answer to the first question needs drastic simplification, preferably to a closed form, and is in any case incorrect: for $n=2$ it yields the value
$$\left(2^{2-|\{1\}|}-1\right)+\left(2^{2-|\{2\}|}-1\right)=2\,,$$
but the correct figure is $1$, since the only disjoint pair is $\big\{\{1\},\{2\}\big\}$. I agree with lulu in the comments that it’s easiest to count ordered pairs first and then make a correction.
Each ordered pair $\langle S,T\rangle$ of disjoint non-empty subsets of $[n]$ is defined by a partition of $[n]$ into three parts, $S$, $T$, and $[n]\setminus(S\cup T)$, where the third part is allowed to be empty. There are $3^n$ ways to divide $[n]$ into three parts if any of the parts are allowed to be empty. However, $2^n$ of these leave $S$ empty, because everything ends up in $T$ or in $[n]\setminus(S\cup T)$, and $2^n$ leave $T$ empty. Finally, there is exactly one division that leaves both $S$ and $T$ empty, so a simple inclusion-exclusion calculation shows that there are $3^n-2\cdot2^n+1$ ordered pairs of disjoint non-empty subsets of $[n]$. That counts each unordered pair twice, so the answer to the first question is
$$\frac{3^n-2\cdot 2^n+1}2=\frac{3^n+1}2-2^n\,.\tag{1}$$
As a quick check, $(1)$ yields $0,1$, and $6$ for $n=0,1,2$, and you can easily verify by hand that these are correct.
We can use a similar idea for the second question, this time dividing $[n]$ into $4$ parts, $S\setminus T$, $S\cap T$, $T\setminus S$, and $[n]\setminus(S\cup T)$, with the requirements that $S,T$, $S\cap T$, and $[n]\setminus(S\cup T)$ all be non-empty. Making $S\cap T$ non-empty automatically ensures that $S$ and $T$ are non-empty, so we need only count the division that make $S\cap T$ and $[n]\setminus(S\cup T)$ non-empty. Use the same sort of inclusion-exclusion argument that I used above, and show that there are $4^n-2\cdot 3^n+2^n$ divisions that make $S\cap T$ and $[n]\setminus(S\cup T)$ non-empty.
There is an added complication here, however: this count includes ordered pairs of the form $\langle S,S\rangle$, where $1\le|S|<n$, and they don’t give rise to any unordered pairs of the desired type. Clearly there is one of these ordered pairs for each $S\in\wp([n])^*$, so there are $2^n-2$ of them altogether. That leaves
$$4^n-2\cdot3^n+2^n-2^n+2=4^n-2\cdot3^n+2$$
ordered pairs $\langle S,T\rangle$ with $S\ne T$, and dividing this by $2$ yields the final answer.
I’ll leave the third part to you; you can use the same basic approach.
