Inclusion–exclusion: Matrices

Question

Let $A$ be an $n\times n$ matrix that contains all the numbers $1,2,\ldots,n^2$ (each one appears one time). Count the number of $n \times n$ matrices $B$ that contain all the numbers $1,2,\ldots,n^2$ and don't have any row identical to some row in $A$, and don't have any column identical to some column in $A$.

I marked $R_i=\{\text{all the matrices with row }i\text{ identical to some row in }A\}$, $C_i=\{\text{all the matrices with column }i\text{ identical to some column in }A\}$, and said that

$$\left|\bigcap_{i\in I} R_i\right|=\left|\bigcap_{i\in I} C_i\right|={n \choose |I|}\big(n^2-|I|n\big)!|I|!$$

and

$$\left|\bigcap_{i\in I} R_i\cap\bigcap_{j\in J} C_j\right|=\left(n^2-(|I|+|J|)n+|I||J|\right)!\;.$$

By the Inclusion–exclusion principle, I got this answer:

$$(n^2)!+\sum_{k=1}^{2n}(-1)^k\left[2{n \choose k}^2k!(n^2-kn)!+ \sum_{i=1}^{k-1}{n \choose i}{n \choose k-i}\big(n^2-kn+i(k-i)\big)!\right]\;.$$

Is this correct? Is there another way? Thanks

Answer 1

Here is a slightly different approach. For the nodes of the poset underlying inclusion-exclusion we will use pairs $(S,T)$ with $S\subseteq [n]$ and $T\subseteq [n]$ so that $(S,T)\ne (\emptyset, \emptyset)$ where $S$ gives the rows that agree with some row of $A$ and $T$ the columns. Now there are several possibilities here. Note that the rows and columns of $A$ are all mutually distinct. If $T$ is empty but not $S$ we choose the $|S|$ rows and may permute them. Same if $S$ is empty but not $T.$ If neither is empty there is only one possible assignment namely an exact match of the corresponding rows and colums from $A.$ Note that in the later case we have used $n(|S|+|T|)- |S|\times|T|$ elements. We thus get by inclusion-exclusion

$$\sum_{S\ne\emptyset} (-1)^{|S|} {n\choose |S|}|S|! (n^2-|S|n)! + \sum_{T\ne\emptyset} (-1)^{|S|} {n\choose |T|}|T|! (n^2-|T|n)! \\ + \sum_{S\ne\emptyset, T\ne \emptyset} (-1)^{|S|+|T|} (n^2 - n(|S|+|T|) + |S|\times|T|)!.$$

Now at this point we need to compute the weight on a configuration that has exactly $p$ rows from $A$ and $q$ columns. With neither of these empty we get

$$\sum_{p'=1}^p {p\choose p'} (-1)^{p'} + \sum_{q'=1}^q {q\choose q'} (-1)^{q'} + \sum_{p'=1}^p \sum_{q'=1}^q {p\choose p'} {q\choose q'} (-1)^{p'+q'} \\ = -1-1+1 = -1.$$

With $T$ empty (same with $S$ empty)

$$\sum_{p'=1}^p {p\choose p'} (-1)^{p'} = -1.$$

We have verified that the weight is $-1$ in all cases and hence the answer is given by

$$(n^2)! + 2\sum_{k=1}^n {n\choose k}^2 (-1)^k \times k! \times (n^2-kn)! \\ + \sum_{k=1}^n \sum_{j=1}^n {n\choose k} {n\choose j} (-1)^{k+j} (n^2-n(k+j)+kj)!.$$

This will produce the sequence

$$0, 13, 350314, 20907473410813, 15511088399276664432001386, \\ 371993307691696427796897697438711091311473, \\ 608281863896576961368925279207011528484342192328937893038299066, \ldots $$

The Maple code for this was as follows (warning, total enumeration only practicable for $n=2$ and $n=3$)

with(combinat);

Q :=
proc(n)
option remember;
local S, T, res, all, p, q;

    res := 0; all := powerset(n);

    for S in all do
        for T in all do
            p := nops(S); q := nops(T);

            if p = 0 and q = 0 then
                next;
            elif q = 0 then
                res := res +
                (-1)^p*binomial(n,p)*p!*(n^2-p*n)!;
            elif p = 0 then
                res := res +
                (-1)^q*binomial(n,q)*q!*(n^2-q*n)!;
            else
                res := res +
                (-1)^(p+q)*(n^2-((p+q)*n-p*q))!;
            fi;
        od;
    od;

    ((n^2)!) + res;
end;

X :=
proc(n)
option remember;
local perm, res, pos, rows, cols, srcrows, srccols;

    res := 0;

    srcrows :=
    {seq([seq(p*n+q+1, q=0..n-1)], p=0..n-1)};

    srccols :=
    {seq([seq(p*n+q+1, p=0..n-1)], q=0..n-1)};

    perm := firstperm(n^2);

    while type(perm, `list`) do

        rows :=
        {seq([seq(perm[p*n+q+1], q=0..n-1)], p=0..n-1)};

        cols :=
        {seq([seq(perm[p*n+q+1], p=0..n-1)], q=0..n-1)};

        if nops(rows intersect srcrows) = 0 and
        nops(cols intersect srccols) = 0 then
            res := res + 1;
        fi;

        perm := nextperm(perm);
    od;

    res;
end;

P :=
proc(n)
    (n^2)! + 2*add(binomial(n,k)^2*(-1)^k*k!*(n^2-k*n)!,
                   k=1..n)
    + add(add((-1)^(k+j)*binomial(n,k)*binomial(n,j)
              *(n^2-n*(k+j)+k*j)!, j=1..n),
          k=1..n);
end;

Answer 2

Since all of my mistakes and your one mistake have been corrected in the meantime, there's not much left to say here except that I believe the count is now correct.