OFFSET
1,2
COMMENTS
In a parking function w(1), ..., w(n), a strict descent is an index i such that w(i) > w(i+1).
Define an n-dimensional polytope as the convex hull of length n+1 nondecreasing parking functions. Then, the Ehrhart h*-polynomial of this polytope is Sum_{k=0..n-1} T(n,k) * z^(n-1-k).
LINKS
Per Alexandersson, Rows 1..35 of triangle
Ari Cruz, Pamela E. Harris, Kimberly J. Harry, Jan Kretschmann, Matt McClinton, Alex Moon, John O. Museus, and Eric Redmon, On some discrete statistics of parking functions, arXiv:2312.16786 [math.CO], 2023.
Paul R. F. Schumacher, Descents in Parking Functions, J. Int. Seq. 21 (2018), #18.2.3.
EXAMPLE
The triangle T(n,k) begins:
n/k 0 1 2 3 4 5
1 1
2 2 1
3 5 10 1
4 14 73 37 1
5 42 476 651 126 1
6 132 2952 8530 4770 422 1
...
The 10 parking functions of length 3 with 1 strict descent are: [[1, 2, 1], [2, 1, 1], [1, 3, 1], [3, 1, 1], [2, 1, 2], [2, 2, 1], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]].
PROG
(SageMath)
var('z, t')
assume(0<z<1)
# Returns a polynomial which is the generating function of strict descents in permutations of a multiset of integers. The multiplicity of these integers are given by an integer partition l. The function uses an analytic expression rather than enumerating the combinatorial objects.
def des_multiset(l):
return expand(factor(sum( mul( mul( t+i for i in range(1, k+1)) / factorial(k) for k in l ) * z**t , t , 0 , oo ) * (1-z)**(sum(l)+1) ))
# Returns the numbers of noncrossing partitions of size n and type l (an integer partition of n), cf. Kreweras: "Sur les partitions non-croisées d'un cycle".
def kreweras_numbers(l):
m = l.to_exp()
s = sum(l)
return ZZ.prod(range(s - len(l) + 2, s + 1)) // ZZ.prod(factorial(i) for i in m)
def Trow(n):
pol = sum(des_multiset(l) * kreweras_numbers(l) for l in Partitions(n))
return pol.list()
print([Trow(n) for n in (1..4)])
(SageMath) # using[latte_int from LattE]
# Install with "sage -i latte_int".
# Another method is to compute the Ehrhart h^*-polynomial of a polytope.
var('z, t')
def Tpol(n):
p = Polyhedron( NonDecreasingParkingFunctions(n+1) ).ehrhart_polynomial()
return expand(factor( (1-z)**(n+1) * sum( p * z**t , t , 0 , oo ) ))
def T(n, k):
return Tpol(n).list()[n-1-k]
CROSSREFS
KEYWORD
AUTHOR
Matthieu Josuat-Vergès, Apr 06 2020
STATUS
approved