A NOTE ON HIGHER-DIMENSIONAL MAGIC MATRICES

Peter J. Cameron^{†}, Christian Krattenthaler^{‡}, and Thomas W. Müller^{†}

† School of Mathematical Sciences, Queen Mary & Westfield College, University of London, Mile End Road, London E1 4NS, United Kingdom.

                       WWW: http://www.maths.qmw.ac.uk/~pjc/
                       WWW: http://www.maths.qmw.ac.uk/~twm/

‡ Fakultät für Mathematik, Universität Wien, Nordbergstraße 15, A-1090 Vienna, Austria.

                      WWW: http://www.mat.univie.ac.at/~kratt

Abstract. We provide exact and asymptotic formulae for the number of unrestricted, respectively indecomposable, d-dimensional matrices where the sum of all matrix entries with one coordinate fixed equals 2.

1. Introduction

We begin by recalling the notion of a magic matrix:^{1} this is a square matrix m = (m_{i,j})_{1≤i,j≤n} with non-negative integral entries such that all row and column sums are equal to the same non-negative integer. If this non-negative integer is s, then we call such a matrix s-magic. The enumeration of s-magic squares has a long history, going back at least to MacMahon [15, §404–419]. A good account of the enumerative theory of magic squares can be found in [18, Sec. 4.6], with many pointers to further literature. For more recent work, see for instance [4, 8].

Let [n] denote the standard n-set {1, 2, …, n}. There are two obvious ways of generalising s-magic matrices to higher dimensions: (G1) All line sums are equal. Given a positive integer d, a d-dimensional matrix

m : [n]^{d} → ℕ_{0} (where ℕ_{0} denotes the set of non-negative integers) is called s-magic if

∑_{ω_{i}∈[n]} m(ω_{1}, ω_{2}, …, ω_{d}) = s  (1.1)

for all fixed ω_{1}, …, ω_{i−1}, ω_{i+1}, …, ω_{d} ∈ [n], and all i = 1, 2, …, d.

2000 Mathematics Subject Classification. Primary 05A15; Secondary 05A16 05A19 05B15.

Key words and phrases. higher-dimensional magic matrices, labelled combinatorial structures, multisort species, exponential principle.

‡Research partially supported by the Austrian Science Foundation FWF, grants Z130-N13 and S9607-N13, the latter in the framework of the National Research Network “Analytic Combinatorics and Probabilistic Number Theory”.

1Strictly speaking, the correct term here would be “s-semi-magic,” since we do not require diagonals to sum up to the same number as the rows and columns, see e.g. [4]. However, here and in what follows we prefer the term “magic” for the sake of brevity.

(G2) All hyperplane sums are equal. Given a positive integer d, a d-dimensional matrix m : [n]^{d} → ℕ_{0} is called s-magic if

∑_{ω_{1},...,ω_{i−1},ω_{i+1},...,ω_{d}∈[n]} m(ω_{1}, ω_{2}, …, ω_{d}) = s  (1.2)

for all fixed ω_{i} ∈ [n], and all i = 1, 2, …, d. Generalisation (G1) appears already in the literature, see e.g. [1, 4]. For d = 3 and

s = 1, these objects are equivalent to Latin squares counted up to isotopy: the roles of rows, columns, and symbols of the corresponding Latin square are played by the first, second, and third coordinate, respectively, and the entry in position (ω_{1}, ω_{2}) of the Latin square is ω_{3} if and only if m(ω_{1}, ω_{2}, ω_{3}) = 1.

Generalisation (G2) appears in the literature (in more general form) as contingency tables in statistics; there are Markov chain methods for approximate counting of these, as well as some remarkable asymptotic estimates, see [11, 9, 13, 19, 10]. Indeed, these results suggest that the counting problem for (G2) is much easier than for (G1). (We are grateful to a referee for this information and the references.)

The present note focusses on the second generalisation. Hence, from now on, whenever we use the term “s-magic,” this is understood in the sense of (G2).

Counting higher-dimensional magic matrices is made more difficult (than the already difficult case of 2-dimensional magic matrices) by the fact that the analogue of Birkhoff’s Theorem (cf. [5] or [2, Corollary 8.40]; it says that any 2-dimensional s-magic matrix can be decomposed in a sum of permutation matrices, that is, 1-magic matrices) fails for them. For example, the 3-dimensional 2-magic matrix with ones in positions (1, 1, 1), (1, 2, 3), (2, 1, 2), (2, 2, 1), (3, 3, 2) and (3, 3, 3) is not the sum of two 1-magic matrices.

As we demonstrate in this note, it is however possible to count the 2-magic matrices of any dimension. Our first result is a recurrence relation for the number u_{n}(d) of indecomposable d-dimensional 2-magic matrices of size n (see Corollary 3 in Section 4). This recurrence is used in Proposition 4 to derive, for fixed d ≥ 3, an asymptotic formula for u_{n}(d). In order to go from indecomposable matrices to unrestricted ones, we observe that the d-dimensional 2-magic matrices may be viewed as a d-sort species in the sense of Joyal [14] which obeys the (d-sort) exponential principle. Let w_{n}(d) denote the number of all d-dimensional 2-magic matrices of size n. The exponential principle can then be applied to relate the numbers w_{n}(d) to the numbers u_{n}(d), see (3.5) (for d = 2) and (6.1) (for d ≥ 2). This relation is used in Theorem 5 to find, for fixed d ≥ 3, an asymptotic estimate for the numbers w_{n}(d) as well. Exact and asymptotic formulae for u_{n}(d) and w_{n}(d) for d = 2 are presented in Section 3. We remark in passing that a simple counting argument shows that the obvious interpretation of the matrices in Generalisation (G1) as a d-sort species does not satisfy the exponential principle, not even under the — in a sense — minimal axiomatics of [7].

2. Indecomposable 2-magic matrices and fixed-point-free involutions

A d-dimensional matrix m : [n]^{d} → ℕ_{0} is called decomposable, if there exist non-empty subsets B_{1}^{(1)}, B_{2}^{(1)}, B_{1}^{(2)}, B_{2}^{(2)}, …, B_{1}^{(d)}, B_{2}^{(d)} of [n] with

B_{1}^{(1)} ⨿ B_{2}^{(1)} = B_{1}^{(2)} ⨿ B_{2}^{(2)} = ⋯ = B_{1}^{(d)} ⨿ B_{2}^{(d)} = [n]

(⨿ denoting disjoint union) and

|B_{1}^{(1)}| = |B_{1}^{(2)}| = ⋯ = |B_{1}^{(d)}|,

such that m(ω_{1}, ω_{2}, …, ω_{d}) ≠ 0 only if either

(ω_{1}, ω_{2}, …, ω_{d}) ∈ B_{1}^{(1)} × B_{1}^{(2)} × ⋯ × B_{1}^{(d)}

or

(ω_{1}, ω_{2}, …, ω_{d}) ∈ B_{2}^{(1)} × B_{2}^{(2)} × ⋯ × B_{2}^{(d)},

otherwise it is called indecomposable.^{2} (In less formal language: there exist reorderings of the lines of the matrix such that m attains a block form.) The integer n is called the size of m.

Let u_{n}(d) denote the number of indecomposable d-dimensional 2-magic matrices of size n. Note that an indecomposable 2-magic matrix with an entry 2 has size 1. So it is enough to consider zero-one matrices.

The purpose of this section is to relate the numbers u_{n}(d) to another sequence of numbers v_{n}(d) counting certain tuples of fixed-point-free involutions on a set with 2n elements. More precisely, let

t_{1} = (1, 2)(3, 4) ⋯ (2n − 1, 2n)  (2.1)

be the standard fixed-point-free involution on the set [2n]. Then we define v_{n}(d) to be the number of choices of d−1 fixed-point-free involutions t_{2}, …, t_{d} on [2n] such that the group G = ⟨t_{1}, t_{2}, …, t_{d}⟩ generated by t_{1}, t_{2}, …, t_{d} is transitive. (For example, when n = 2, there are just three fixed-point-free involutions on {1, 2, 3, 4}, viz., (1, 2)(3, 4), (1, 3)(2, 4) and (1, 4)(2, 3), any two of which generate a transitive group. So v_{2}(d) = 3^{d−1} − 1.)

We have the following relation. Lemma 1. For all integers n, d > 1, we have

u_{n}(d) = 2^{−n}(n!)^{d−1}v_{n}(d).  (2.2)

Proof. Let m be an indecomposable d-dimensional 2-magic matrix of size n, where n > 1. Then m is a zero-one matrix, and it contains 2n entries equal to 1, the rest being zero. Number the positions of the 1’s in m from 1 to 2n in such a way that the positions with first coordinate j are numbers 2j − 1 and 2j for j = 1, …, n. (There are 2^{n} ways to do this, since for each j we can choose arbitrarily which of the two 1’s has number j − 1.) Then, for i = 1, …, d, let t_{i} be the fixed-point-free involution whose cycles are the pairs of numbers in {1, …, 2n} indexing positions of 1’s with the same i-th coordinate. Note that t_{1} is the involution defined in (2.1).

We claim that the subgroup G of S_{2n} generated by t_{1}, …, t_{d} is transitive if and only if the matrix m is indecomposable. For this, note that the 1’s whose labels belong to a cycle of t_{i} have the same i-th coordinate. So, if m is decomposable, and the 1 with label 1 belongs to B_{1}^{(1)} × ⋯ × B_{1}^{(d)}, then an easy induction shows that any 1 whose label is in the same orbit belongs to this set, so that G is intransitive. Conversely, if G is intransitive, then the coordinates of the 1’s whose labels belong to a G-orbit give rise to a decomposition of m.

So each matrix gives rise to 2^{n} such d-tuples of involutions. Thus, the number of pairs consisting of a matrix and a corresponding sequence of permutations is 2^{n} u_{n}(d).

For instance, the example of a matrix failing the analogue of Birkhoff’s Theorem given in the Introduction, with the entries numbered in the order given, produces the three permutations (1, 2)(3, 4)(5, 6), (1, 3)(2, 4)(5, 6) and (1, 4)(2, 6)(3, 5).

2We warn the reader that for d = 2 this does not reduce to the notion of decomposability of matrices in linear algebra since there rows and columns are reordered by the same permutation. Yet another definition of indecomposability occurs in [1].

Conversely, let t_{1}, …, t_{d} be fixed-point-free involutions on the set {1, …, 2n} which generate a transitive group, where t_{1} is the standard involution defined in (2.1). Number the cycles of each t_{i} from 1 to n such that the cycle (2j−1, 2j) of t_{1} has number j. (There are (n!)^{d−1} such numberings.) Now construct a d-dimensional matrix m as follows: for k = 1, …, 2n, if k lies in cycle number ω_{i} of t_{i}, then m(ω_{1}, ω_{2}, …, ω_{d}) = 1; all other entries are zero. Then m is 2-magic. Consequently, each sequence of permutations gives rise to (n!)^{d−1} matrices; and the number of pairs consisting of a matrix and a corresponding sequence of permutations equals (n!)^{d−1} v_{n}(d).

Comparing these two expressions, we obtain (2.2), as required. □

Remark. We note that u_{1}(d) = v_{1}(d) = 1 for all d. Hence, Formula (2.2) is false for n = 1.

3. Computation of u_{n}(2) and w_{n}(2)

The number w_{n}(2) of 2-dimensional 2-magic matrices of size n has been addressed earlier by Anand, Dumir and Gupta in [3, Sec. 8.1]. They found the generating function formula

∑_{n≥0} w_{n}(2)\frac{z^{n}}{(n!)^{2}} = (1 − z)^{−1/2}e^{z/2}.  (3.1)

This gives the explicit formula

w_{n}(2) = ∑_{k=0}^{n} \binom{2k}{k}\frac{(n!)^{2}}{2^{n−k}(n − k)!}.  (3.2)

Singularity analysis (cf. [12, Ch. VI]) applied to (3.1) then yields the asymptotic formula

w_{n}(2) = (n!)^{2}\sqrt{\frac{e}{πn}} (1 + O (\frac{1}{n})) ,  as n → ∞.  (3.3)

The number u_{n}(2) of indecomposable 2-dimensional 2-magic matrices of size n can also be computed explicitly. One way is to observe that, by Birkhoff’s Theorem (cf.

[5] or [2, Corollary 8.40]), a 2-magic matrix m is the sum of two permutation matrices, say p_{1} and p_{2}. If m is indecomposable, then the pair {p_{1}, p_{2}} is uniquely determined. Premultiplying by p_{1}^{−1}, we obtain a situation where p_{1} is the identity; indecomposability forces p_{2} to be the permutation matrix corresponding to a cyclic permutation, since a cycle of p_{2} not containing all points would provide a decomposition of m. So there are n! (n − 1)! choices for (p_{1}, p_{2}), and half this many choices for m (assuming, as we may, that n > 1). Note that this formula gives half the correct number for n = 1. So we have

u_{n}(2) = \begin{cases}1, & if n = 1, \\ \frac{1}{2}n! (n − 1)!, & if n > 1. \end{cases}  (3.4)

Alternatively, we may observe that 2-dimensional 2-magic matrices may be seen as a 2-sort species in the sense of Joyal [14] (see also [6, Def. 4 on p. 102]), with the row indices and the column indices forming the two sets on which the functor defining the species operates. Hence, by the exponential principle for 2-sort species [14, Prop. 20] (see also [6, Sec. 2.4]), we have

∑_{n≥0} w_{n}(2)\frac{z^{n}}{(n!)^{2}} = exp (∑_{n≥1} u_{n}(2)\frac{z^{n}}{(n!)^{2}} ) .  (3.5)

Combining this with (3.1), we find that

∑_{n≥1} u_{n}(2)\frac{z^{n}}{(n!)^{2}} = \frac{z}{2} + \frac{1}{2} log (\frac{1}{1 − z} ) .

Extraction of the coefficient of z^{n} then leads (again) to (3.4).

4. A recurrence relation for v_{n}(d)

In this section we prove a recurrence relation for the numbers v_{n}(d) (see Section 2 for their definition). By Lemma 1, this affords as well a recurrence relation for the numbers u_{n}(d).

Proposition 2. The numbers v_{n}(d) satisfy v_{1}(d) = 1 and

∑_{k=1}^{n} \binom{n − 1}{k − 1} ((2n − 2k − 1)!!)^{d−1} v_{k}(d) = ((2n − 1)!!)^{d−1}, n > 1.  (4.1)

Here, (2n − 1)!! = 1 · 3 · 5 ⋯ (2n − 1) is the product of the first n odd positive integers for n > 0, and, by convention, (−1)!! = 1.

Proof. Recall that (2n − 1)!! is the number of fixed-point-free involutions on a set of size 2n. (This is a special case of the general formula

\frac{n!}{∏_{i=1}^{n} i^{a_{i}}a_{i}!}

for the number of permutations in S_{n} with a_{i} cycles of length i for i = 1, …, n.) The number of choices of involutions t_{1}, t_{2}, …, t_{d}, where t_{1} is as in (2.1), such that the orbit containing 1 of the group they generate has size 2k is

\binom{n − 1}{k − 1} ((2n − 2k − 1)!!)^{d−1} v_{k}(d),

since we can choose in order

(i) k − 1 of the n − 1 cycles of t_{1} other than (1, 2) such that the elements not fixed by all of these k − 1 transpositions together with {1, 2} form the desired orbit, O say;

(ii) d − 1 fixed-point-free involutions on O which, together with the restriction of t_{1}

to O, generate a transitive group; (iii) d − 1 arbitrary fixed-point-free involutions on the complement of O.

Summing these values shows that the numbers v_{n}(d) satisfy the desired recurrence. □

Corollary 3. For all integers d > 1, the numbers u_{n}(d) satisfy u_{1}(d) = 1 and

((2n − 3)!!)^{d−1} + ∑_{k=2}^{n} \binom{n − 1}{k − 1} (\frac{(2n − 2k − 1)!!}{k!})^{d−1} 2^{k} u_{k}(d) = ((2n − 1)!!)^{d−1},

n > 1.

Remarks. (1) In the case d = 2, we have seen in (3.4) that u_{n}(2) = n!(n − 1)!/2 for n > 1, so that

v_{n}(2) = 2^{n−1} (n − 1)! = (2n − 2)!!,

d  n = 1 n = 2 n = 3 n = 4  n = 5  n = 6
2 indec  1  1  6  72  1440  43200
0-1  0  1  6  90  2040  67950
all  1  3  21  282  6210  202410
3 indec  1  8 900 359424 370828800 820150272000
0-1  0  8 900 366336 378028800 833156928000
all  1  12 1152 431424 427723200 920031955200

Table 1. Indecomposable, zero-one and arbitrary d-dimensional 2-magic matrices of size n

where (2n − 2)!! is the product of the even integers up to 2n − 2 (with 0!! = 1 by convention). Substituting this in (4.1), we have proved the somewhat curious looking identity

∑_{k=1}^{n} \binom{n − 1}{k − 1} (2n − 2k − 1)!! (2k − 2)!! = (2n − 1)!!

for n > 1.

We remark that this identity has an interpretation in terms of hypergeometric functions, for which we refer to [16], in particular, (1.7.7), Appendix (III.4). The left-hand side is

2^{n−1} (1/2)_{n−1} ·_{2}F_{1}[\begin{matrix}−n + 1, 1 \\ −n + \frac{1}{2} \end{matrix}; 1] ,

and the identity is an instance of the Chu–Vandermonde identity.

(2) For d > 2, we have not been able to solve the recurrence explicitly. However, it is easy to calculate terms in the sequences, and we can describe their asymptotics (see Sections 5 and 6).

Table 1 gives counts of all indecomposable matrices, all zero-one matrices, and all non-negative integer matrices, with dimension d and hyperplane sums 2. The sequences for d = 2 are numbers A010796, A001499, and A000681 in the On-Line Encyclopedia of Integer Sequences [17]. For d = 3, they are A112578, A112579 and A112580.

5. Asymptotics of the numbers u_{n}(d)

This section provides the preparation for the determination of the asymptotics of the numbers w_{n}(d) for d ≥ 3 in the next section. Our goal here is to establish an asymptotic estimate for the sequence u_{n}(d) with fixed d ≥ 3.

Proposition 4. For fixed d ≥ 3, we have

u_{n}(d) ∼ 2^{−dn}((2n)!)^{d−1}, as n → ∞.

Proof. By Lemma 1, we have u_{n}(d) = (n!)^{d−1}v_{n}(d)/2^{n} for n > 1, so it suffices to show that

v_{n}(d) ∼ ((2n − 1)!!)^{d−1}.

We will use the estimates

\sqrt{2(n + 1)} ≤ \frac{2^{n} n!}{(2n − 1)!!} ≤ 2\sqrt{n}

for n ≥ 1. With c_{n} = 2^{n}n!/(2n − 1)!!, we have c_{n+1}/c_{n} = (2n + 2)/(2n + 1), and both inequalities are easily proved by induction. From these estimates, we obtain the inequality

\frac{(2n − 1)!!}{(2k − 1)!! (2n − 2k − 1)!!} ≥ \binom{n}{k} (\frac{(k + 1)(n − k + 1)}{n})^{1/2} .  (5.1)

To simplify our formulae, we denote the left-hand side of this inequality by \begin{matrix}( \\ ( & {n \atop k} & ) \\ ) \end{matrix}.

Now, by Proposition 4.1, v_{n}(d) satisfies the recurrence

v_{n}(d) = ((2n − 1)!!)^{d−1} − ∑_{k=1}^{n−1} \binom{n − 1}{k − 1}((2n − 2k − 1)!!)^{d−1}v_{k}(d), n > 1.

Clearly v_{n}(d) ≤ ((2n − 1)!!)^{d−1}. We show that v_{n}(d) ≥ ((2n − 1)!!)^{d−1}(1 − O(1/n)), an estimate which, in view of the above recurrence, follows if we can show that

L := ∑_{k=1}^{n−1} \binom{n − 1}{k − 1} \begin{matrix}( \\ ( & {n \atop k} & ) \\ ) \end{matrix}^{−(d−1)} = O (\frac{1}{n}) .

Using (5.1), we have

L ≤ \frac{n}{(2n − 1)^{d−1}} + ∑_{k=2}^{n−2} \binom{n − 1}{k − 1}\binom{n}{k}^{−(d−1)} (\frac{n}{(k + 1)(n − k + 1)})^{(d−1)/2}

≤ \frac{n}{(2n − 1)^{d−1}} + ∑_{k=2}^{n−2} \frac{k}{n}\binom{n}{k}^{−(d−2)} (\frac{n}{(k + 1)(n − k + 1)})^{(d−1)/2} .

Since k/n < 1, n/(k + 1)(n − k + 1) < 1/2, and \binom{n}{k} ≥ \binom{n}{2}, and there are fewer than n − 1 terms in the sum, the second term is at most

n^{−(d−2)}(n − 1)^{−(d−3)} · 2^{d−2} · 2^{−(d−1)/2} ≤ \frac{1}{n},

as required. □

6. Asymptotics of the numbers w_{n}(d)

Recall that w_{n}(d) and u_{n}(d) are the numbers of unrestricted, respectively indecomposable, d-dimensional 2-magic matrices of size n. Using the exponential principle, we can relate the sequence (w_{n}(d))_{n≥0} to the sequence (u_{n}(d))_{n≥0} for each fixed d, see (6.1) below. This relationship combined with the fact that the sequence (u_{n}(d))_{n≥0} grows sufficiently rapidly for d ≥ 3 (Proposition 4 says that it grows very roughly like ((2n)!)^{d−1}) allows us to conclude that, for d ≥ 3, w_{n}(d) and u_{n}(d) grow at the same rate.

Theorem 5. For fixed d ≥ 3, we have

w_{n}(d) ∼ 2^{−nd}((2n)!)^{d−1}, as n → ∞.

Proof. Generalising the argument at the end of Section 3, we observe that d-dimensional 2-magic matrices may be seen as a d-sort species in the sense of Joyal [14] (see also [6, Def. 4 on p. 102]), with the row indices and the column indices forming the two set on which the functor defining the species operates. Hence, by the exponential principle for d-sort species [14, Prop. 20] (see also [6, Sec. 2.4]), we have

∑_{n≥0} w_{n}(d)\frac{z^{n}}{(n!)^{d}} = exp (∑_{n≥1} u_{n}(d)\frac{z^{n}}{(n!)^{d}} ) .

If we now differentiate both sides of this equation with respect to z and subsequently multiply both sides by z, then we obtain

∑_{n≥0} nw_{n}(d)\frac{z^{n}}{(n!)^{d}} = (∑_{n≥1} nu_{n}(d)\frac{z^{n}}{(n!)^{d}} ) exp (∑_{n≥1} u_{n}(d)\frac{z^{n}}{(n!)^{d}} )

= (∑_{n≥1} nu_{n}(d)\frac{z^{n}}{(n!)^{d}} ) (∑_{n≥0} w_{n}(d)\frac{z^{n}}{(n!)^{d}} ) .

Comparison of coefficients of z^{n} on both sides then leads to the relation

w_{n}(d) = u_{n}(d) + ∑_{k=1}^{n−1} \frac{k}{n}\binom{n}{k}^{d}u_{k}(d)w_{n−k}(d).  (6.1)

As we said at the beginning of this section, our goal is to show that w_{n}(d) grows asymptotically at the same rate as u_{n}(d). Hence, putting w_{n}(d) = u_{n}(d) + x_{n}(d), we have to show that x_{n}(d) = o(u_{n}(d)). We assume inductively that

x_{m}(d) ≤ 2^{−m}((2m − 1)!!)^{d−1}(m!)^{d−1}

for all m between 2 and n − 1; the induction starts since we have x_{1}(d) = x_{2}(d) = 0. Now, using the inductive hypothesis with the recurrence relation (6.1), we have

\frac{x_{n}(d)2^{n}}{((2n − 1)!!)^{d−1}(n!)^{d−1}} ≤ 2 ∑_{k=1}^{n−1} \frac{k}{n}\binom{n}{k}^{d} \begin{matrix}( \\ ( & {n \atop k} & ) \\ ) \end{matrix}^{−(d−1)} \binom{n}{k}^{−(d−1)}

≤ 2 ∑_{k=1}^{n−1} \frac{k}{n}\binom{n}{k}^{−(d−2)} (\frac{n}{(k + 1)(n − k + 1)})^{(d−1)/2}

≤ (2^{1/2}n)^{−(d−3)},

which establishes the result if d > 3. For d = 3, this inequality gives the inductive step (that is, that the left-hand side is at most 1); the fact that it is o(1) for large n is proved by an argument like that in the proof of Proposition 4. □

Acknowledgment. The authors are grateful to a referee for some helpful information on contingency tables.

References

[1] M. Ahmed, J. A. De Loera and R. Hemmecke, Polyhedral cones of magic cubes and squares, in: Discrete and Computational Geometry. The Goodman–Pollack Festschrift (B. Aronov, S. Basu, J. Pach and M. Sharir, eds.), Springer–Verlag, Berlin, Algorithms Comb. 25, 2003, pp. 25–41.

[2] M. Aigner, Combinatorial Theory, Springer–Verlag, Berlin, 1979.

[3] H. Anand, V. C. Dumir, and H. Gupta, A combinatorial distribution problem, Duke Math. J. 33 (1966), 757–769.

[4] M. Beck, M. Cohen, J. Cuomo and P. Gribelyuk, The number of “magic” squares, cubes, and hypercubes, Amer. Math. Monthly 110 (2003), 707–717.

[5] G. Birkhoff, Tres observaciones sobre el álgebra lineal, Univ. Nac. Tucum’an Rev. Ser. A 5 (1946), 147–150.

[6] F. Bergeron, G. Labelle, and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge University Press, Cambridge, 1998.

[7] P. J. Cameron, C. Krattenthaler and T. W. Müller, Decomposable functors and the exponential principle, II, Séminaire Lotharingien Combin. 61A (2011), Article B61Am, 38 pages.

[8] J. A. De Loera, F. Liu and R. Yoshida, A generating function for all semi-magic squares and the volume of the Birkhoff polytope, J. Algebraic Combin. 30 (2009), 113–139.

[9] J. A. De Loera and S. Onn, The complexity of three-way statistical tables, SIAM J. Comput. 33 (2004), 819–836 (electronic).

[10] J. A. De Loera and S. Onn, All linear and integer programs are slim 3-way transportation programs, SIAM J. Optim. 17 (2006), 806–821 (electronic).

[11] P. Diaconis and A. Gangolli, Rectangular arrays with fixed margins, in Discrete Probability and Algorithms (D. Aldous, P. Diaconis, J. Spencer, and J. M. Steele (eds.), IMA Vol. Math. Appl., Springer, New York, pp.15–41.

[12] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, Cambridge, 2009.

[13] S. Hoşten and S. Sullivant, Gröbner bases and polyhedral geometry of reducible and cyclic models, J. Combinatorial Theory Ser. A 100 (2002), 277–301.

[14] A. Joyal, Une théorie combinatoire des séries formelles, Adv. in Math. 42 (1981), 1–82.

[15] P. A. MacMahon, Combinatory Analysis, vol. 2, Cambridge University Press, 1916; reprinted by Chelsea, New York, 1960.

[16] L. J. Slater, Generalized Hypergeometric Functions, Cambridge University Press, Cambridge, 1966.

[17] N. J. A. Sloane (editor), The On-Line Encyclopedia of Integer Sequences, available at

http://www.research.att.com:80/~njas/sequences/.

[18] R. P. Stanley, Enumerative Combinatorics, vol. 1, Wadsworth & Brooks/Cole, Pacific Grove, California, 1986; reprinted by Cambridge University Press, Cambridge, 1998.

[19] B. Sturmfels, Gröbner Bases and Convex Polytopes, University Lecture Series 8, Amer. Math. Soc., Providence, RI, 1996.

School of Mathematical Sciences, Queen Mary & Westfield College, University of London, Mile End Road, London E1 4NS, United Kingdom.

WWW: http://www.maths.qmw.ac.uk/~pjc/, http://www.maths.qmw.ac.uk/~twm/.

Fakultät für Mathematik, Universität Wien, Nordbergstraße 15, A-1090 Vienna,

Austria. WWW: http://www.mat.univie.ac.at/~kratt.