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.

1, 2, 1, 5, 10, 1, 14, 73, 37, 1, 42, 476, 651, 126, 1, 132, 2952, 8530, 4770, 422, 1, 429, 17886, 95943, 114612, 31851, 1422, 1, 1430, 107305, 987261, 2162033, 1317133, 202953, 4853, 1, 4862, 642070, 9613054, 35196634, 39471355, 13792438, 1262800, 16786, 1

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

Table of n, a(n) for n=1..45.

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

Row sums give A000272(n+1).

Column k=0 gives A000108.

Similar to A108267.

Sequence in context: A326179 A247368 A019098 * A035309 A174218 A226308

Adjacent sequences: A333826 A333827 A333828 * A333830 A333831 A333832

Keyword

nonn,tabl,easy

Author

Matthieu Josuat-Vergès, Apr 06 2020

Status

approved