On the volume of a certain polytope. (English) Zbl 0960.05004

Summary: Let \(n\geq 2\) be an integer and consider the set \(T_n\) of \(n\times n\) permutation matrices \(\pi\) for which \(\pi_{ij}= 0\) for \(j\geq i+2\). We study the convex hull \(P_n\) of \(T_n\), a polytope of dimension \(\left(\begin{smallmatrix} n\\ 2\end{smallmatrix}\right)\). We provide evidence for several conjectures involving \(P_n\), including Conjecture 1: Let \(v_n\) denote the minimum volume of a simplex with vertices in the affine lattice spanned by \(T_n\). Then the volume of \(P_n\) is \(v_n\) times the product \[ \prod^{n-2}_{i= 0}{1\over i+1}{2i\choose i} \] of the first \(n-1\) Catalan numbers. We also give a related result on the Ehrhart polynomial of \(P_n\).
Editor’s note: After this paper was circulated, Doron Zeilberger [Proof of a conjecture of Chan, Robbins, and Yuen, ETNA, Electron. Trans. Numer. Anal. 9, 147-148, electronic only (1999; Zbl 0941.05006)] proved Conjecture 1, using the authors’ reduction of the original problem to a conjectural combinatorial identity, and sketched the proofs of two others. The problems and methodology presented here gain even further interest thereby.


05A15 Exact enumeration problems, generating functions
52B20 Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry)
52A38 Length, area, volume and convex sets (aspects of convex geometry)
52A40 Inequalities and extremum problems involving convexity in convex geometry
05A19 Combinatorial identities, bijective combinatorics


Zbl 0941.05006
Full Text: DOI arXiv EuDML


[1] Billera L. J., Formal power series and algebraic combinatorics (New Brunswick, NJ, 1994) pp 1– (1996)
[2] DOI: 10.1080/10586458.1999.10504406 · Zbl 0951.05015
[3] DOI: 10.1007/978-1-4612-0801-3_3
[4] Ehrhart E., Polynômes arithmétiques et méthode des polyedres en combinatoire (1977) · Zbl 0337.10019
[5] Hibi T., Algebraic combinatorics on convex polytopes (1992) · Zbl 0772.52008
[6] Postnikov, A. and Stanley, R. P. 1998. [Postnikov and Stanley 1998], Private communication
[7] DOI: 10.1016/S0167-5060(08)70717-9 · Zbl 0812.52012
[8] Zeilberger D., ”Proof of a conjecture of Chan, Robbins and Yuen” (1998) · Zbl 0941.05006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.