A037302 - OEIS

A037302

Normalized volume of Birkhoff polytope of n X n doubly-stochastic square matrices. If the volume is v(n), then a(n) = ((n-1)^2)! * v(n) / n^(n-1).

1, 1, 3, 352, 4718075, 14666561365176, 17832560768358341943028, 12816077964079346687829905128694016, 7658969897501574748537755050756794492337074203099, 5091038988117504946842559205930853037841762820367901333706255223000

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

COMMENTS

The Birkhoff polytope is an (n-1)^2-dimensional polytope in n^2-dimensional space; its vertices are the n! permutation matrices.

Is a(n) divisible by n^2 for all n>=4? - Dean Hickerson, Nov 27 2002

LINKS

Table of n, a(n) for n=1..10.

Matthias Beck and Dennis Pixton, The Ehrhart polynomial of the Birkhoff polytope

Matthias Beck, Stanley's Major Contributions to Ehrhart Theory, arXiv preprint arXiv:1407.0255 [math.CO], 2014.

Matthias Beck and Dennis Pixton, The Ehrhart polynomial of the Birkhoff polytope, arXiv:math/0202267 [math.CO], 2002-2005.

Matthias Beck and Dennis Pixton, The Ehrhart polynomial of the Birkhoff polytope, Discrete Comput. Geom. 30 (2003), no. 4, 623-637.

Petter Brändén, Jonathan Leake, and Igor Pak, Lower bounds for contingency tables via Lorentzian polynomials, arXiv:2008.05907 [math.CO], 2020.

C. S. Chan and D. P. Robbins, On the volume of the polytope of doubly stochastic matrices, arXiv:math/9806076 [math.CO], 1998.

C. S. Chan and D. P. Robbins, On the volume of the polytope of doubly stochastic matrices, Exper. Math. 8 (1999), 291-300.

Jesús A. De Loera, Fu Liu, and Ruriko Yoshida, A generating function for all semi-magic squares and the volume of the Birkhoff polytope, J. Algebraic Combin. 30 (2009), no. 1, 113-139.

R. P. Stanley, Decompositions of rational convex polytopes, Annals of Discrete Math. 6 (1980), 333-342.

FORMULA

a(n) = ((n-1)^2)!*A078524(n)/(n^(n-1)*A078525(n)). - Andrew Howroyd, Apr 11 2020

EXAMPLE

a(2)=1: The polytope of 2 X 2 matrices is the line segment from (1,0;0,1) to (0,1;1,0), with length v(2)=2, so a(2) = 1! * 2 / 2^1 = 1.

CROSSREFS

Numerator and denominator of v(n) are in A078524 and A078525.

Row sums of A259473.

Cf. A257493.

Sequence in context: A376748 A039515 A209426 * A341229 A157591 A005336

Adjacent sequences: A037299 A037300 A037301 * A037303 A037304 A037305

KEYWORD

nonn,hard,nice

AUTHOR

Günter M. Ziegler (ziegler(AT)math.tu-berlin.de)

EXTENSIONS

v(9) computed by Matthias Beck (matthias(AT)math.binghamton.edu) and Dennis Pixton (dennis(AT)math.binghamton.edu), Feb 25 2002

Edited by Dean Hickerson, Nov 27 2002

a(10) is based on a calculation of v(10) by Matthias Beck (matthias(AT)math.binghamton.edu) and Dennis Pixton (dennis(AT)math.binghamton.edu) from Mar 13 2002 to May 18 2003

STATUS

approved