INFORMALLY (reference [Beck]):
Imagine a one-way cul-de-sac with parking spots. We will give the
first parking spot the number 1, the next one number 2, etc., down to
the last one, number
. Initially they are all free, but there are
cars approaching the street, and they would all like to park there.
To make life interesting, every car has a parking preference, and we
record the preferences in a sequence; For example, if
, the
sequence
means that the first car would like to park at
spot number 2, the second car prefers parking spot number 1, and the
last car would also like to part at number 1. The street is very
narrow, so there is no way to back up. Now each car enters the street
and approaches its preferred parking spot; if it is free, it parks
there, and if not, it moves down the street to the first available
spot. We call a sequence a parking function (of length
) if all
cars end up finding a parking spot. For example, the sequence
is a parking sequence (of length 3), whereas the sequence
is not.
FORMALLY:
A parking function of size is a sequence
of
positive integers such that if
is
the increasing rearrangement of
, then
.
A parking function of size is a pair
of two sequences
and
where
is a permutation and
is an area sequence of a
Dyck path of size n such that
,
and
if
then
.
The number of parking functions of size is equal to the number of
rooted forests on
vertices and is equal to
.
REFERENCES:
[Beck] | M. Beck, Stanford Math Circle - Parking Functions, October 2010, http://math.stanford.edu/circle/parkingBeck.pdf |
[Hag08] | (1, 2, 3) The ![]() |
[Shin] | (1, 2) H. Shin, Forests and Parking Functions, slides from talk September 24, 2008, http://www.emis.de/journals/SLC/wpapers/s61vortrag/shin.pdf |
[GXZ] | (1, 2, 3) A. M. Garsia, G. Xin, M. Zabrocki, A three shuffle case of the compositional parking function conjecture, Arxiv 1208.5796v1 |
AUTHORS:
- used non-decreasing_parking_functions code by Florent Hivert (2009 - 04)
- Dorota Mazur (2012 - 09)
Return the combinatorial class of Parking Functions.
A parking function of size is a sequence
of positive integers such that if
is
the increasing rearrangement of
, then
.
A parking function of size is a pair
of two sequences
and
where
is a permutation and
is an area sequence
of a Dyck Path of size
such that
,
and if
then
.
The number of parking functions of size is equal to the number
of rooted forests on
vertices and is equal to
.
INPUT:
OUTPUT:
EXAMPLES:
sage: ParkingFunction([])
[]
sage: ParkingFunction([1])
[1]
sage: ParkingFunction([2])
Traceback (most recent call last):
...
ValueError: [2] is not a parking function.
sage: ParkingFunction([1,2])
[1, 2]
sage: ParkingFunction([1,1,2])
[1, 1, 2]
sage: ParkingFunction([1,4,1])
Traceback (most recent call last):
...
ValueError: [1, 4, 1] is not a parking function.
sage: ParkingFunction(labelling=[3,1,2], area_sequence=[0,0,1])
[2, 2, 1]
sage: ParkingFunction([2,2,1]).to_labelled_dyck_word()
[3, 0, 1, 2, 0, 0]
sage: ParkingFunction(labelled_dyck_word = [3,0,1,2,0,0])
[2, 2, 1]
sage: ParkingFunction(labelling=[3,1,2], area_sequence=[0,1,1])
Traceback (most recent call last):
...
ValueError: [3, 1, 2] is not a valid labeling of area sequence [0, 1, 1]
Bases: sage.combinat.combinat.CombinatorialObject
TESTS:
sage: ParkingFunction([1, 1, 2, 2, 5, 6])
[1, 1, 2, 2, 5, 6]
Return the area of the labelled Dyck path corresponding to the parking function.
INPUT:
OUTPUT:
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5])
sage: PF.area()
6
sage: ParkingFunction([3,1,1,4]).area()
1
sage: ParkingFunction([4,1,1,1]).area()
3
sage: ParkingFunction([2,1,4,1]).area()
2
Return the sequence of cars that take parking spots 1 through
and corresponding to the parking function.
For example, cars_permutation(PF) = [2, 4, 5, 6, 3, 1, 7] means that car 2 takes spots 1, car 4 takes spot 2, ..., car 1 takes spot 6 and car 7 takes spot 7.
INPUT:
OUTPUT:
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5])
sage: PF.cars_permutation()
[2, 4, 5, 6, 3, 1, 7]
sage: ParkingFunction([3,1,1,4]).cars_permutation()
[2, 3, 1, 4]
sage: ParkingFunction([4,1,1,1]).cars_permutation()
[2, 3, 4, 1]
sage: ParkingFunction([2,1,4,1]).cars_permutation()
[2, 1, 4, 3]
Return the characteristic quasisymmetric function of self.
The characteristic function of the Parking Function is the sum
over all permutation labellings of the Dyck path where
(ides_composition()) is
the descent composition of diagonal reading word of the
parking function.
INPUT:
OUTPUT:
EXAMPLES:
sage: R = QQ['q','t'].fraction_field()
sage: (q,t) = R.gens()
sage: cqf = sum(t**PF.area()*PF.characteristic_quasisymmetric_function() for PF in ParkingFunctions(3)); cqf
(q^3+q^2*t+q*t^2+t^3+q*t)*F[1, 1, 1] + (q^2+q*t+t^2+q+t)*F[1, 2] + (q^2+q*t+t^2+q+t)*F[2, 1] + F[3]
sage: s = SymmetricFunctions(R).s()
sage: s(cqf.to_symmetric_function())
(q^3+q^2*t+q*t^2+t^3+q*t)*s[1, 1, 1] + (q^2+q*t+t^2+q+t)*s[2, 1] + s[3]
sage: s(cqf.to_symmetric_function()).nabla(power = -1)
s[1, 1, 1]
sage: p = ParkingFunction([3, 1, 2])
sage: p.characteristic_quasisymmetric_function()
q*F[2, 1]
sage: pf = ParkingFunction([1,2,7,2,1,2,3,2,1])
sage: pf.characteristic_quasisymmetric_function()
q^2*F[1, 1, 1, 2, 1, 3]
Return the composition of the labelled Dyck path corresponding to the parking function.
For example, touch_composition(PF) = [4, 3] means that the first touch is four diagonal units from the starting point, and the second is three units further (see [GXZ] p. 2).
INPUT:
OUTPUT:
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5])
sage: PF.touch_composition()
[4, 3]
sage: ParkingFunction([3,1,1,4]).touch_composition()
[2, 1, 1]
sage: ParkingFunction([4,1,1,1]).touch_composition()
[3, 1]
sage: ParkingFunction([2,1,4,1]).touch_composition()
[3, 1]
Return a diagonal word of the labelled Dyck path corresponding to parking function (see [Hag08] p. 75).
INPUT:
OUTPUT:
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5])
sage: PF.diagonal_reading_word()
[5, 1, 7, 4, 6, 3, 2]
sage: ParkingFunction([1, 1, 1]).diagonal_reading_word()
[3, 2, 1]
sage: ParkingFunction([1, 2, 3]).diagonal_reading_word()
[3, 2, 1]
sage: ParkingFunction([1, 1, 3, 4]).diagonal_reading_word()
[2, 4, 3, 1]
sage: ParkingFunction([1, 1, 1]).diagonal_word()
[3, 2, 1]
sage: ParkingFunction([1, 2, 3]).diagonal_word()
[3, 2, 1]
sage: ParkingFunction([1, 4, 3, 1]).diagonal_word()
[4, 2, 3, 1]
Return a diagonal word of the labelled Dyck path corresponding to parking function (see [Hag08] p. 75).
INPUT:
OUTPUT:
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5])
sage: PF.diagonal_reading_word()
[5, 1, 7, 4, 6, 3, 2]
sage: ParkingFunction([1, 1, 1]).diagonal_reading_word()
[3, 2, 1]
sage: ParkingFunction([1, 2, 3]).diagonal_reading_word()
[3, 2, 1]
sage: ParkingFunction([1, 1, 3, 4]).diagonal_reading_word()
[2, 4, 3, 1]
sage: ParkingFunction([1, 1, 1]).diagonal_word()
[3, 2, 1]
sage: ParkingFunction([1, 2, 3]).diagonal_word()
[3, 2, 1]
sage: ParkingFunction([1, 4, 3, 1]).diagonal_word()
[4, 2, 3, 1]
Return the number of inversions of a labelled Dyck path corresponding to the parking function (see [Hag08] p. 74).
Same as the cardinality of dinversion_pairs().
INPUT:
OUTPUT:
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5])
sage: PF.dinv()
6
sage: ParkingFunction([3,1,1,4]).dinv()
3
sage: ParkingFunction([4,1,1,1]).dinv()
1
sage: ParkingFunction([2,1,4,1]).dinv()
2
Return the descent inversion pairs of a labelled Dyck path corresponding to the parking function.
INPUT:
OUTPUT:
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5])
sage: PF.dinversion_pairs()
[(0, 4), (1, 5), (2, 5), (1, 4), (2, 4), (3, 6)]
sage: ParkingFunction([3,1,1,4]).dinversion_pairs()
[(0, 3), (2, 3), (1, 2)]
sage: ParkingFunction([4,1,1,1]).dinversion_pairs()
[(1, 3)]
sage: ParkingFunction([2,1,4,1]).dinversion_pairs()
[(0, 3), (1, 3)]
Return the descents() sequence of the inverse of the diagonal_reading_word() of self.
For example, ides(PF) = [1, 2, 3, 5] means that descents are at the 2nd, 3rd, 4th and 6th positions in the inverse of the diagonal_reading_word() of the parking function (see [GXZ] p. 2).
INPUT:
OUTPUT:
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5])
sage: PF.ides()
[1, 2, 3, 5]
sage: ParkingFunction([3,1,1,4]).ides()
[1]
sage: ParkingFunction([4,1,1,1]).ides()
[1, 2]
sage: ParkingFunction([4,3,1,1]).ides()
[2]
Return the descents_composition() of the inverse of the diagonal_reading_word() of corresponding parking function.
For example, ides_composition(PF) = [4, 2, 1] means that the descents of the inverse of the permutation diagonal_reading_word() of the parking function with word PF are at the 4th and 6th positions.
INPUT:
OUTPUT:
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5])
sage: PF.ides_composition()
[2, 1, 1, 2, 1]
sage: ParkingFunction([3,1,1,4]).ides_composition()
[2, 2]
sage: ParkingFunction([4,1,1,1]).ides_composition()
[2, 1, 1]
sage: ParkingFunction([4,3,1,1]).ides_composition()
[3, 1]
Return the sum of the differences between the parked and preferred parking spots.
See [Shin] p. 18.
INPUT:
OUTPUT:
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5])
sage: PF.jump()
6
sage: ParkingFunction([3,1,1,4]).jump()
1
sage: ParkingFunction([4,1,1,1]).jump()
3
sage: ParkingFunction([2,1,4,1]).jump()
2
Return the displacements of cars that corresponds to the parking function.
For example, jump_list(PF) = [0, 0, 0, 0, 1, 3, 2] means that car 1 through 4 parked in their preferred spots, car 5 had to park one spot farther (jumped or was displaced by one spot), car 6 had to jump 3 spots, and car 7 had to jump two spots.
INPUT:
OUTPUT:
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5])
sage: PF.jump_list()
[0, 0, 0, 0, 1, 3, 2]
sage: ParkingFunction([3,1,1,4]).jump_list()
[0, 0, 1, 0]
sage: ParkingFunction([4,1,1,1]).jump_list()
[0, 0, 1, 2]
sage: ParkingFunction([2,1,4,1]).jump_list()
[0, 0, 0, 2]
Return the number of cars that parked in their preferred parking spots (see [Shin] p. 33).
INPUT:
OUTPUT:
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5])
sage: PF.luck()
4
sage: ParkingFunction([3,1,1,4]).luck()
3
sage: ParkingFunction([4,1,1,1]).luck()
2
sage: ParkingFunction([2,1,4,1]).luck()
3
Return the cars that can park in their preferred spots. For example, lucky_cars(PF) = [1, 2, 7] means that cars 1, 2 and 7 parked in their preferred spots and all the other cars did not.
INPUT:
OUTPUT:
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5])
sage: PF.lucky_cars()
[1, 2, 3, 4]
sage: ParkingFunction([3,1,1,4]).lucky_cars()
[1, 2, 4]
sage: ParkingFunction([4,1,1,1]).lucky_cars()
[1, 2]
sage: ParkingFunction([2,1,4,1]).lucky_cars()
[1, 2, 3]
Return the sequence of parking spots that are taken by cars 1
through and corresponding to the parking function.
For example, parking_permutation(PF) = [6, 1, 5, 2, 3, 4, 7] means that spot 6 is taken by car 1, spot 1 by car 2, spot 5 by car 3, spot 2 is taken by car 4, spot 3 is taken by car 5, spot 4 is taken by car 6 and spot 7 is taken by car 7.
INPUT:
OUTPUT:
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5])
sage: PF.parking_permutation()
[6, 1, 5, 2, 3, 4, 7]
sage: ParkingFunction([3,1,1,4]).parking_permutation()
[3, 1, 2, 4]
sage: ParkingFunction([4,1,1,1]).parking_permutation()
[4, 1, 2, 3]
sage: ParkingFunction([2,1,4,1]).parking_permutation()
[2, 1, 4, 3]
Displays a parking function as a lattice path consisting of a Dyck path and a labelling with the labels displayed along the edges of the Dyck path.
INPUT:
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5])
sage: PF.pretty_print()
___
_|1x
|7x .
_____|3 . .
|5x x . . .
_|4x . . . .
|6x . . . . .
|2 . . . . . .
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5])
sage: PF.pretty_print(underpath = false)
___
_| x 1
| x . 7
_____| . . 3
| x x . . . 5
_| x . . . . 4
| x . . . . . 6
| . . . . . . 2
sage: ParkingFunction([3, 1, 1, 4]).pretty_print()
_
_|4
___|1 .
|3x . .
|2 . . .
sage: ParkingFunction([1,1,1]).pretty_print()
_____
|3x x
|2x .
|1 . .
sage: ParkingFunction([4,1,1,1]).pretty_print()
_
_____|1
|4x x .
|3x . .
|2 . . .
sage: ParkingFunction([2,1,4,1]).pretty_print()
_
___|3
_|1x .
|4x . .
|2 . . .
sage: ParkingFunction([2,1,4,1]).pretty_print(underpath = false)
_
___| 3
_| x . 1
| x . . 4
| . . . 2
sage: pf = ParkingFunction([1,2,3,7,3,2,1,2,3,2,1])
sage: pf.pretty_print()
_________
_______| x x x x 4
| x x x x x x x . 9
| x x x x x x . . 5
_| x x x x x . . . 3
| x x x x x . . . . 10
| x x x x . . . . . 8
| x x x . . . . . . 6
_| x x . . . . . . . 2
| x x . . . . . . . . 11
| x . . . . . . . . . 7
| . . . . . . . . . . 1
Return the primary descent inversion pairs of a labelled Dyck path corresponding to the parking function.
INPUT:
OUTPUT:
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5])
sage: PF.primary_dinversion_pairs()
[(0, 4), (1, 5), (2, 5)]
sage: ParkingFunction([3,1,1,4]).primary_dinversion_pairs()
[(0, 3), (2, 3)]
sage: ParkingFunction([4,1,1,1]).primary_dinversion_pairs()
[]
sage: ParkingFunction([2,1,4,1]).primary_dinversion_pairs()
[(0, 3)]
Return the secondary descent inversion pairs of a labelled Dyck path corresponding to the parking function.
INPUT:
OUTPUT:
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5])
sage: PF.secondary_dinversion_pairs()
[(1, 4), (2, 4), (3, 6)]
sage: ParkingFunction([3,1,1,4]).secondary_dinversion_pairs()
[(1, 2)]
sage: ParkingFunction([4,1,1,1]).secondary_dinversion_pairs()
[(1, 3)]
sage: ParkingFunction([2,1,4,1]).secondary_dinversion_pairs()
[(1, 3)]
Return the non-decreasing parking function which underlies the parking function.
INPUT:
OUTPUT:
See also
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5])
sage: PF.to_NonDecreasingParkingFunction()
[1, 1, 2, 2, 5, 5, 6]
sage: ParkingFunction([3,1,1,4]).to_NonDecreasingParkingFunction()
[1, 1, 3, 4]
sage: ParkingFunction([4,1,1,1]).to_NonDecreasingParkingFunction()
[1, 1, 1, 4]
sage: ParkingFunction([2,1,4,1]).to_NonDecreasingParkingFunction()
[1, 1, 2, 4]
sage: ParkingFunction([4,1,2,1]).to_NonDecreasingParkingFunction()
[1, 1, 2, 4]
Return the area sequence of the support Dyck path of the parking function.
INPUT:
OUTPUT:
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5])
sage: PF.to_area_sequence()
[0, 1, 1, 2, 0, 1, 1]
sage: ParkingFunction([3,1,1,4]).to_area_sequence()
[0, 1, 0, 0]
sage: ParkingFunction([4,1,1,1]).to_area_sequence()
[0, 1, 2, 0]
sage: ParkingFunction([2,1,4,1]).to_area_sequence()
[0, 1, 1, 0]
Return the support Dyck word of the parking function.
INPUT:
OUTPUT:
See also
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5])
sage: PF.to_dyck_word()
[1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0]
sage: ParkingFunction([3,1,1,4]).to_dyck_word()
[1, 1, 0, 0, 1, 0, 1, 0]
sage: ParkingFunction([4,1,1,1]).to_dyck_word()
[1, 1, 1, 0, 0, 0, 1, 0]
sage: ParkingFunction([2,1,4,1]).to_dyck_word()
[1, 1, 0, 1, 0, 0, 1, 0]
Return the labelled Dyck word corresponding to the parking function.
This is a representation of the parking function as a list where the entries of 1 in the Dyck word are replaced with the corresponding label.
INPUT:
OUTPUT:
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5])
sage: PF.to_labelled_dyck_word()
[2, 6, 0, 4, 5, 0, 0, 0, 3, 7, 0, 1, 0, 0]
sage: ParkingFunction([3,1,1,4]).to_labelled_dyck_word()
[2, 3, 0, 0, 1, 0, 4, 0]
sage: ParkingFunction([4,1,1,1]).to_labelled_dyck_word()
[2, 3, 4, 0, 0, 0, 1, 0]
sage: ParkingFunction([2,1,4,1]).to_labelled_dyck_word()
[2, 4, 0, 1, 0, 0, 3, 0]
Return a pair consisting of a labelling and an area sequence of a Dyck path which corresponds to the given parking function.
INPUT:
OUTPUT:
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5])
sage: PF.to_labelling_area_sequence_pair()
([2, 6, 4, 5, 3, 7, 1], [0, 1, 1, 2, 0, 1, 1])
sage: ParkingFunction([1, 1, 1]).to_labelling_area_sequence_pair()
([1, 2, 3], [0, 1, 2])
sage: ParkingFunction([1, 2, 3]).to_labelling_area_sequence_pair()
([1, 2, 3], [0, 0, 0])
sage: ParkingFunction([1, 1, 2]).to_labelling_area_sequence_pair()
([1, 2, 3], [0, 1, 1])
sage: ParkingFunction([1, 1, 3, 1]).to_labelling_area_sequence_pair()
([1, 2, 4, 3], [0, 1, 2, 1])
Return the pair (L, D) where L is a labelling and D is the Dyck word of the parking function.
INPUT:
OUTPUT:
See also
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5])
sage: PF.to_labelling_dyck_word_pair()
([2, 6, 4, 5, 3, 7, 1], [1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0])
sage: ParkingFunction([3,1,1,4]).to_labelling_dyck_word_pair()
([2, 3, 1, 4], [1, 1, 0, 0, 1, 0, 1, 0])
sage: ParkingFunction([4,1,1,1]).to_labelling_dyck_word_pair()
([2, 3, 4, 1], [1, 1, 1, 0, 0, 0, 1, 0])
sage: ParkingFunction([2,1,4,1]).to_labelling_dyck_word_pair()
([2, 4, 1, 3], [1, 1, 0, 1, 0, 0, 1, 0])
Return the labelling of the support Dyck path of the parking function.
INPUT:
OUTPUT:
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5])
sage: PF.to_labelling_permutation()
[2, 6, 4, 5, 3, 7, 1]
sage: ParkingFunction([3,1,1,4]).to_labelling_permutation()
[2, 3, 1, 4]
sage: ParkingFunction([4,1,1,1]).to_labelling_permutation()
[2, 3, 4, 1]
sage: ParkingFunction([2,1,4,1]).to_labelling_permutation()
[2, 4, 1, 3]
Return the composition of the labelled Dyck path corresponding to the parking function.
For example, touch_composition(PF) = [4, 3] means that the first touch is four diagonal units from the starting point, and the second is three units further (see [GXZ] p. 2).
INPUT:
OUTPUT:
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5])
sage: PF.touch_composition()
[4, 3]
sage: ParkingFunction([3,1,1,4]).touch_composition()
[2, 1, 1]
sage: ParkingFunction([4,1,1,1]).touch_composition()
[3, 1]
sage: ParkingFunction([2,1,4,1]).touch_composition()
[3, 1]
Return the sequence of touch points which corresponds to the labelled Dyck path after initial step.
For example, touch_points(PF) = [4, 7] means that after
the initial step, the path touches the main diagonal at points
and
.
INPUT:
OUTPUT:
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5])
sage: PF.touch_points()
[4, 7]
sage: ParkingFunction([3,1,1,4]).touch_points()
[2, 3, 4]
sage: ParkingFunction([4,1,1,1]).touch_points()
[3, 4]
sage: ParkingFunction([2,1,4,1]).touch_points()
[3, 4]
Return the combinatorial class of Parking Functions.
A parking function of size is a sequence
of positive integers such that if
is
the increasing rearrangement of
, then
.
A parking function of size is a pair
of two sequences
and
where
is a permutation and
is an area sequence
of a Dyck Path of size n such that
,
and if
then
.
The number of parking functions of size is equal to the number
of rooted forests on
vertices and is equal to
.
EXAMPLES:
Here are all parking functions of size 3:
sage: from sage.combinat.parking_functions import ParkingFunctions
sage: ParkingFunctions(3).list()
[[1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [1, 1, 3], [1, 3, 1], [3, 1, 1],
[1, 2, 2], [2, 1, 2], [2, 2, 1], [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1],
[3, 1, 2], [3, 2, 1]]
If no size is specified, then ParkingFunctions returns the combinatorial class of all parking functions.
sage: PF = ParkingFunctions(); PF
Parking functions
sage: [] in PF
True
sage: [1] in PF
True
sage: [2] in PF
False
sage: [1,3,1] in PF
True
sage: [1,4,1] in PF
False
If the size is specified, then ParkingFunctions returns
the combinatorial class of all parking functions of size
.
sage: PF = ParkingFunctions(0)
sage: PF.list()
[[]]
sage: PF = ParkingFunctions(1)
sage: PF.list()
[[1]]
sage: PF = ParkingFunctions(3)
sage: PF.list()
[[1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [1, 1, 3],
[1, 3, 1], [3, 1, 1], [1, 2, 2], [2, 1, 2], [2, 2, 1],
[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
sage: PF3 = ParkingFunctions(3); PF3
Parking functions of size 3
sage: [] in PF3
False
sage: [1] in PF3
False
sage: [1,3,1] in PF3
True
sage: [1,4,1] in PF3
False
TESTS:
sage: PF = ParkingFunctions(5)
sage: len(PF.list()) == PF.cardinality()
True
Bases: sage.combinat.combinat.InfiniteAbstractCombinatorialClass
TESTS:
sage: from sage.combinat.parking_functions import ParkingFunctions
sage: DW = ParkingFunctions()
sage: DW == loads(dumps(DW))
True
Bases: sage.combinat.combinat.CombinatorialClass
The combinatorial class of parking functions of size .
A parking function of size is a sequence
of positive integers such that if
is
the increasing rearrangement of
, then
.
A parking function of size is a pair
of two sequences
and
where
is a permutation and
is an area sequence
of a Dyck Path of size
such that
,
and if
then
.
The number of parking functions of size is equal to the number
of rooted forests on
vertices and is equal to
.
EXAMPLES:
sage: PF = ParkingFunctions(3)
sage: PF.list()
[[1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [1, 1, 3],
[1, 3, 1], [3, 1, 1], [1, 2, 2], [2, 1, 2], [2, 2, 1],
[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
sage: [ParkingFunctions(i).cardinality() for i in range(6)]
[1, 1, 3, 16, 125, 1296]
Warning
The precise order in which the parking function are generated or listed is not fixed, and may change in the future.
Return the number of parking functions of size n.
The cardinality is equal to .
EXAMPLES:
sage: [ParkingFunctions(i).cardinality() for i in range(6)]
[1, 1, 3, 16, 125, 1296]
Return a random parking function of size .
The algorithm uses a circular parking space with
spots. Then all
cars can park and there remains one empty
spot. Spots are then renumbered so that the empty spot is
.
The probability distribution is uniform on the set of
parking functions of size
.
EXAMPLES:
sage: pf = ParkingFunctions(8)
sage: a = pf.random_element(); a # random
[5, 7, 2, 4, 2, 5, 1, 3]
sage: a in pf
True
Return the parking function corresponding to the labelled Dyck word.
INPUT:
OUTPUT:
EXAMPLES:
sage: from sage.combinat.parking_functions import from_labelled_dyck_word
sage: LDW = [2, 6, 0, 4, 5, 0, 0, 0, 3, 7, 0, 1, 0, 0]
sage: from_labelled_dyck_word(LDW)
[6, 1, 5, 2, 2, 1, 5]
sage: from_labelled_dyck_word([2, 3, 0, 0, 1, 0, 4, 0])
[3, 1, 1, 4]
sage: from_labelled_dyck_word([2, 3, 4, 0, 0, 0, 1, 0])
[4, 1, 1, 1]
sage: from_labelled_dyck_word([2, 4, 0, 1, 0, 0, 3, 0])
[2, 1, 4, 1]
Return the parking function corresponding to the labelling area sequence pair.
INPUT:
OUTPUT:
EXAMPLES:
sage: from sage.combinat.parking_functions import from_labelling_and_area_sequence
sage: from_labelling_and_area_sequence([2, 6, 4, 5, 3, 7, 1], [0, 1, 1, 2, 0, 1, 1])
[6, 1, 5, 2, 2, 1, 5]
sage: from_labelling_and_area_sequence([1, 2, 3], [0, 1, 2])
[1, 1, 1]
sage: from_labelling_and_area_sequence([1, 2, 3], [0, 0, 0])
[1, 2, 3]
sage: from_labelling_and_area_sequence([1, 2, 3], [0, 1, 1])
[1, 1, 2]
sage: from_labelling_and_area_sequence([1, 2, 4, 3], [0, 1, 2, 1])
[1, 1, 3, 1]
Check whether a list is a parking function.
If a size is specified, checks if a list is a parking function
of size
.
TESTS:
sage: from sage.combinat.parking_functions import is_a
sage: is_a([1,1,2])
True
sage: is_a([1,2,1])
True
sage: is_a([1,1,4])
False
sage: is_a([3,1,1], 3)
True