8 places 4 labels $\{1,2,3,4\}$
the original order 1,1,2,2,3,3,4,4
how many ways to order such that no label will have the original position.
solution:
we will use inclusion exclusion principle , we will find all ways such that they are in the original places
A1- we have $6!/(2!2!2!)$
and for the same logic we get : $A_i$ = $4\choose1$$6!/(2!2!2!)$
$A_(1\cap2)$= $4!/(2!2!)$ and by the same logic we get : $A_(i\cap j)$= $4\choose2$$4!/(2!2!)$, $i\neq j$
$A_(1\cap2\cap3)$=$2!/(2!)$ and by the same logic we get: $A_(i\cap j\cap k)$=$4\choose3$$2!/(2!)$ where i,j,K differ from one another
for 4 of them we have 1 option\
we conclude : $|U|-(A_i)+(A_(i\cap j))-(A_(i\cap j \cap k )) +…= $$8!/(2!2!2!2!)$–$4\choose1$$6!/(2!2!2!)$+$4\choose2$$4!/(2!2!)$–$4\choose3$$2!/(2!)$+1
is it Correct?
Best Answer
This is a special case of this problem.
You can compute the result by counting the number of placements of 8 rooks on the $8\times 8$ board with four $2\times 2$ squares on the diagonal removed and then dividing the result by $(2!)^4$.
First find the rook polynomial of the complement of this board, which consists of four independent $2\times 2$ squares, hence the polynomial is $$(1+4x+x^2)^4 = 16 x^8 + 128 x^7 + 416 x^6 + 704 x^5 + 664 x^4 + 352 x^3 + 104 x^2 + 16 x + 1$$
Now apply the inclusion-exclusion formula for the number of rooks on the original board $$\sum_{k} (-1)^k(8-k)!r_k,$$ where $r_k$ is the coefficient of $x^k$ in the above polynomial (it is fully explained in the answer I linked), to get $$1\cdot 8!-16\cdot 7!+104\cdot 6!-352\cdot5!+664\cdot 4!-704\cdot 3!+416\cdot 2!-128\cdot 1!+16\cdot 0! = 4752$$
The number of rook placements is $(2!)^4$-times bigger than the number you seek because the rooks are labeled by their row numbers (so, e.g. the placement in which the rooks in rows 1 and 2 are in the columns 3 and 4, respectively, is different from the placement where these rooks are in columns 4 and 3, but they both correspond to a single permutation ##11####).
So the final result is $4752/(2!)^4 = 297$.