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

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$.

• 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: drvinceknight.blogspot.com.au/2013/05/… Jul 1 '14 at 11:29
• Have you had a look? Jul 2 '14 at 12:32
• Sorry, i am late. you know the damned GFW, i can't get into the link, can you copy that or show me another one. Jul 2 '14 at 12:37
• It's a bit long to copy. Can you send email to the guy who wrote it, KnightVA at cardiff.ac.ukq (but leave off the q at the end)? Jul 2 '14 at 12:52
• Thanks, i have bypassed the GFW, i have read the blog, i got this: 1. the matrix that satisfies these condition is called semi magic matrix. 2. |SMS(3,r)|=C(44,r)+C(34,r)+C(24,r) 3. |SMS(n,2)|=taylor(f(x),x,0,n).coeff(x^n)*(factorial(n)^2), f(x) = e ^ (x / 2)/(sqrt(1 - x)) But when n,r are others, what's the result? Jul 2 '14 at 15:59

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 Birkhoﬀ 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.