Application of PIE Let $A_1, . . . , A_m$ be sets such that $|A_i| = n$ and $A_i \bigcap A_j$ = ∅ for $i \ne j$.
Find the number of sequences of elements from $\bigcup A_i$ which have the
following properties: (1) Every element from $\bigcup A_i$ appears exactly once
in the sequence and (2) For every $i = 1, . . . m$, the elements of $A_i$ are
not consecutive.
 A: The case where $n=2$ is indeed solvable with PIE.
Let $B_j$ be the sequences such that the two elements of $A_j$ are consecutive.

For each $k=1,\ldots,m$:$$\begin{align}|\text{Any intersection of $k$ of the $B$'s}|&=\left|B_1\cap\cdots\cap B_k\right|\\&=(2m-k)!\times 2^k\end{align}$$

because we can consider those $A_1,A_2,\ldots,A_k$ as blocks of 2 first and permute the blocks, and then multiply by 2 for each pair which can be reordered.


$$\left|\bigcup_j B_j\right|=\sum_{k=1}^m(-1)^{k-1}{m\choose k}\left|B_1\cap\cdots\cap B_k\right|$$
$$\text{Ans}=(2m)!-\left|\bigcup_j B_j\right|=\sum_{k=0}^m(-1)^k{m\choose k} 2^k(2m-k)!$$
On the linked question there is a formula for the case $m=3$ (that formula must be multiplied by $n!^3$. For verification, both formulae give $240$ when $n=2$ and $m=3$. But I think we have not found a general formula for this when $n,m$ are arbitrary.
A: Possible first step:
First choose the number of ways to set which indices are allocated to each set.
Then multiply by ${n!}^m$ to permute the elements of each set.
