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.
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.
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.
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.
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:
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.
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.
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.
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.
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:
n
a(n)
status before this session
8
7,501,422
published, last known term
9
167,341,283
expected from the conjectured e.g.f. only
10
4,191,140,394
expected from the conjectured e.g.f. only
11
116,425,416,531
expected from the conjectured e.g.f. only
12
3,552,072,881,320
expected from the conjectured e.g.f. only
40
3.5317… × 1063
beyond 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
Two published theorems are used as black boxes. Stanley's facet
description of Pn, as established in Amanbayeva–Wang (ECA 2022), and
Postnikov's Theorem 11.3 (IMRN 2009). Both were read in the original. The facet
description was additionally checked computationally here by exact rational hull
membership at n = 3 and 4.
Theorem B's sum-form is not new. It specializes Liu–Thawinrak,
Corollary 7.6. See Section 3; this is stated there rather than buried.
The asymptotic law is proved, the convergence is not shown. At
n = 40 the ratio is 0.984, and the figure says so rather than
cropping the axis.
Twelve exact checks back the computation, all in exact arithmetic:
three independent computations of a(n) at small n; the graph side brute-forced
independently in Python for n ≤ 7 and in C at n = 8 over
30.2 million subsets; the Ehrhart polynomial three ways; exact rational hull
membership; and Ehrhart reciprocity against brute interior counts.
Two guesses were killed early and are recorded rather than hidden. A
Tutte-evaluation reformulation (T(K3;3,1) = 13, not 17) and
a zonotope guess (7, not 3, at n = 2), both dead in minutes.
Upstream reporting has not happened. The OEIS edit turning the two
conjectures into theorems, and notes to Selig, Howroyd and Wiseman, are pending
at the time this page went up. Nothing here should be read as saying the entry
has been updated.
Section 6Open questions
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.
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).
Amanbayeva–Wang's question 6(a), the h-vector, which Theorem B does not
settle.
A sign-reversing involution for the interior points, which would make the
reciprocity check structural rather than numerical.