A generating function for all semi-magic squares and the volume of the Birkhoff polytope (Q735404)

The famous Birkhoff polytope \(B_n\) is the convex polytope of \(n\times n\) doubly stochastic matrices, with vertices at the permutation matrices. The Ehrhart polynomial of \(B_n\) is a polynomial in a variable \(t\) that records the number of lattice points within the dilation \(tB_n\). The authors find exact formulae for the coefficients of the Ehrhart polynomial, including the leading coefficient which gives the volume of \(B_n\). The formulae involve sums over all permutations of \(n\) and over all arborescences (rooted trees) on \(n\) nodes and hence seem impractical to evaluate except for very small \(n\). However, \textit{E. R. Canfield} and \textit{B. D. McKay} [Online J. Anal. Comb. 4, Article 2, 4 p., electronic only (2009; Zbl 1193.15034)] have recently found asymptotic formulae which yield practical approximations for large \(n\). The authors' formulae are corollaries of a multivariate rational generating function they find for the \(n\times n\) non-negative integer matrices with row and column sums all equal to \(t\). Such matrices are sometimes called semi-magic squares. The coefficients of the Ehrhart polynomial of \(B_n\) are found after expressing this generating function in terms of Todd polynomials. To demonstrate that their methods have wider applicability, the authors finish by explicitly computing the Ehrhart polynomials of a facet of \(B_n\) for \(3\leq n\leq 6\) and of the Chan-Robbins-Yuen polytope \(CRY_n\) for \(3\leq n\leq 7\).