Non-Decreasing Parking Functions¶

A non-decreasing parking function of size \(n\) is a non-decreasing function \(f\) from \(\{1,\dots,n\}\) to itself such that for all \(i\), one has \(f(i) \leq i\).

The number of non-decreasing parking functions of size \(n\) is the \(n\)-th Catalan number.

The set of non-decreasing parking functions of size \(n\) is in bijection with the set of Dyck words of size \(n\).

AUTHORS:

Florent Hivert (2009-04)
Christian Stump (2012-11) added pretty printing

class sage.combinat.non_decreasing_parking_function.NonDecreasingParkingFunction(lst)[source]¶

Bases: Element

A non decreasing parking function of size \(n\) is a non-decreasing function \(f\) from \(\{1,\dots,n\}\) to itself such that for all \(i\), one has \(f(i) \leq i\).

EXAMPLES:

Sage

sage: NonDecreasingParkingFunction([])
[]
sage: NonDecreasingParkingFunction([1])
[1]
sage: NonDecreasingParkingFunction([2])
Traceback (most recent call last):
...
ValueError: [2] is not a non-decreasing parking function
sage: NonDecreasingParkingFunction([1,2])
[1, 2]
sage: NonDecreasingParkingFunction([1,1,2])
[1, 1, 2]
sage: NonDecreasingParkingFunction([1,1,4])
Traceback (most recent call last):
...
ValueError: [1, 1, 4] is not a non-decreasing parking function

Python

>>> from sage.all import *
>>> NonDecreasingParkingFunction([])
[]
>>> NonDecreasingParkingFunction([Integer(1)])
[1]
>>> NonDecreasingParkingFunction([Integer(2)])
Traceback (most recent call last):
...
ValueError: [2] is not a non-decreasing parking function
>>> NonDecreasingParkingFunction([Integer(1),Integer(2)])
[1, 2]
>>> NonDecreasingParkingFunction([Integer(1),Integer(1),Integer(2)])
[1, 1, 2]
>>> NonDecreasingParkingFunction([Integer(1),Integer(1),Integer(4)])
Traceback (most recent call last):
...
ValueError: [1, 1, 4] is not a non-decreasing parking function

classmethod from_dyck_word(dw)[source]¶

Bijection from Dyck words. It is the inverse of the bijection to_dyck_word(). You can find there the mathematical definition.

EXAMPLES:

Sage

sage: NonDecreasingParkingFunction.from_dyck_word([])
[]
sage: NonDecreasingParkingFunction.from_dyck_word([1,0])
[1]
sage: NonDecreasingParkingFunction.from_dyck_word([1,1,0,0])
[1, 1]
sage: NonDecreasingParkingFunction.from_dyck_word([1,0,1,0])
[1, 2]
sage: NonDecreasingParkingFunction.from_dyck_word([1,0,1,1,0,1,0,0,1,0])
[1, 2, 2, 3, 5]

Python

>>> from sage.all import *
>>> NonDecreasingParkingFunction.from_dyck_word([])
[]
>>> NonDecreasingParkingFunction.from_dyck_word([Integer(1),Integer(0)])
[1]
>>> NonDecreasingParkingFunction.from_dyck_word([Integer(1),Integer(1),Integer(0),Integer(0)])
[1, 1]
>>> NonDecreasingParkingFunction.from_dyck_word([Integer(1),Integer(0),Integer(1),Integer(0)])
[1, 2]
>>> NonDecreasingParkingFunction.from_dyck_word([Integer(1),Integer(0),Integer(1),Integer(1),Integer(0),Integer(1),Integer(0),Integer(0),Integer(1),Integer(0)])
[1, 2, 2, 3, 5]

grade()[source]¶

Return the length of self.

EXAMPLES:

Sage

sage: ndpf = NonDecreasingParkingFunctions(5)
sage: len(ndpf.random_element())
5

Python

>>> from sage.all import *
>>> ndpf = NonDecreasingParkingFunctions(Integer(5))
>>> len(ndpf.random_element())
5

to_dyck_word()[source]¶

Implement the bijection to Dyck words, which is defined as follows. Take a non decreasing parking function, say [1,1,2,4,5,5], and draw its graph:

         ___
        |  . 5
       _|  . 5
   ___|  . . 4
 _|  . . . . 2
|  . . . . . 1
|  . . . . . 1

The corresponding Dyck word [1,1,0,1,0,0,1,0,1,1,0,0] is then read off from the sequence of horizontal and vertical steps. The converse bijection is from_dyck_word().

EXAMPLES:

Sage

sage: NonDecreasingParkingFunction([1,1,2,4,5,5]).to_dyck_word()
[1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0]
sage: NonDecreasingParkingFunction([]).to_dyck_word()
[]
sage: NonDecreasingParkingFunction([1,1,1]).to_dyck_word()
[1, 1, 1, 0, 0, 0]
sage: NonDecreasingParkingFunction([1,2,3]).to_dyck_word()
[1, 0, 1, 0, 1, 0]
sage: NonDecreasingParkingFunction([1,1,3,3,4,6,6]).to_dyck_word()
[1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0]

Python

>>> from sage.all import *
>>> NonDecreasingParkingFunction([Integer(1),Integer(1),Integer(2),Integer(4),Integer(5),Integer(5)]).to_dyck_word()
[1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0]
>>> NonDecreasingParkingFunction([]).to_dyck_word()
[]
>>> NonDecreasingParkingFunction([Integer(1),Integer(1),Integer(1)]).to_dyck_word()
[1, 1, 1, 0, 0, 0]
>>> NonDecreasingParkingFunction([Integer(1),Integer(2),Integer(3)]).to_dyck_word()
[1, 0, 1, 0, 1, 0]
>>> NonDecreasingParkingFunction([Integer(1),Integer(1),Integer(3),Integer(3),Integer(4),Integer(6),Integer(6)]).to_dyck_word()
[1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0]

sage.combinat.non_decreasing_parking_function.NonDecreasingParkingFunctions(n=None)[source]¶

Return the set of Non-Decreasing Parking Functions.

A non-decreasing parking function of size \(n\) is a non-decreasing function \(f\) from \(\{1,\dots,n\}\) to itself such that for all \(i\), one has \(f(i) \leq i\).

EXAMPLES:

Here are all the-non decreasing parking functions of size 5:

Sage

sage: NonDecreasingParkingFunctions(3).list()
[[1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 2, 3]]

Python

>>> from sage.all import *
>>> NonDecreasingParkingFunctions(Integer(3)).list()
[[1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 2, 3]]

If no size is specified, then NonDecreasingParkingFunctions returns the set of all non-decreasing parking functions.

Sage

sage: PF = NonDecreasingParkingFunctions(); PF
Non-decreasing parking functions
sage: [] in PF
True
sage: [1] in PF
True
sage: [2] in PF
False
sage: [1,1,3] in PF
True
sage: [1,1,4] in PF
False

Python

>>> from sage.all import *
>>> PF = NonDecreasingParkingFunctions(); PF
Non-decreasing parking functions
>>> [] in PF
True
>>> [Integer(1)] in PF
True
>>> [Integer(2)] in PF
False
>>> [Integer(1),Integer(1),Integer(3)] in PF
True
>>> [Integer(1),Integer(1),Integer(4)] in PF
False

If the size \(n\) is specified, then NonDecreasingParkingFunctions returns the set of all non-decreasing parking functions of size \(n\).

Sage

sage: PF = NonDecreasingParkingFunctions(0)
sage: PF.list()
[[]]
sage: PF = NonDecreasingParkingFunctions(1)
sage: PF.list()
[[1]]
sage: PF = NonDecreasingParkingFunctions(3)
sage: PF.list()
[[1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 2, 3]]

sage: PF3 = NonDecreasingParkingFunctions(3); PF3
Non-decreasing parking functions of size 3
sage: [] in PF3
False
sage: [1] in PF3
False
sage: [1,1,3] in PF3
True
sage: [1,1,4] in PF3
False

Python

>>> from sage.all import *
>>> PF = NonDecreasingParkingFunctions(Integer(0))
>>> PF.list()
[[]]
>>> PF = NonDecreasingParkingFunctions(Integer(1))
>>> PF.list()
[[1]]
>>> PF = NonDecreasingParkingFunctions(Integer(3))
>>> PF.list()
[[1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 2, 3]]

>>> PF3 = NonDecreasingParkingFunctions(Integer(3)); PF3
Non-decreasing parking functions of size 3
>>> [] in PF3
False
>>> [Integer(1)] in PF3
False
>>> [Integer(1),Integer(1),Integer(3)] in PF3
True
>>> [Integer(1),Integer(1),Integer(4)] in PF3
False

class sage.combinat.non_decreasing_parking_function.NonDecreasingParkingFunctions_all[source]¶

Bases: UniqueRepresentation, Parent

graded_component(n)[source]¶

Return the graded component.

EXAMPLES:

Sage

sage: P = NonDecreasingParkingFunctions()
sage: P.graded_component(4) == NonDecreasingParkingFunctions(4)
True

Python

>>> from sage.all import *
>>> P = NonDecreasingParkingFunctions()
>>> P.graded_component(Integer(4)) == NonDecreasingParkingFunctions(Integer(4))
True

class sage.combinat.non_decreasing_parking_function.NonDecreasingParkingFunctions_n(n)[source]¶

Bases: UniqueRepresentation, Parent

The combinatorial class of non-decreasing parking functions of size \(n\).

A non-decreasing parking function of size \(n\) is a non-decreasing function \(f\) from \(\{1,\dots,n\}\) to itself such that for all \(i\), one has \(f(i) \leq i\).

The number of non-decreasing parking functions of size \(n\) is the \(n\)-th Catalan number.

EXAMPLES:

Sage

sage: PF = NonDecreasingParkingFunctions(3)
sage: PF.list()
[[1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 2, 3]]
sage: PF = NonDecreasingParkingFunctions(4)
sage: PF.list()
[[1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 1, 3], [1, 1, 1, 4], [1, 1, 2, 2], [1, 1, 2, 3], [1, 1, 2, 4], [1, 1, 3, 3], [1, 1, 3, 4], [1, 2, 2, 2], [1, 2, 2, 3], [1, 2, 2, 4], [1, 2, 3, 3], [1, 2, 3, 4]]
sage: [ NonDecreasingParkingFunctions(i).cardinality() for i in range(10)]
[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862]

Python

>>> from sage.all import *
>>> PF = NonDecreasingParkingFunctions(Integer(3))
>>> PF.list()
[[1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 2, 3]]
>>> PF = NonDecreasingParkingFunctions(Integer(4))
>>> PF.list()
[[1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 1, 3], [1, 1, 1, 4], [1, 1, 2, 2], [1, 1, 2, 3], [1, 1, 2, 4], [1, 1, 3, 3], [1, 1, 3, 4], [1, 2, 2, 2], [1, 2, 2, 3], [1, 2, 2, 4], [1, 2, 3, 3], [1, 2, 3, 4]]
>>> [ NonDecreasingParkingFunctions(i).cardinality() for i in range(Integer(10))]
[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862]

Warning

The precise order in which the parking function are generated or listed is not fixed, and may change in the future.

AUTHORS:

Florent Hivert

Element[source]¶: alias of NonDecreasingParkingFunction

cardinality()[source]¶

Return the number of non-decreasing parking functions of size \(n\).

This number is the \(n\)-th Catalan number.

EXAMPLES:

Sage

sage: PF = NonDecreasingParkingFunctions(0)
sage: PF.cardinality()
1
sage: PF = NonDecreasingParkingFunctions(1)
sage: PF.cardinality()
1
sage: PF = NonDecreasingParkingFunctions(3)
sage: PF.cardinality()
5
sage: PF = NonDecreasingParkingFunctions(5)
sage: PF.cardinality()
42

Python

>>> from sage.all import *
>>> PF = NonDecreasingParkingFunctions(Integer(0))
>>> PF.cardinality()
1
>>> PF = NonDecreasingParkingFunctions(Integer(1))
>>> PF.cardinality()
1
>>> PF = NonDecreasingParkingFunctions(Integer(3))
>>> PF.cardinality()
5
>>> PF = NonDecreasingParkingFunctions(Integer(5))
>>> PF.cardinality()
42

one()[source]¶

Return the unit of this monoid.

This is the non-decreasing parking function [1, 2, …, n].

EXAMPLES:

Sage

sage: ndpf = NonDecreasingParkingFunctions(5)
sage: x = ndpf.random_element(); x  # random
sage: e = ndpf.one()
sage: x == e*x == x*e
True

Python

>>> from sage.all import *
>>> ndpf = NonDecreasingParkingFunctions(Integer(5))
>>> x = ndpf.random_element(); x  # random
>>> e = ndpf.one()
>>> x == e*x == x*e
True

random_element()[source]¶

Return a random parking function of the given size.

EXAMPLES:

Sage

sage: ndpf = NonDecreasingParkingFunctions(5)
sage: x = ndpf.random_element(); x  # random
[1, 2, 2, 4, 5]
sage: x in ndpf
True

Python

>>> from sage.all import *
>>> ndpf = NonDecreasingParkingFunctions(Integer(5))
>>> x = ndpf.random_element(); x  # random
[1, 2, 2, 4, 5]
>>> x in ndpf
True

sage.combinat.non_decreasing_parking_function.is_a(x, n=None)[source]¶

Check whether a list is a non-decreasing parking function.

If a size \(n\) is specified, checks if a list is a non-decreasing parking function of size \(n\).