The combinatorial problem is as follows:
Let $H_3(r)$ denote the number of $3\times 3$ matrices with nonnegative integer
entries such that each row and each column sum to $r$.
Show that $$H_3(r) = \binom{r+5}{5} – \binom{r+2}{5}$$
Theorem. (Birkhoff-von Neumann). Every $n \times n$ magic square with row and column sum $r$ is a sum of $r$ permutation matrices (of size $n \times n)$.
Using this theorem and the fact that the number of $3\times 3$ permutation matrices is $3! = 6$. I find that if there are no "repeated" cases, the number is $\binom{r+5}{5}$. But there are, for example, $r = 3$:
$$\begin{aligned}
&\left[\begin{array}{lll}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{array}\right]+\left[\begin{array}{lll}
0 & 1 & 0 \\
0 & 0 & 1 \\
1 & 0 & 0
\end{array}\right]+\left[\begin{array}{lll}
0 & 0 & 1 \\
1 & 0 & 0 \\
0 & 1 & 0
\end{array}\right]=\\
&\left[\begin{array}{lll}
1 & 0 & 0 \\
0 & 0 & 1 \\
0 & 1 & 0
\end{array}\right]+\left[\begin{array}{lll}
0 & 0 & 1 \\
0 & 1 & 0 \\
1 & 0 & 0
\end{array}\right]+\left[\begin{array}{lll}
0 & 1 & 0 \\
1 & 0 & 0 \\
0 & 0 & 1
\end{array}\right]=\left[\begin{array}{lll}
1 & 1 & 1 \\
1 & 1 & 1 \\
1 & 1 & 1
\end{array}\right]
\end{aligned}$$
Question: How to prove that the number of superfluous matrices is exactly $\binom{r+2}{5}$ for a general $r$ so that we can subtract it safely from $\binom{r+5}{5}$?
I tried to think of it but failed. Any help is appreciated.
Best Answer
Let $$A=\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}\qquad B=\begin{bmatrix}0&1&0\\0&0&1\\1&0&0\end{bmatrix}\qquad C=\begin{bmatrix}0&0&1\\1&0&0\\0&1&0\end{bmatrix}$$ $$D=\begin{bmatrix}0&0&1\\0&1&0\\1&0&0\end{bmatrix}\qquad E=\begin{bmatrix}0&1&0\\1&0&0\\0&0&1\end{bmatrix}\qquad F=\begin{bmatrix}1&0&0\\0&0&1\\0&1&0\end{bmatrix}$$ By the theorem, every magic square with nonnegative entries and row/column sum $r$ can be expressed as $$aA+bB+cC+dD+eE+fF$$ where $a+b+c+d+e+f=r$. But we have $$A+B+C=D+E+F$$ so to canonicalise the representation of a magic square, we will require that $d,e,f$ cannot all be positive (at least one has to be zero). This is the only deduplication we can make.
The number of ordered tuples of nonnegative integers $(a,b,c,d,e,f)$ that sum to $r$ and have $d,e,f\ge1$ is the same as the number of tuples $(a,b,c,d',e',f')$ that sum to $r-3$ where $d',e',f'\ge0$ like $a,b,c$. This count can be determined by stars and bars as $\binom{r+2}5$, and is the number of superfluous representations that we need to subtract from $\binom{r+5}5$ to get the correct final answer.