Number of derangement on $(1, 1, 2, 2, 3, 3, 4, 4)$

Question

How many 8-tuples of $[4]^8=\{1,2,3,4\}^8$ are there s.t. every number in $[4]$ appears exactly twice, and $i$ never appears on the $i$th place for all $i\in[4]$?

There are $8!/16$ different tuples in $[4]^8$. I think the number of them with at least one fixed point is exactly like the number of derangements in $S_8$, but couldn't find a proof for it. Am I right? How shall I continue?

Answer 1

As you say, there are $\frac{8!}{16}$ tuples $p$ to consider. We must exclude those that have $p_i=i$ for some $1\leq i\leq4$. There are $4$ ways to choose $i$ and then $\frac{7!}{8}$ ways to permute the remaining numbers, giving $$\frac{8!}{16}-\frac{7!}{8}$$ However, any tuple with $p_i=i$ for two values of $i$ has been subtracted twice, so these must be added back in. There are $\binom 42=6$ ways to choose the two values of $i$, and then $\frac{6!}{4}$ ways to permute the remaining elements, giving $$\frac{8!}{16}-\frac{7!}{8}+\frac{6!}{4}$$ What about permutations with three values of $i$ fixed? These have been subtracted $3$ times, then added back in $\binom 32=3$, so we need to subtract them again. After that, we need to consider the tuples that start $1,2,3,4$. They will have been subtracted $4$ times, added back in $\binom 42$ times and subtracted $\binom 43$ times, so we must add them back in.

I leave it to you to finish up. (I get $864$ as the final answer.)

Answer 2

In general suppose that you have a set of "errors" you want to avoid.

You want to count the number of configurations without any errors, however it seems hard.

If it is possible to count the number of configurations that satisfy a subset of the errors then you can obtain a formula for the number of configurations with no errors.

The formula is:

$\sum\limits_{S} (-1)^{|S|} f(S)$ where $S$ ranges over all possible subsets of errors and $f(S)$ is the number of configurations with at least those errors (note that when $S$ is the empty set we get the total number of configurations, disregarding errors).

In our case there are $4$ possible errors, so there would be $2^4$ possibilites for $S$, however the only thing that matters is if $S$ has size $0,1,2,3$ or $4$. So we can make our sum only range over the possible size of $S$.

We have that $f(S)$ is equal to $(8-|S|)!/2^{4-S}$ (because we must have that there is an $i$ in the position $i$ for $|S|$ values).

So our formula turns into $\sum\limits_{i=0}^4 \binom{4}{i}(-1)^i\frac{(8-i)!}{2^{4-i}} = 2520 - 2520 + 1080 - 240 + 24 = 864$

c++ brute force checker:

#include <bits/stdc++.h>
using namespace std;

int a[9] = {0,1,1,2,2,3,3,4,4};

int check(){
        for(int i=1;i<=4;i++){
                if( a[i] == i ) return 0;
        }
        return 1;
}

int main(){
        int start=1;
        int res = 0;
        while( start || next_permutation(a+1,a+9)){
                start = 0;
                if( check() ) res++;
        }
        cout << res << "\n";
}

Answer 3

This is inclusion/exclusion, so the total is $$\sum_{k=0}^8(-1)^k A(k)(8-k)!$$
$k$ is the number of matches. Let it be made from $p$ pairs and $q$ single digits.
$$A(k) = \sum_{2p+q=k}{4\choose p,q}B(p,q)$$ A pair can match in two ways (1a,1b) and (1b,1a), and a single digit can match in four ways (1a,x),(1b,x),(x,1a),(x,1b), so $$B(p,q)=2^p4^q$$ Finally, divide everything by $2^4$ because we can't distinguish 1a from 1b

$$\frac{1}{2^N}\sum_{k=0}^{2N}(-1)^k\sum_{2p+q=k}{N\choose p,q}2^p4^q(2N-k)!$$ I think that comes to 297 for $N=4$, from the sequence A000459