A333829 - OEIS

%I #49 Jan 05 2024 14:55:59

%S 1,2,1,5,10,1,14,73,37,1,42,476,651,126,1,132,2952,8530,4770,422,1,

%T 429,17886,95943,114612,31851,1422,1,1430,107305,987261,2162033,

%U 1317133,202953,4853,1,4862,642070,9613054,35196634,39471355,13792438,1262800,16786,1

%N Triangle read by rows: T(n,k) is the number of parking functions of length n with k strict descents. T(n,k) for n >= 1 and 0 <= k <= n-1.

%C In a parking function w(1), ..., w(n), a strict descent is an index i such that w(i) > w(i+1).

%C 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).

%H Ari Cruz, Pamela E. Harris, Kimberly J. Harry, Jan Kretschmann, Matt McClinton, Alex Moon, John O. Museus, and Eric Redmon, <a href="https://arxiv.org/abs/2312.16786">On some discrete statistics of parking functions</a>, arXiv:2312.16786 [math.CO], 2023.

%H Paul R. F. Schumacher, <a href="https://www.emis.de/journals/JIS/VOL21/Schumacher/schu5.html">Descents in Parking Functions</a>, J. Int. Seq. 21 (2018), #18.2.3.

%e The triangle T(n,k) begins:

%e n/k  0    1    2    3    4    5

%e 1    1

%e 2    2    1

%e 3    5   10    1

%e 4   14   73   37    1

%e 5   42  476  651  126    1

%e 6  132 2952 8530 4770  422    1

%e ...

%e 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]].

%o (SageMath)

%o var('z,t')

%o assume(0<z<1)

%o # 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.

%o def des_multiset(l):

%o     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) ))

%o # 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".

%o def kreweras_numbers(l):

%o     m = l.to_exp()

%o     s = sum(l)

%o     return ZZ.prod(range(s - len(l) + 2, s + 1)) // ZZ.prod(factorial(i) for i in m)

%o def Trow(n):

%o     pol = sum(des_multiset(l) * kreweras_numbers(l) for l in Partitions(n))

%o     return pol.list()

%o print([Trow(n) for n in (1..4)])

%o (SageMath) # using[latte_int from LattE]

%o # Install with "sage -i latte_int".

%o # Another method is to compute the Ehrhart h^*-polynomial of a polytope.

%o var('z,t')

%o def Tpol(n):

%o     p = Polyhedron( NonDecreasingParkingFunctions(n+1) ).ehrhart_polynomial()

%o     return expand(factor( (1-z)**(n+1) * sum( p * z**t , t , 0 , oo ) ))

%o def T(n,k):

%o     return Tpol(n).list()[n-1-k]

%Y Row sums give A000272(n+1).

%Y Column k=0 gives A000108.

%Y Similar to A108267.

%K nonn,tabl,easy

%O 1,2

%A _Matthieu Josuat-Vergès_, Apr 06 2020