cp's OEIS Frontend

A333829 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.

%I A333829 #49 Jan 05 2024 14:55:59
%S A333829 1,2,1,5,10,1,14,73,37,1,42,476,651,126,1,132,2952,8530,4770,422,1,
%T A333829 429,17886,95943,114612,31851,1422,1,1430,107305,987261,2162033,
%U A333829 1317133,202953,4853,1,4862,642070,9613054,35196634,39471355,13792438,1262800,16786,1
%N A333829 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 A333829 In a parking function w(1), ..., w(n), a strict descent is an index i such that w(i) > w(i+1).
%C A333829 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 A333829 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 A333829 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 A333829 The triangle T(n,k) begins:
%e A333829 n/k  0    1    2    3    4    5
%e A333829 1    1
%e A333829 2    2    1
%e A333829 3    5   10    1
%e A333829 4   14   73   37    1
%e A333829 5   42  476  651  126    1
%e A333829 6  132 2952 8530 4770  422    1
%e A333829 ...
%e A333829 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 A333829 (SageMath)
%o A333829 var('z,t')
%o A333829 assume(0<z<1)
%o A333829 # 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 A333829 def des_multiset(l):
%o A333829     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 A333829 # 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 A333829 def kreweras_numbers(l):
%o A333829     m = l.to_exp()
%o A333829     s = sum(l)
%o A333829     return ZZ.prod(range(s - len(l) + 2, s + 1)) // ZZ.prod(factorial(i) for i in m)
%o A333829 def Trow(n):
%o A333829     pol = sum(des_multiset(l) * kreweras_numbers(l) for l in Partitions(n))
%o A333829     return pol.list()
%o A333829 print([Trow(n) for n in (1..4)])
%o A333829 (SageMath) # using[latte_int from LattE]
%o A333829 # Install with "sage -i latte_int".
%o A333829 # Another method is to compute the Ehrhart h^*-polynomial of a polytope.
%o A333829 var('z,t')
%o A333829 def Tpol(n):
%o A333829     p = Polyhedron( NonDecreasingParkingFunctions(n+1) ).ehrhart_polynomial()
%o A333829     return expand(factor( (1-z)**(n+1) * sum( p * z**t , t , 0 , oo ) ))
%o A333829 def T(n,k):
%o A333829     return Tpol(n).list()[n-1-k]
%Y A333829 Row sums give A000272(n+1).
%Y A333829 Column k=0 gives A000108.
%Y A333829 Similar to A108267.
%K A333829 nonn,tabl,easy
%O A333829 1,2
%A A333829 _Matthieu Josuat-Vergès_, Apr 06 2020