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)

class sage.combinat.non_decreasing_parking_function.NonDecreasingParkingFunction(lst)¶

Bases: sage.combinat.combinat.CombinatorialObject

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: NonDecreasingParkingFunction([])
[]
sage: NonDecreasingParkingFunction([1])
[1]
sage: NonDecreasingParkingFunction([2])
...
AssertionError: [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])
...
AssertionError: [1, 1, 4] is not a non-decreasing parking function.

classmethod from_dyck_word(dw)¶

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

EXAMPLES:

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]

TESTS:

sage: ndpf=NonDecreasingParkingFunctions(5);
sage: list(ndpf) == [NonDecreasingParkingFunction.from_dyck_word(pf.to_dyck_word()) for pf in ndpf]
True

to_dyck_word()¶

Implements 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:

                  .
               .  |
            .__.__|
         .__|  .  .
      .  |  .  .  .
   .  .__|  .  .  .
.__.__|  .  .  .  .
  1  1  2  4  5  5

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: 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]

TESTS:

sage: ndpf=NonDecreasingParkingFunctions(5);
sage: list(ndpf) == [pf.to_dyck_word().to_non_decreasing_parking_function() for pf in ndpf]
True

sage.combinat.non_decreasing_parking_function.NonDecreasingParkingFunctions(n=None)¶

Returns the combinatorial class 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: NonDecreasingParkingFunctions(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 combinatorial class of all non-decreasing parking functions.

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

If the size $n$ is specified, then NonDecreasingParkingFunctions returns combinatorial class of all non-decreasing parking functions of size $n$ .

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

TESTS:

sage: PF = NonDecreasingParkingFunctions(5)
sage: len(PF.list()) == PF.cardinality()
True

class sage.combinat.non_decreasing_parking_function.NonDecreasingParkingFunctions_all¶: Bases: sage.combinat.combinat.InfiniteAbstractCombinatorialClass

class sage.combinat.non_decreasing_parking_function.NonDecreasingParkingFunctions_n(n)¶

Bases: sage.combinat.combinat.CombinatorialClass

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: 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]

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

cardinality()¶

Returns the number of non-decreasing parking functions of size $n$ . This number is the $n$ -th Catalan number.

EXAMPLES:

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

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

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

TESTS:

sage: from sage.combinat.non_decreasing_parking_function import is_a
sage: is_a([1,1,2])
True
sage: is_a([1,1,4])
False
sage: is_a([1,1,3], 3)
True

Non-Decreasing Parking Functions¶

Previous topic

Next topic

This Page

Navigation

Non-Decreasing Parking Functions¶

Previous topic

Next topic

This Page

Quick search

Navigation