How many nonnegative integer matrices of size $N$ have all row and column sums equal to $D$?

Question

Given the positive integer $N$ and $D$, generate all the non-negative integer matrices which satisfy

1. matrix dimension is $N\times N$;
2. sum of each row elements equals to $D$
3. sum of each column elements equals to $D$

when $N\leq 5, D\leq 8$, there are how many matrices in each $\langle N,D\rangle $.

Answer 1

^{I post a summary of comments, since nobody wrote an answer.}

---

Gerry Myerson:

This isn't so easy. There are research papers on the number of such matrices. For the given parameters, might be simplest just to bung it on a computer and count the matrices. This looks useful: Counting semi-magic squares from drvinceknight.blogspot.com. I did find a couple of other papers that should help:

MR0332532 (48 #10859), Ehrhart, Eugène, Sur les carrés magiques, C. R. Acad. Sci. Paris Sér. A-B 277 (1973), A651–A654. Author's summary: "Le nombre de carrés magiques de côté $c$ et de somme $n$ est un polynôme en $n$ de degré $(c−1)^2$.

MR0317970 (47 #6519), Stanley, Richard P, Linear homogeneous Diophantine equations and magic labelings of graphs, Duke Math. J. 40 (1973), 607–632.

The Stanley paper says, Let $H_n(r)$ denote the number of squares of side $n$, with nonnegative integral entries in each of the $n^2$ cells into which the square can be divided, such that every line-sum in the direction of an edge is $r$. The reviewer noted that $H_n(r)$ is a polynomial in $r$ of degree $d=(n-1)^2$ with rational coefficients, satisfying the relations $H_n(−t)=0$, $t=1,2,\dots,n−1$, and $H_n(r)=(−1)^dH_n(−n−r)$, $r\ge0$. If you can calculate the answers for some small values of $N,D$ then the Online Encyclopedia of Integer Sequences might have your answers.

Two more papers:

MR2023999 (2004k:05009), Beck, Matthias; Cohen, Moshe; Cuomo, Jessica; Gribelyuk, Paul, The number of "magic'' squares, cubes, and hypercubes, Amer. Math. Monthly 110 (2003), no. 8, 707–717.

MR2519852 (2010h:52017), De Loera, J. A.; Liu, F.; Yoshida, R., A generating function for all semi-magic squares and the volume of the Birkhoff polytope, J. Algebraic Combin. 30 (2009), no. 1, 113–139.

OEIS sequences oeis.org/A122751 and oeis.org/A002817 might be helpful.

---

user2468587:

I found this paper: The Ehrhart polynomial of the Birkhoff polytope, it told me how to get $H_n(t)$, it's really useful. In the same website, Ehrhart polynomials for $n =1, \dots , 9$ are given, that's amazing.