How to prove there are $\frac{3^n-1}{2}$ couples $A,B \in \mathcal{P}([n])$ such that $A \cup B = [n]$, $A \neq B$. Consider the unordered couple of sets $A,B \in \mathcal{P}([n])$ such that $A \cup B = [n]$, $A \neq B$. I would like to prove that the number of such couples is:
$$\frac{3^n-1}{2}$$
I derived that expression by enumerating the solutions for the first values of $n$, and also considering the sum of the number of those couples for all different values of $n$ over $\mathcal{P}([m])$:
$${2^m \choose 2} = \sum_{n=0}^m {m \choose n}\frac{3^n-1}{2}$$
(this is easy to show using the binomial expansion).
I have checked OEIS A003462 where they count the number of couples $A,B \in \mathcal{P}([n])$ with $A \cap B = \emptyset$ and $A \neq \emptyset$ or $B \neq \emptyset$, with the same $\frac{3^n-1}{2}$ result, but it's not the same thing and I was not able to adapt that reasoning.
 A: You seem to treat $A,B$ as unordered... that for instance $A=\{1,2\}$ and $B=\{3,4,5,6\}$ to be the same result than $A=\{3,4,5,6\}$ and $B=\{1,2\}$.  For the time being let us go with the other interpretation that these are distinct outcomes as it makes the math far simpler.
Now... for each element $x$ in $[n]=\{1,2,3,\dots,n\}$ for it to be that $A\cup B=[n]$ as well as $A\subseteq [n]$ and $B\subseteq [n]$, exactly one of the following must be true:

*

*$x\in A$ and $x\notin B$

*$x\in B$ and $x\notin A$

*$x\in A$ and $x\in B$
For each element choose which of these three it is.  Apply rule of product.  That gives $3\times 3\times 3\times \cdots \times 3 = 3^n$ different choices of $A,B$.
This included in it however the possibility that we answered $x\in A$ and $x\in B$ for every $x$ which would have meant that $A=B$.  You explicitly wanted to avoid this case, so subtracting $1$ will correct the count.
Finally, you seemed to be wanting to talk about unlabled pairs of sets rather than labeled pairs of sets.  Dividing by $2$ corrects that aspect of the count.  (Note that every outcome was counted twice.  The only outcome that might have been counted only once was the case where $A=B$ but that was already removed)
This gives, as expected, the final result of:
$$\frac{3^n-1}{2}$$
A: Alternatively, using what you found in OEIS, take $\{A,B\}$ with $A\cap B=\emptyset,$ $A,B\neq \emptyset$ and consider $C=[n]\setminus (A\cup B)$ counted by the expression. Now, consider mapping that set to $\{A\cup C,B\cup C\},$ check that the properties that you required are satisfied and, moreover, this mapping is a bijection. So both problems have the same number of solutions.
A: Note that $A\cup B=(A\setminus B)\cup(A\cap B)\cup(B\setminus A)$ is a disjoint union. Assign to each unordered couple $\{A,B\}$ the $n$-length ternary string $(a_1,a_2,\ldots,a_n)$ defined by $$a_j=\begin{cases}0\quad\text{if $a_j\in A\setminus B$}\\1\quad\text{if $a_j\in A\cap B$}\\2\quad\text{if $a_j\in B\setminus A$}\end{cases}$$
