Fabian Arevalo

OEIS A333331 · enumerative combinatorics · session 2026-08-29

Counting the lattice points of the parking-function polytope

A proof that the count equals the number of loop-graphs whose every piece carries exactly one cycle, settling both standing conjectures in the OEIS entry and the enumeration question of Selig's sandpile paper; plus the polytope's Ehrhart polynomial, and certified terms to n = 40 where eight were known.
29 August 2026 · AI-assisted (Claude), see disclosure · code, data and certificates

Start here, no maths required

A one-way street has n parking spots in a row. n cars drive in, one at a time. Each driver has a favourite spot, drives straight to it, and parks there if it is free; if not, they carry on forwards and take the next free spot. If they run off the end of the street, everybody loses. A list of favourites where everybody parks is called a parking function.

For three spots there are sixteen such lists. Now think of each list as a point in space: the list (1, 3, 2) is the point with coordinates 1, 3, 2. Sixteen points. Stretch a skin around them, the smallest convex shape containing them all, and ask a different question: how many points with whole-number coordinates are inside that shape? Not sixteen. Seventeen. There is exactly one extra, the point (2, 2, 2), sitting dead in the middle of a face, and it is not a parking function: if all three drivers want the middle spot, the third one runs off the end.

Counting those points, for every n, is the problem. Richard Stanley put it in the encyclopedia of integer sequences in 2020 with eight terms. It sat there. Two people later added guesses about what the answer should be, and nobody proved either. The figure below is the shape at n = 3, sliced so you can see all seventeen points.

The seventeen lattice points of conv(PF3), computed live from Stanley's inequalities. The polytope is three-dimensional, so it is drawn one slice at a time: each slice fixes the coordinate sum, and within a slice the three coordinates are plotted on a triangular grid. Filled dots are parking functions. The single ringed dot, (2, 2, 2) in the Σ = 6 slice, is in the hull but is not a parking function: it is the seventeenth point. Nothing here is stored. The figure tests every point of the cube against the facet inequalities each time it draws, and the totals it reports, 17 and 16, are the ones the repository's exact dynamic program returns for n = 3.

What this note adds

Two guesses were attached to the sequence. Andrew Howroyd (January 2024) proposed a formula for the generating function. Jamie Wiseman (March 2024) proposed that the count is really counting graphs of a certain kind. Both were guesses fitted against the same eight terms, and separately, Thomas Selig's 2024 sandpile paper asked to count what turns out to be the same objects and left it open. This session proved all of it.

  1. The graphs are the right answer. The number of lattice points equals the number of ways to draw n edges on n labelled dots, allowing an edge from a dot to itself, so that every connected piece contains exactly one loop or cycle. That is Wiseman's guess, proved, and it gives Howroyd's formula as a consequence.
  2. It answers Selig's question too. The recurrent states of the stochastic sandpile on the complete graph are counted by the same number, including the growth rate he asked for: about 0.7465 × nn−1/4.
  3. Eight known terms became forty computed ones. The ninth term, 167,341,283, had never been calculated by anyone; it had only been predicted by the unproved formula. All forty terms were computed twice, from two sides that the theorem says must agree, and they do.
  4. The shape's full counting polynomial, not just its points. Blow the polytope up by a whole-number factor and the point count is a polynomial in that factor. This note writes it down, which answers a question left open in the 2022 paper that set up the facet description.

Everything below is the technical version. The second figure is the dictionary between points and graphs, and it will check the theorem for you out to n = 7.

AbstractSummary of results

Let Pn = conv(PFn) ⊂ Rn be the convex hull of the parking functions of length n, and a(n) = #(Pn ∩ Zn), which is OEIS A333331 (entry by Richard Stanley, March 2020, eight terms). Two conjectures stand in that entry: Howroyd (January 2024), that the exponential generating function is exp(−½log(1−T) + T/2 − T²/4) with T the tree function; and Wiseman (March 2024), that a(n) counts choosable loop-graphs on [n] with n edges.

Theorem A (PROVED). a(n) equals the number u(n) of loop-graphs on [n] with n edges in which every connected component contains exactly one cycle, loops counting as cycles of length 1 and parallel edges not allowed; hence the exponential generating function is exp(T + ∑k≥3Tk/2k) = exp(−½log(1−T) + T/2 − T²/4). This proves both A333331 conjectures and answers the open enumeration question of Selig, Electron. J. Combin. 31(3) (2024), §6, on the recurrent states of the stochastic sandpile on Kn0, including its asymptotic half: a(n) ~ C·nn−1/4 with C = e1/4√(2π)/(21/4Γ(1/4)) = 0.7464918…

Theorem B (PROVED). The Ehrhart polynomial of Pn is i(Pn,t) = ∑M ts(M)(t(t+1)/2)d(M), summed over sparse multiforests M, with closed generating function (1−τ)−1/2exp((2−t)τ/2t − τ²/4t), τ = T(tx). This answers Amanbayeva–Wang §6(b). The sum-form is a specialization of Liu–Thawinrak (December 2025), Corollary 7.6; what is new here is the identification of the index set and the closed form.

CERTIFIED. a(1) through a(40) by exact dynamic programming over Stanley's facet description, the first independent computation of any term past a(8); all eight published terms reproduced, and Howroyd's generating function, previously supported by those eight fitted terms, matched exactly through n = 40.

Section 1The polytope, and the two guesses

A parking function of length n is a vector c ∈ [n]n whose weakly increasing rearrangement b satisfies bi ≤ i. There are (n+1)n−1 of them. Stanley's facet description of their hull, established in Amanbayeva–Wang and read in the original for this note, is

Pn = { x : 1 ≤ xi ≤ n, and ∑i∈I xi ≤ σ(|I|) for every I }
σ(k) = (n−k+1) + … + n = kn − k(k−1)/2

For an integer point the binding subset of a given size is the set of largest coordinates, so membership reduces to sorting and checking prefix sums. That is what the certified count runs on, and it is what the figure at the top of the page evaluates in the browser.

Amanbayeva–Wang determine a(n) only as a sum of Postnikov-formula evaluations over sum-slices, their Theorem 5.2, which is not a closed form. That is why the entry stayed at eight terms for four years: everything from a(9) onward that appears anywhere was an expected value read off Howroyd's conjectured generating function, never computed independently.

Section 2Theorem A, and the chain that proves it

Theorem A · PROVED

a(n) equals the number u(n) of loop-graphs on [n] with n edges in which every connected component contains exactly one cycle, where loops count as cycles of length 1 and parallel edges are not allowed. Consequently ∑ a(n)xn/n! = exp(T + ∑k≥3Tk/2k), which is Howroyd's conjectured generating function, and Wiseman's choosability conjecture holds.

The proof is a chain of five steps, each elementary once the previous one is in place:

  1. Shift. Subtracting 1 from every coordinate turns the facet inequalities into ∑i∈Iei ≤ ∂(I), where ∂(I) is the number of edges of Kn meeting I. So the lattice points are the integer points of a polymatroid.
  2. Hall. Those integer vectors are exactly the in-degree vectors of partial orientations of Kn: orient each edge toward one endpoint or leave it blank. One direction is counting; the other is Hall's theorem on a bipartite graph of demand units against edges.
  3. Lift. The polymatroid is the Minkowski sum of the C(n,2) triangles conv{0, êi, êj}, and lifting to one extra coordinate turns it into a sum of simplices Δ{0,i,j}, with the projection a bijection on lattice points.
  4. Postnikov. Theorem 11.3 of Postnikov's Permutohedra, associahedra, and beyond counts the lattice points of such a sum by G-draconian sequences. With y = (0,1,…,1) every raising factorial in that formula is 1, so a(n) is simply the number of draconian sequences.
  5. Identify, then re-count. A draconian sequence here is exactly a sparse multiforest: give each edge of Kn multiplicity 0, 1 or 2 so that every component is a tree or unicyclic. A labeled dissymmetry identity, unrooted trees plus edge-rooted trees equals vertex-rooted trees, matches those component types one for one with the components of Wiseman's objects: loop-rooted trees and simple unicyclic graphs. The exponential formula then gives the generating function.

The last step is where the doubled edge, which is a 2-cycle and therefore allowed in a sparse multiforest, is traded for a loop, which is a 1-cycle and is what Wiseman's loop-graphs use. The two families are equinumerous component by component, not identical.

17 graphs, 17 lattice points
The dictionary, at n = 3. All seventeen loop-graphs on three labelled dots with three edges whose every component carries exactly one cycle, enumerated in the browser rather than stored. A loop is drawn as a small circle at its dot. These seventeen are what Theorem A says the seventeen lattice points of the figure above are counting. Press the button to run both sides independently out to n = 7: the graph side by direct enumeration over edge subsets, the polytope side by the same facet test the first figure uses. They agree at every size, which is a check on the theorem, not a proof of it. The proof is the chain above.

Section 3Theorem B, the Ehrhart polynomial

The same machinery, run with the dilation factor kept as a variable, gives the whole counting polynomial rather than only its value at 1.

Theorem B · PROVED

i(Pn, t) = ∑M∈Sn ts(M) (t(t+1)/2)d(M), the sum over sparse multiforests M on [n], where s(M) and d(M) count the pairs of multiplicity 1 and 2. Equivalently ∑n≥0 i(Pn,t) xn/n! = (1−τ)−1/2 exp((2−t)τ/2t − τ²/4t), τ = T(tx). This answers question 6(b) of Amanbayeva–Wang.

Credit, prominently. The sum-form is a specialization of Corollary 7.6 of Liu–Thawinrak, arXiv:2512.14199 (December 2025), which was found mid-session during the novelty check and read in full before any claim was written. What is new here is the combinatorial identification of the draconian index set as sparse multiforests, and the closed generating function. The Minkowski-sum realization in Lemmas 1 to 3 is marked as an independent rediscovery: it is implicit in that paper's Example 7.4.

Setting t = 1 recovers Theorem A. Ehrhart reciprocity was checked against brute-force interior counts at n = 2 to 5, giving interior totals 0, 0, 5 and 96.

Section 4Forty terms, and the growth law

An exact dynamic program over the facet description, running over the value being placed and carrying the state (number of coordinates used, their sum), computes a(n) in big-integer arithmetic with no floating point anywhere. It reproduces all eight published terms and continues:

na(n)status before this session
87,501,422published, last known term
9167,341,283expected from the conjectured e.g.f. only
104,191,140,394expected from the conjectured e.g.f. only
11116,425,416,531expected from the conjectured e.g.f. only
123,552,072,881,320expected from the conjectured e.g.f. only
403.5317… × 1063beyond any published range

Howroyd's generating function, whose support was those eight fitted terms, matches the computed values exactly at every n ≤ 40. That is now a theorem rather than a coincidence, but it is worth stating as a separate fact because it is the strongest evidence available that the dynamic program itself is right.

The proved law against the exact terms, and how far apart they still are. The curve is a(n) / (C·nn−1/4) with C = e1/4√(2π)/(21/4Γ(1/4)) = 0.746492, the constant Corollary A4 proves. The terms a(n) are recomputed in your browser in exact big-integer arithmetic, from the graph side of Theorem A, and they reproduce the repository's certified facet-DP values digit for digit at all forty sizes. The law is proved, so the curve must tend to 1. It does not look like it yet: it crosses 1 near n = 9, bottoms out at 0.9841 around n = 33, and by n = 40 has climbed back only to 0.9842. The corrections are of order n−1/2, so the convergence is genuinely this slow; a reader who fitted a law to this data rather than proving one would get the exponent wrong. Hover for exact values.

Section 5What this rests on

Section 6Open questions

  1. A bijective proof of Theorem A. The route through Postnikov's formula is not bijective, and Selig's stochastic burning algorithm is the natural candidate for one.
  2. The complete-bipartite analogue. The same draconian machinery over Ka,b plus a cone should identify bipartite sparse multiforests, which would speak to Selig–Zhu (WALCOM 2025).
  3. Amanbayeva–Wang's question 6(a), the h-vector, which Theorem B does not settle.
  4. A sign-reversing involution for the interior points, which would make the reciprocity check structural rather than numerical.