## Thursday, January 12, 2017

### Number of 2 by 2 matrices with all elements in {0,1,..,n} and its permanent equal to the sum of all elements

OEIS sequence A280934 is defined as: $a(n) =$ the number of 2 by 2 matrices with all elements integers in the set $\{0,1,..,n\}$ and its permanent is equal to the sum of all elements.

Consider a 2 by 2 matrix $\left(\begin{array}{cc}a & c \\ d & b\end{array}\right)$. The sum of all elements equal to the permanent is written as $a+b+c+d = ab+cd$. This can be rewritten as $(a-1)(b-1) + (c-1)(d-1) = 2$. In other words, $a(n) =$ the number of 2 by 2 matrices with all elements integers in the set $\{-1,..,n-1\}$ and its permanent is equal to 2. We will consider this alternative formulation in the rest of this note. Suppose $n > 3$ and at least one of members of the matrix has value $n-1$. Let us count how many of such matrices has permanent 2, i.e. $ab+cd = 2$.

First consider the case $a = n-1$. If  $b = -1$, then $cd = n+1$. Note that $c \neq 1$ and $c \neq n+1$ since $-1\leq c,d\leq n-1$. Since $n> 3$, any nontrivial factor of $n+1$ is less than $n-1$. Thus setting $c>1$ equal to any nontrivial factor of $n+1$ and $d = (n+1)/c$ will result in a matrix with permanent 2. Thus there are $\tau(n+1)-2$ such matrices. Here $\tau(n)$ denotes the number of divisors of $n$. If $b = 0$, then $cd = 2$ and there are 2 cases: $(c,d) = (1,2)$ and $(c,d) = (2,1)$. If $b=1$, then $cd = 3-n$ and there are 2 cases as well: $(c,d) = (-1,n-3)$ and $(c,d) = (n-3,-1)$. Note that $cd \geq 1-n$ since $-1\leq c,d\leq n-1$. This means that if $b > 1$ then $ab+cd \geq n-1 > 2$. Thus we have a total of $\tau(n+1)+2$ cases. Note that in all cases, exactly one element of the matrix is of value $n-1$.

By symmetry, the same analysis applies to $b=n-1$, $c=n-1$ and $d=n-1$ as well. Since in all the cases only one element of the matrix is of value $n-1$, there is no double counting. Thus the number of matrices with at least one member equal to $n-1$ and permanent 2 is $4\tau(n+1)+8$. This implies the following recurrence relation for $a(n)$:

$$a(n) = a(n-1) + 4\tau(n+1)+8 \quad\mbox{for}\quad n> 3$$.