NumberDB$^\beta$ Advanced search Tags Tables Help Login
Ehrhart polynomials of the permutohedra
edit · history · discussion · files · short url · combinatorics discrete geometry polynomial
Polynomials
$n$ 
$L_{\Pi_n}(t)$
3:
3*t^2 + 3*t + 1
4:
16*t^3 + 15*t^2 + 6*t + 1
5:
125*t^4 + 110*t^3 + 45*t^2 + 10*t + 1
6:
1296*t^5 + 1080*t^4 + 435*t^3 + 105*t^2 + 15*t + 1
7:
16807*t^6 + 13377*t^5 + 5250*t^4 + 1295*t^3 + 210*t^2 + 21*t + 1
8:
262144*t^7 + 200704*t^6 + 76608*t^5 + 18865*t^4 + 3220*t^3 + 378*t^2 + 28*t + 1
9:
4782969*t^8 + 3542940*t^7 + 1316574*t^6 + 320544*t^5 + 55755*t^4 + 7056*t^3 + 630*t^2 + 36*t + 1
10:
100000000*t^9 + 72000000*t^8 + 26100000*t^7 + 6258000*t^6 + 1092105*t^5 + 143325*t^4 + 14070*t^3 + 990*t^2 + 45*t + 1
11:
2357947691*t^10 + 1656409535*t^9 + 587030895*t^8 + 138437310*t^7 + 24048255*t^6 + 3207897*t^5 + 331485*t^4 + 26070*t^3 + 1485*t^2 + 55*t + 1
12:
61917364224*t^11 + 42568187904*t^10 + 14780620800*t^9 + 3428282880*t^8 + 590412240*t^7 + 79170399*t^6 + 8411634*t^5 + 705375*t^4 + 45540*t^3 + 2145*t^2 + 66*t + 1
13:
1792160394037*t^12 + 1208912928522*t^11 + 412069511139*t^10 + 94059655690*t^9 + 16027796070*t^8 + 2146836978*t^7 + 231354123*t^6 + 20151846*t^5 + 1402830*t^4 + 75790*t^3 + 3003*t^2 + 78*t + 1
14:
56693912375296*t^13 + 37603105146880*t^12 + 12604714327296*t^11 + 2833936641536*t^10 + 477411574640*t^9 + 63641666088*t^8 + 6899167275*t^7 + 614506893*t^6 + 44837793*t^5 + 2637635*t^4 + 121121*t^3 + 4095*t^2 + 91*t + 1
15:
1946195068359375*t^14 + 1271514111328125*t^13 + 419801484375000*t^12 + 93055995703125*t^11 + 15495339234375*t^10 + 2051450651250*t^9 + 222569372025*t^8 + 20073049425*t^7 + 1508782275*t^6 + 93783690*t^5 + 4729725*t^4 + 187005*t^3 + 5460*t^2 + 105*t + 1
16:
72057594037927936*t^15 + 46443371157258240*t^14 + 15123782440058880*t^13 + 3308477732618240*t^12 + 544652100894720*t^11 + 71530799628288*t^10 + 7741879425280*t^9 + 702495121185*t^8 + 53789959080*t^7 + 3467403940*t^6 + 186113928*t^5 + 8143590*t^4 + 280280*t^3 + 7140*t^2 + 120*t + 1
17:
2862423051509815793*t^16 + 1822442358054692408*t^15 + 586049426860524300*t^14 + 126642365068676240*t^13 + 20619226977792170*t^12 + 2684845732979592*t^11 + 289297137120992*t^10 + 26300384653400*t^9 + 2036262886515*t^8 + 134463763720*t^7 + 7530498976*t^6 + 352975896*t^5 + 13536250*t^4 + 409360*t^3 + 9180*t^2 + 136*t + 1
18:
121439531096594251776*t^17 + 76461926986744528896*t^16 + 24307340986526810112*t^15 + 5193315990469140480*t^14 + 836670560604157440*t^13 + 107992630908804096*t^12 + 11570476164077376*t^11 + 1050925859466912*t^10 + 81857181636945*t^9 + 5491244257785*t^8 + 316658880252*t^7 + 15572652732*t^6 + 643493214*t^5 + 21816270*t^4 + 584460*t^3 + 11628*t^2 + 153*t + 1
19:
5480386857784802185939*t^18 + 3415753581721829617275*t^17 + 1074495780444130114509*t^16 + 227160198500847385884*t^15 + 36232055577668433690*t^14 + 4636019437800293718*t^13 + 493535471267193810*t^12 + 44702294310795888*t^11 + 3490649483399793*t^10 + 236503301350745*t^9 + 13915427604507*t^8 + 707994733680*t^7 + 30850128582*t^6 + 1132991622*t^5 + 34215390*t^4 + 817836*t^3 + 14535*t^2 + 171*t + 1
20:
262144000000000000000000*t^19 + 161873920000000000000000*t^18 + 50429952000000000000000*t^17 + 10557603840000000000000*t^16 + 1668081561600000000000*t^15 + 211623646464000000000*t^14 + 22376155441920000000*t^13 + 2018603140944000000*t^12 + 157637380245930000*t^11 + 10742799174110575*t^10 + 640777121734750*t^9 + 33400119451725*t^8 + 1512302602200*t^7 + 58838794350*t^6 + 1934143380*t^5 + 52374450*t^4 + 1124040*t^3 + 17955*t^2 + 190*t + 1
Definition
For a positive integer $n$, $\Pi_n=\operatorname{conv}\{(\sigma(1),\ldots,\sigma(n)):\sigma\in S_n\}\subset\mathbb{R}^n$ is the $(n-1)$-dimensional permutohedron. This table stores the Ehrhart polynomial $L_{\Pi_n}(t)=\#(t\Pi_n\cap\mathbb{Z}^n)$.
Parameters
$n$
—   order ($n$ is a positive integer)
Formulas
(1)
$L_{\Pi_n}(t)=\sum_{k=0}^{n-1}f_{n,k}t^k$, where $f_{n,k}$ is the number of forests on $n$ labelled vertices with $k$ edges.
(2)
$L_{\Pi_n}(t)=t^{n-1}T_{K_n}(1+1/t,1)$, where $T_{K_n}$ is the Tutte polynomial of the complete graph.
(3)
The leading coefficient of $L_{\Pi_n}(t)$ is $n^{n-2}$, the number of labelled trees on $n$ vertices that [6] lists.
(4)
$L_{\Pi_n}(1)$ is the number of forests on $n$ labelled vertices.
(5)
$\sum_{t\geq0}L_{\Pi_n}(t)z^t=h^*_{\Pi_n}(z)/(1-z)^n$.
Comments
(6)
Up to translation by $(1,\ldots,1)$, $\Pi_n$ is the graphical zonotope of $K_n$ [2], the Minkowski sum of the segments $[e_i,e_j]$ for $1\leq i<j\leq n$. An integer translation does not change the Ehrhart polynomial. Stanley [1] showed that the Ehrhart polynomial of a graphical zonotope counts the forests of its graph by their number of edges, giving (1) for $K_n$.
(7)
The omitted cases $\Pi_1$ and $\Pi_2$ have Ehrhart polynomials $1$ and $t+1$.
(8)
OEIS A105599 [4] lists the Ehrhart-polynomial coefficient rows, and OEIS A001858 [5] lists the totals $L_{\Pi_n}(1)$.
Programs
(P1)
Sage
from sage.graphs.graph_generators import graphs
from sage.rings.rational_field import QQ
from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing

n = 5
Tt = PolynomialRing(QQ, 't'); t = Tt.gen()
T = graphs.CompleteGraph(n).tutte_polynomial(); x, y = T.parent().gens()
L = Tt(t ** (n - 1) * T.subs({x: 1 + 1/t, y: 1}))
L
References
[1]
Richard P. Stanley, A zonotope associated with graphical degree sequences, in Applied Geometry and Discrete Mathematics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 4, American Mathematical Society, 1991, 555-570.
Links
Similar tables
Ehrhart $h^*$-polynomials of the permutohedra —   holds $h^*_{\Pi_n}(z)$ for the same permutohedra; the two are connected by $\sum_{t\geq0}L_{\Pi_n}(t)z^t=h^*_{\Pi_n}(z)/(1-z)^n$, so a reader holding the counting polynomial should use this table and a reader holding the Ehrhart-series numerator should use that one
Tutte polynomials of connected graphs —   holds $T_{K_n}(x,y)$ for $n\leq7$, and $L_{\Pi_n}(t)=t^{n-1}T_{K_n}(1+1/t,1)$
Chromatic polynomials of connected graphs —   holds $P(K_n,x)$ for $n\leq7$; $|P(K_n,-1)|=n!$ counts the acyclic orientations of $K_n$, which correspond to the vertices of $\Pi_n$
Ehrhart polynomials of the hypersimplices —   holds the Ehrhart polynomials of the non-simplex hypersimplices that occur, up to symmetry, in the Minkowski sum $\Pi_n=\Delta(1,n)+\cdots+\Delta(n-1,n)+(1,\ldots,1)$
Data properties
Entries are of type: rational polynomial
How well the digits are known: exact
Table is complete: no (it holds $L_{\Pi_n}(t)$ for every $n$ with $3\leq n\leq20$; the range starts after the trivial cases $n=1,2$)
How they were obtained:

The generator computes the forest numbers $f_{n,k}$ by an exact recurrence on the tree component containing a distinguished vertex, using Cayley's formula for the number of labelled trees on each component. It then forms $L_{\Pi_n}(t)=\sum_k f_{n,k}t^k$. Direct lattice-point counts in $t\Pi_n$ agreed with $L_{\Pi_n}(t)$ for $3\leq n\leq5$ and $0\leq t\leq n$.

more

The specialization in (2) agreed with the stored Tutte polynomials of $K_1,\ldots,K_7$. For every stored $n$, the leading coefficient was $n^{n-2}$.



API Python package Skill for AI Privacy Legal notice Source
Data licensed CC BY-SA 4.0. No tracking, no analytics, essential cookies only.