login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 0
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 (list; table; graph; refs; listen; history; text; internal format)
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()

    return mul( i for i in range(sum(l)-len(l)+2, sum(l)+1) ) / mul( 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.

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 27 06:29 EDT 2022. Contains 357052 sequences. (Running on oeis4.)