Ehrhart $h^*$-polynomials of the permutohedra

edit · history · discussion · files · short url · combinatorics discrete geometry polynomial

Polynomials

$n$

$h^*_{\Pi_n}(z)$

z^2 + 4*z + 1

6*z^3 + 55*z^2 + 34*z + 1

51*z^4 + 1026*z^3 + 1636*z^2 + 286*z + 1

560*z^5 + 23921*z^4 + 83006*z^3 + 45106*z^2 + 2926*z + 1

7575*z^6 + 668998*z^5 + 4498719*z^4 + 5548544*z^3 + 1340249*z^2 + 36954*z + 1

122052*z^7 + 21906879*z^6 + 264518108*z^5 + 627262259*z^4 + 362149964*z^3 + 44684557*z^2 + 561940*z + 1

2285353*z^8 + 825216976*z^7 + 16989077620*z^6 + 70073863360*z^5 + 78693513406*z^4 + 24572159728*z^3 + 1683167140*z^2 + 10026496*z + 1

10:

48803904*z^9 + 35253011809*z^8 + 1193466428494*z^7 + 8014563347824*z^6 + 15555261799474*z^5 + 9640088562046*z^4 + 1777757854066*z^3 + 71354583856*z^2 + 205608526*z + 1

11:

1171278945*z^10 + 1687574155356*z^9 + 91556249332813*z^8 + 955734714031120*z^7 + 2970904539689362*z^6 + 3195311257292584*z^5 + 1199423040660274*z^4 + 138517441805392*z^3 + 3379825414285*z^2 + 4767440668*z + 1

12:

31220505800*z^11 + 89603092983119*z^10 + 7646863577076692*z^9 + 119960832373015701*z^8 + 566534492445459000*z^7 + 971598197061692454*z^6 + 639212471071554480*z^5 + 154665063744248058*z^4 + 11657923950148224*z^3 + 177442346676475*z^2 + 123373203196*z + 1

13:

915350812299*z^12 + 5230578875812018*z^11 + 692772934578766848*z^10 + 15922911570352267430*z^9 + 109934943067930285683*z^8 + 283671515000910847188*z^7 + 298120473614814086328*z^6 + 128140092402152054316*z^5 + 20890139562469184385*z^4 + 1059367806720441882*z^3 + 10245220568790728*z^2 + 3525630110094*z + 1

14:

29281681800384*z^13 + 333145759391195505*z^12 + 67812001643922568514*z^11 + 2239441408506715141574*z^10 + 21955616723370024827978*z^9 + 81726528463474599834975*z^8 + 128837619476886885707988*z^7 + 88953520613673592823220*z^6 + 26177492566400074085460*z^5 + 2971432944241714485807*z^4 + 103728217896858907626*z^3 + 645892925853771142*z^2 + 110284283006626*z + 1

15:

1015074250155511*z^14 + 22998789873734328046*z^13 + 7143773983610324327011*z^12 + 333849257853653472581096*z^11 + 4543950978080107110430151*z^10 + 23636735584689868736507078*z^9 + 53419477854752785747359483*z^8 + 55374527829921465280720128*z^7 + 26387848082474293069464333*z^6 + 5505241366000186891083098*z^5 + 446205213453446128176161*z^4 + 10913283133766989379096*z^3 + 44173541010565927861*z^2 + 3748357699560946*z + 1

16:

37909738774479600*z^15 + 1711036984166426174911*z^14 + 806875104551695275551872*z^13 + 52723115532245419156291879*z^12 + 978534023477269157087428592*z^11 + 6939490651095774045563400971*z^10 + 21730968070914350497362919808*z^9 + 32225304746680174890978243171*z^8 + 23135249428516241183524918992*z^7 + 7893536507245843112337863901*z^6 + 1199231032560078518510064128*z^5 + 70789421511120418779404981*z^4 + 1229900748976693296702032*z^3 + 3258548904291176162329*z^2 + 137557910094840832*z + 1

17:

1517587042234033425*z^16 + 136491787558987553907552*z^15 + 97358924268486881675448616*z^14 + 8810346973912226074951498816*z^13 + 219777761374206542949299966188*z^12 + 2083432999375042306558467428192*z^11 + 8803965226607493910539940995512*z^10 + 18013435370505292765700047535168*z^9 + 18509380392066600853722920149878*z^8 + 9564069163913888459392683699744*z^7 + 2403313640201422981115905975896*z^6 + 271583850843184750049866343360*z^5 + 11861573605544953208807285516*z^4 + 147998471150969479816621856*z^3 + 257946941475768579959368*z^2 + 5421179050350334912*z + 1

18:

64830903253553212928*z^17 + 11622996405037657616240321*z^16 + 12507283407406496493999865742*z^15 + 1555555196728574897664766832060*z^14 + 51542954890979322707466924721082*z^13 + 642789764568689356565390517121220*z^12 + 3588888437766174882074324881381118*z^11 + 9851696926075219521832133752769732*z^10 + 13945617057945362232311717795278010*z^9 + 10337070935580233671181007133322806*z^8 + 3959753394949149582634141073660986*z^7 + 749396132790686165154514041367876*z^6 + 64074506587138304549943358964350*z^5 + 2097321364307297350781517773380*z^4 + 18956497326052230558243765562*z^3 + 21813131993648535927648316*z^2 + 228359487335194570510*z + 1

19:

2944016994706445303937*z^18 + 1052417093898657521289778804*z^17 + 1705266877461409890033363403353*z^16 + 289707519421349428654909207367648*z^15 + 12627398546892264145636329631202164*z^14 + 204457092800430055901101144871585328*z^13 + 1482671358955446774918297729704976452*z^12 + 5340111382422713071373041562768809120*z^11 + 10111208326852983913587316542601834350*z^10 + 10328039481487825900064310466908471992*z^9 + 5695819177839511687063696876018066478*z^8 + 1655792043847462855666820750311132704*z^7 + 240308438528019564216073218223732996*z^6 + 15765192016049859056314229994825776*z^5 + 390829673384135283561077142440244*z^4 + 2576726603424233035064724104032*z^3 + 1962661102879835121270279065*z^2 + 10239206473040881277556*z + 1

20:

141619391130850396785504*z^19 + 100971263547197346233318012559*z^18 + 246028161333127146651009354105524*z^17 + 56814706713390375265259602079460329*z^16 + 3231298133342888896148950821563680424*z^15 + 67187857306314076699406859303090259388*z^14 + 623935476927071978314537363590129890648*z^13 + 2895586797607921127465682549860470586228*z^12 + 7163948738916051032749312814439460303688*z^11 + 9776791203640521970116530506604317891778*z^10 + 7441860271636098260036305296635919859712*z^9 + 3128895371526679238225992969691652863902*z^8 + 703451945028131318315577736338234468472*z^7 + 79463509519929651156499540503511528012*z^6 + 4046656736882255670076247717628949672*z^5 + 76642930287544070677565708682235396*z^4 + 370640554181902844532737339241016*z^3 + 187223668801661815776195594151*z^2 + 486909744862576654283596*z + 1

Definition

For a positive integer $n$, $\Pi_n=\operatorname{conv}\{(\sigma(1),\ldots,\sigma(n)):\sigma\in S_n\}$ is the $(n-1)$-dimensional permutohedron. This table stores the Ehrhart $h^*$-polynomial $h^*_{\Pi_n}(z)$.

Parameters

$n$

— order ($n$ is a positive integer)

Formulas

(1)

$\sum_{t\geq0}L_{\Pi_n}(t)z^t=h^*_{\Pi_n}(z)/(1-z)^n$.

(2)

$h^*_{\Pi_n}(1)=(n-1)!\,n^{n-2}$ is the normalized volume of $\Pi_n$.

Comments

(3)

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 series, and hence does not change $h^*_{\Pi_n}(z)$.

(4)

The omitted cases $\Pi_1$ and $\Pi_2$ both have $h^*$-polynomial $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()
Zz = PolynomialRing(QQ, 'z'); z = Zz.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}))
h = (sum(L(j) * z ** j for j in range(n)) * (1 - z) ** n).truncate(n)
h

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

[2]

Wikipedia: Permutohedron

[3]

Wikipedia: Ehrhart polynomial

Similar tables

Ehrhart polynomials of the permutohedra — holds $L_{\Pi_n}(t)$ 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 that table and a reader holding the Ehrhart-series numerator should use this one

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 $h^*_{\Pi_n}(z)$ for every $n$ with $3\leq n\leq20$; the range starts after the trivial cases $n=1,2$ and stops with $h^*_{\Pi_{20}}(z)$ already over 800 characters)

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 forms $L_{\Pi_n}(t)=\sum_k f_{n,k}t^k$ and then converts this polynomial to $h^*_{\Pi_n}(z)$ by the exact Ehrhart-series transform that (1) states. 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$. For every stored $n$, $h^*_{\Pi_n}(1)$ equalled $(n-1)!n^{n-2}$.