Tuples of sets $A_1, ... , A_k \in \mathcal{P}([n])$ with $\bigcup_{i=1}^{k}{A_i}=[n]$ and $A_i \neq A_j$, $1 \le i \lt j \le k$ To generalize this question I would like to count how many tuples of sets $A_1, ... , A_k \in \mathcal{P}([n])$ with $\bigcup_{i=1}^{k}{A_i}=[n]$ and $A_i \neq A_j$, for any $i,j$ such that $1 \le i \lt j \le k$, are there.
The case $k=2$ has been solved in the linked question and the result is $\frac{3^n-1}{2!}$.
The case $k=3$ can be stated as $\frac{7^n-1}{3!}-\frac{3^n-1}{2!}$ and a computer test confirms the result.
For case $k = 4$ I would have expected something like $\frac{15^n-1}{4!}-\frac{7^n-1}{3!}+\frac{3^n-1}{2!}$, but the first addendum is not an integer. The values computed (hopefully correctly) for $n=1,2,3,4,5,6$ are $0,1,67,1546,27550,445531$.
To complete with computing data, the case $k = 5$ gives $0,0,56,4144,180096,6480656$, for $k = 6$ we have $0,0,28,7896,866432,69656776$, for $k = 7$: $0,0,8,11408,3308736,601192496$.
Any hint? If possible, for the general case, but especially for $k = 4$. Thank you.

I will prove the following formula, valid for all $m\in \mathbb N$:
$$
\#\text{ sets of $m$ distinct sets whose union is $[n]$}=\frac1{k!}\sum_{i=1}^k(-1)^{k-i}{k\brack i}(2^i-1)^n
$$
Let $X$ be the set of ordered $k$-tuplets of sets whose union is $[n]$. This is different than what we actually want in two ways; first of all, this includes $k$-tuplets with repeated sets, and secondly, this distinguishes the order of the $k$-tuples. To deal with the first problem, we will use an alternating summation where the "bad" tuples with two ore more repeated entries cancel out. Once these are gone, we fix the order issue by dividing by $k!$.
In more detail, let $S_k$ be the set of permutations of $[k]$. Any such permutation $\pi$ can be applied to an element $x$ of $X$ to permute the indices of $x$. Now, consider the set of ordered pairs
$$
(x,\pi)\quad\text{   such that   }\quad x \text{ is unchanged by $\pi$}
$$
I claim that
$$
\sum_{(x,\pi)}\text{sign}(\pi)=\#\text{ of ordered tuples in $X$ whose entries are distinct}
$$
This follows from the following sign-reversing involution. Given an ordered pair $(x,\pi)$ where $x$ is unchanged by $\pi$, and where $x$ has at least two identical entries, let $(i,j)$ be the lexicographically first pair of indices for which the entries of $x$ at those indices are equal. Then the ordered pair matched to $(x,\pi)$ is $(x,(i\;\;j)\pi)$. This changes the sign of $\pi$, so the two ordered pairs matched together will cancel each other out in the above summation. All that remains are ordered pairs $(x,\pi)$ where $x$ has all distinct entries. Therefore, we have canceled out the bad tuples, and can account for the ordering by dividing by $k!$:
\begin{align}
\#\text{ sets of $m$ distinct sets whose union is $[n]$}
  &=\frac1{k!}\sum_{(x,\pi)}\text{sign}(\pi)
\\&=\frac1{k!}\sum_{\pi\in S_k}\text{sign}(\pi)\cdot \#\{x:x\text{ is unchanged by $\pi$}\}
\end{align}
You finally conclude in two steps:

*

*For a given $\pi$, being unchanged by $\pi$ means that you can freely choose one of the entries of $x$ for each cycle of $\pi$, so $\#\{x:x\text{ is unchanged by $\pi$}\}$ is just $(2^i-1)^n$, where $i$ is the number of cycles of $\pi$.


*You then group all permutations together with the same number of cycles, leading to the Stirling numbers of the first kind appearing.
