Parking Functions#
INFORMALLY (reference [Beck]):
Imagine a one-way cul-de-sac with \(n\) parking spots. We will give the first parking spot the number 1, the next one number 2, etc., down to the last one, number \(n\). Initially they are all free, but there are \(n\) 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 \(n = 3\), the sequence \((2, 1, 1)\) 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 \(n\)) if all cars end up finding a parking spot. For example, the sequence \((2, 1, 1)\) is a parking sequence (of length 3), whereas the sequence \((2, 3, 2)\) is not.
FORMALLY:
A parking function of size \(n\) is a sequence \((a_1, \ldots, a_n)\) of positive integers such that if \(b_1 \leq b_2 \leq \cdots \leq b_n\) is the increasing rearrangement of \(a_1, \ldots, a_n\), then \(b_i \leq i\).
A parking function of size \(n\) is a pair \((L, D)\) of two sequences \(L\) and \(D\) where \(L\) is a permutation and \(D\) is an area sequence of a Dyck path of size n such that \(D[i] \geq 0\), \(D[i+1] \leq D[i]+1\) and if \(D[i+1] = D[i]+1\) then \(L[i+1] > L[i]\).
The number of parking functions of size \(n\) is equal to the number of rooted forests on \(n\) vertices and is equal to \((n+1)^{n-1}\).
REFERENCES:
M. Beck, Stanford Math Circle - Parking Functions, October 2010, http://math.stanford.edu/circle/parkingBeck.pdf
The \(q,t\) – Catalan Numbers and the Space of Diagonal Harmonics: With an Appendix on the Combinatorics of Macdonald Polynomials, James Haglund, University of Pennsylvania, Philadelphia – AMS, 2008, 167 pp.
H. Shin, Forests and Parking Functions, slides from talk September 24, 2008, http://www.emis.de/journals/SLC/wpapers/s61vortrag/shin.pdf
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)
- sage.combinat.parking_functions.PF[source]#
alias of
ParkingFunction
- class sage.combinat.parking_functions.ParkingFunction(parent, lst)[source]#
Bases:
ClonableArray
A Parking Function.
A parking function of size \(n\) is a sequence \((a_1, \ldots,a_n)\) of positive integers such that if \(b_1 \leq b_2 \leq \cdots \leq b_n\) is the increasing rearrangement of \(a_1, \ldots, a_n\), then \(b_i \leq i\).
A parking function of size \(n\) is a pair \((L, D)\) of two sequences \(L\) and \(D\) where \(L\) is a permutation and \(D\) is an area sequence of a Dyck Path of size \(n\) such that \(D[i] \geq 0\), \(D[i+1] \leq D[i]+1\) and if \(D[i+1] = D[i]+1\) then \(L[i+1] > L[i]\).
The number of parking functions of size \(n\) is equal to the number of rooted forests on \(n\) vertices and is equal to \((n+1)^{n-1}\).
INPUT:
pf
– (default:None
) a list whose increasing rearrangement satisfies \(b_i \leq i\)labelling
– (default:None
) a labelling of the Dyck patharea_sequence
– (default:None
) an area sequence of a Dyck pathlabelled_dyck_word
– (default:None
) a Dyck word with 1’s replaced by labelling
OUTPUT:
A parking function
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]
>>> from sage.all import * >>> ParkingFunction([]) [] >>> ParkingFunction([Integer(1)]) [1] >>> ParkingFunction([Integer(2)]) Traceback (most recent call last): ... ValueError: [2] is not a parking function >>> ParkingFunction([Integer(1),Integer(2)]) [1, 2] >>> ParkingFunction([Integer(1),Integer(1),Integer(2)]) [1, 1, 2] >>> ParkingFunction([Integer(1),Integer(4),Integer(1)]) Traceback (most recent call last): ... ValueError: [1, 4, 1] is not a parking function >>> ParkingFunction(labelling=[Integer(3),Integer(1),Integer(2)], area_sequence=[Integer(0),Integer(0),Integer(1)]) [2, 2, 1] >>> ParkingFunction([Integer(2),Integer(2),Integer(1)]).to_labelled_dyck_word() [3, 0, 1, 2, 0, 0] >>> ParkingFunction(labelled_dyck_word=[Integer(3),Integer(0),Integer(1),Integer(2),Integer(0),Integer(0)]) [2, 2, 1] >>> ParkingFunction(labelling=[Integer(3),Integer(1),Integer(2)], area_sequence=[Integer(0),Integer(1),Integer(1)]) Traceback (most recent call last): ... ValueError: [3, 1, 2] is not a valid labeling of area sequence [0, 1, 1]
- area()[source]#
Return the area of the labelled Dyck path corresponding to the parking function.
OUTPUT:
the sum of squares under and over the main diagonal the Dyck Path, corresponding to the parking function
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5]) sage: PF.area() 6
>>> from sage.all import * >>> PF = ParkingFunction([Integer(6), Integer(1), Integer(5), Integer(2), Integer(2), Integer(1), Integer(5)]) >>> 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
>>> from sage.all import * >>> ParkingFunction([Integer(3),Integer(1),Integer(1),Integer(4)]).area() 1 >>> ParkingFunction([Integer(4),Integer(1),Integer(1),Integer(1)]).area() 3 >>> ParkingFunction([Integer(2),Integer(1),Integer(4),Integer(1)]).area() 2
- cars_permutation()[source]#
Return the sequence of cars that take parking spots 1 through \(n\) 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.OUTPUT:
the permutation of cars corresponding to the parking function and which is the same size as parking function
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5]) sage: PF.cars_permutation() [2, 4, 5, 6, 3, 1, 7]
>>> from sage.all import * >>> PF = ParkingFunction([Integer(6), Integer(1), Integer(5), Integer(2), Integer(2), Integer(1), Integer(5)]) >>> 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]
>>> from sage.all import * >>> ParkingFunction([Integer(3),Integer(1),Integer(1),Integer(4)]).cars_permutation() [2, 3, 1, 4] >>> ParkingFunction([Integer(4),Integer(1),Integer(1),Integer(1)]).cars_permutation() [2, 3, 4, 1] >>> ParkingFunction([Integer(2),Integer(1),Integer(4),Integer(1)]).cars_permutation() [2, 1, 4, 3]
- characteristic_quasisymmetric_function(q=None, R=Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field)[source]#
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 \(q^{dinv(PF)} F_{ides(PF)}\) where \(ides(PF)\) (
ides_composition()
) is the descent composition of diagonal reading word of the parking function.INPUT:
q
– (default:q = R('q')
) a parameter for the generating function powerR
– (default:R = QQ['q','t'].fraction_field()
) the base ring to do the calculations over
OUTPUT:
an element of the quasisymmetric functions over the ring
R
EXAMPLES:
sage: # needs sage.modules 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]
>>> from sage.all import * >>> # needs sage.modules >>> R = QQ['q','t'].fraction_field() >>> (q,t) = R.gens() >>> cqf = sum(t**PF.area() * PF.characteristic_quasisymmetric_function() ... for PF in ParkingFunctions(Integer(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] >>> s = SymmetricFunctions(R).s() >>> 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] >>> s(cqf.to_symmetric_function()).nabla(power=-Integer(1)) s[1, 1, 1]
sage: p = ParkingFunction([3, 1, 2]) sage: p.characteristic_quasisymmetric_function() # needs sage.modules q*F[2, 1] sage: pf = ParkingFunction([1,2,7,2,1,2,3,2,1]) sage: pf.characteristic_quasisymmetric_function() # needs sage.modules q^2*F[1, 1, 1, 2, 1, 3]
>>> from sage.all import * >>> p = ParkingFunction([Integer(3), Integer(1), Integer(2)]) >>> p.characteristic_quasisymmetric_function() # needs sage.modules q*F[2, 1] >>> pf = ParkingFunction([Integer(1),Integer(2),Integer(7),Integer(2),Integer(1),Integer(2),Integer(3),Integer(2),Integer(1)]) >>> pf.characteristic_quasisymmetric_function() # needs sage.modules q^2*F[1, 1, 1, 2, 1, 3]
- check()[source]#
Check that
self
is a valid parking function.EXAMPLES:
sage: PF = ParkingFunction([1, 1, 2, 2, 5, 6]) sage: PF.check()
>>> from sage.all import * >>> PF = ParkingFunction([Integer(1), Integer(1), Integer(2), Integer(2), Integer(5), Integer(6)]) >>> PF.check()
- diagonal_composition()[source]#
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).OUTPUT:
the length between the corresponding touch points which of the labelled Dyck path that corresponds to the parking function
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5]) sage: PF.touch_composition() [4, 3]
>>> from sage.all import * >>> PF = ParkingFunction([Integer(6), Integer(1), Integer(5), Integer(2), Integer(2), Integer(1), Integer(5)]) >>> 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]
>>> from sage.all import * >>> ParkingFunction([Integer(3),Integer(1),Integer(1),Integer(4)]).touch_composition() [2, 1, 1] >>> ParkingFunction([Integer(4),Integer(1),Integer(1),Integer(1)]).touch_composition() [3, 1] >>> ParkingFunction([Integer(2),Integer(1),Integer(4),Integer(1)]).touch_composition() [3, 1]
- diagonal_reading_word()[source]#
Return a diagonal word of the labelled Dyck path corresponding to parking function (see [Hag08] p. 75).
OUTPUT:
returns a word, read diagonally from NE to SW of the pretty print of the labelled Dyck path that corresponds to
self
and the same size asself
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5]) sage: PF.diagonal_reading_word() [5, 1, 7, 4, 6, 3, 2]
>>> from sage.all import * >>> PF = ParkingFunction([Integer(6), Integer(1), Integer(5), Integer(2), Integer(2), Integer(1), Integer(5)]) >>> 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]
>>> from sage.all import * >>> ParkingFunction([Integer(1), Integer(1), Integer(1)]).diagonal_reading_word() [3, 2, 1] >>> ParkingFunction([Integer(1), Integer(2), Integer(3)]).diagonal_reading_word() [3, 2, 1] >>> ParkingFunction([Integer(1), Integer(1), Integer(3), Integer(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]
>>> from sage.all import * >>> ParkingFunction([Integer(1), Integer(1), Integer(1)]).diagonal_word() [3, 2, 1] >>> ParkingFunction([Integer(1), Integer(2), Integer(3)]).diagonal_word() [3, 2, 1] >>> ParkingFunction([Integer(1), Integer(4), Integer(3), Integer(1)]).diagonal_word() [4, 2, 3, 1]
- diagonal_word()[source]#
Return a diagonal word of the labelled Dyck path corresponding to parking function (see [Hag08] p. 75).
OUTPUT:
returns a word, read diagonally from NE to SW of the pretty print of the labelled Dyck path that corresponds to
self
and the same size asself
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5]) sage: PF.diagonal_reading_word() [5, 1, 7, 4, 6, 3, 2]
>>> from sage.all import * >>> PF = ParkingFunction([Integer(6), Integer(1), Integer(5), Integer(2), Integer(2), Integer(1), Integer(5)]) >>> 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]
>>> from sage.all import * >>> ParkingFunction([Integer(1), Integer(1), Integer(1)]).diagonal_reading_word() [3, 2, 1] >>> ParkingFunction([Integer(1), Integer(2), Integer(3)]).diagonal_reading_word() [3, 2, 1] >>> ParkingFunction([Integer(1), Integer(1), Integer(3), Integer(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]
>>> from sage.all import * >>> ParkingFunction([Integer(1), Integer(1), Integer(1)]).diagonal_word() [3, 2, 1] >>> ParkingFunction([Integer(1), Integer(2), Integer(3)]).diagonal_word() [3, 2, 1] >>> ParkingFunction([Integer(1), Integer(4), Integer(3), Integer(1)]).diagonal_word() [4, 2, 3, 1]
- dinv()[source]#
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()
.OUTPUT:
the number of dinversion pairs
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5]) sage: PF.dinv() 6
>>> from sage.all import * >>> PF = ParkingFunction([Integer(6), Integer(1), Integer(5), Integer(2), Integer(2), Integer(1), Integer(5)]) >>> 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
>>> from sage.all import * >>> ParkingFunction([Integer(3),Integer(1),Integer(1),Integer(4)]).dinv() 3 >>> ParkingFunction([Integer(4),Integer(1),Integer(1),Integer(1)]).dinv() 1 >>> ParkingFunction([Integer(2),Integer(1),Integer(4),Integer(1)]).dinv() 2
- dinversion_pairs()[source]#
Return the descent inversion pairs of a labelled Dyck path corresponding to the parking function.
OUTPUT:
the primary and secondary diversion pairs
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)]
>>> from sage.all import * >>> PF = ParkingFunction([Integer(6), Integer(1), Integer(5), Integer(2), Integer(2), Integer(1), Integer(5)]) >>> 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)]
>>> from sage.all import * >>> ParkingFunction([Integer(3),Integer(1),Integer(1),Integer(4)]).dinversion_pairs() [(0, 3), (2, 3), (1, 2)] >>> ParkingFunction([Integer(4),Integer(1),Integer(1),Integer(1)]).dinversion_pairs() [(1, 3)] >>> ParkingFunction([Integer(2),Integer(1),Integer(4),Integer(1)]).dinversion_pairs() [(0, 3), (1, 3)]
- grade()[source]#
Return the length of the parking function.
EXAMPLES:
sage: PF = ParkingFunction([1, 1, 2, 2, 5, 6]) sage: PF.grade() 6
>>> from sage.all import * >>> PF = ParkingFunction([Integer(1), Integer(1), Integer(2), Integer(2), Integer(5), Integer(6)]) >>> PF.grade() 6
- ides()[source]#
Return the
descents()
sequence of the inverse of thediagonal_reading_word()
ofself
.Warning
Here we use the standard convention that descent labels start at \(1\). This behaviour has been changed in Issue #20555.
For example,
ides(PF) = [2, 3, 4, 6]
means that descents are at the 2nd, 3rd, 4th and 6th positions in the inverse of thediagonal_reading_word()
of the parking function (see [GXZ] p. 2).OUTPUT:
the descents sequence of the inverse of the
diagonal_reading_word()
of the parking function
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5]) sage: PF.ides() [2, 3, 4, 6]
>>> from sage.all import * >>> PF = ParkingFunction([Integer(6), Integer(1), Integer(5), Integer(2), Integer(2), Integer(1), Integer(5)]) >>> PF.ides() [2, 3, 4, 6]
sage: ParkingFunction([3,1,1,4]).ides() [2] sage: ParkingFunction([4,1,1,1]).ides() [2, 3] sage: ParkingFunction([4,3,1,1]).ides() [3]
>>> from sage.all import * >>> ParkingFunction([Integer(3),Integer(1),Integer(1),Integer(4)]).ides() [2] >>> ParkingFunction([Integer(4),Integer(1),Integer(1),Integer(1)]).ides() [2, 3] >>> ParkingFunction([Integer(4),Integer(3),Integer(1),Integer(1)]).ides() [3]
- ides_composition()[source]#
Return the
descents_composition()
of the inverse of thediagonal_reading_word()
of corresponding parking function.For example,
ides_composition(PF) = [4, 2, 1]
means that the descents of the inverse of the permutationdiagonal_reading_word()
of the parking function with wordPF
are at the 4th and 6th positions.OUTPUT:
the descents composition of the inverse of the
diagonal_reading_word()
of the parking function
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5]) sage: PF.ides_composition() [2, 1, 1, 2, 1]
>>> from sage.all import * >>> PF = ParkingFunction([Integer(6), Integer(1), Integer(5), Integer(2), Integer(2), Integer(1), Integer(5)]) >>> 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]
>>> from sage.all import * >>> ParkingFunction([Integer(3),Integer(1),Integer(1),Integer(4)]).ides_composition() [2, 2] >>> ParkingFunction([Integer(4),Integer(1),Integer(1),Integer(1)]).ides_composition() [2, 1, 1] >>> ParkingFunction([Integer(4),Integer(3),Integer(1),Integer(1)]).ides_composition() [3, 1]
- jump()[source]#
Return the sum of the differences between the parked and preferred parking spots.
See [Shin] p. 18.
OUTPUT:
the sum of the differences between the parked and preferred parking spots
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5]) sage: PF.jump() 6
>>> from sage.all import * >>> PF = ParkingFunction([Integer(6), Integer(1), Integer(5), Integer(2), Integer(2), Integer(1), Integer(5)]) >>> 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
>>> from sage.all import * >>> ParkingFunction([Integer(3),Integer(1),Integer(1),Integer(4)]).jump() 1 >>> ParkingFunction([Integer(4),Integer(1),Integer(1),Integer(1)]).jump() 3 >>> ParkingFunction([Integer(2),Integer(1),Integer(4),Integer(1)]).jump() 2
- jump_list()[source]#
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.OUTPUT:
the displacements sequence of parked cars which corresponds to the parking function and which is the same size as parking function
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5]) sage: PF.jump_list() [0, 0, 0, 0, 1, 3, 2]
>>> from sage.all import * >>> PF = ParkingFunction([Integer(6), Integer(1), Integer(5), Integer(2), Integer(2), Integer(1), Integer(5)]) >>> 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]
>>> from sage.all import * >>> ParkingFunction([Integer(3),Integer(1),Integer(1),Integer(4)]).jump_list() [0, 0, 1, 0] >>> ParkingFunction([Integer(4),Integer(1),Integer(1),Integer(1)]).jump_list() [0, 0, 1, 2] >>> ParkingFunction([Integer(2),Integer(1),Integer(4),Integer(1)]).jump_list() [0, 0, 0, 2]
- luck()[source]#
Return the number of cars that parked in their preferred parking spots (see [Shin] p. 33).
OUTPUT:
the number of cars that parked in their preferred parking spots
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5]) sage: PF.luck() 4
>>> from sage.all import * >>> PF = ParkingFunction([Integer(6), Integer(1), Integer(5), Integer(2), Integer(2), Integer(1), Integer(5)]) >>> 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
>>> from sage.all import * >>> ParkingFunction([Integer(3),Integer(1),Integer(1),Integer(4)]).luck() 3 >>> ParkingFunction([Integer(4),Integer(1),Integer(1),Integer(1)]).luck() 2 >>> ParkingFunction([Integer(2),Integer(1),Integer(4),Integer(1)]).luck() 3
- lucky_cars()[source]#
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.OUTPUT:
the cars that can park in their preferred spots
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5]) sage: PF.lucky_cars() [1, 2, 3, 4]
>>> from sage.all import * >>> PF = ParkingFunction([Integer(6), Integer(1), Integer(5), Integer(2), Integer(2), Integer(1), Integer(5)]) >>> 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]
>>> from sage.all import * >>> ParkingFunction([Integer(3),Integer(1),Integer(1),Integer(4)]).lucky_cars() [1, 2, 4] >>> ParkingFunction([Integer(4),Integer(1),Integer(1),Integer(1)]).lucky_cars() [1, 2] >>> ParkingFunction([Integer(2),Integer(1),Integer(4),Integer(1)]).lucky_cars() [1, 2, 3]
- parking_permutation()[source]#
Return the sequence of parking spots that are taken by cars 1 through \(n\) 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.OUTPUT:
the permutation of parking spots that corresponds to the parking function and which is the same size as parking function
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5]) sage: PF.parking_permutation() [6, 1, 5, 2, 3, 4, 7]
>>> from sage.all import * >>> PF = ParkingFunction([Integer(6), Integer(1), Integer(5), Integer(2), Integer(2), Integer(1), Integer(5)]) >>> 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]
>>> from sage.all import * >>> ParkingFunction([Integer(3),Integer(1),Integer(1),Integer(4)]).parking_permutation() [3, 1, 2, 4] >>> ParkingFunction([Integer(4),Integer(1),Integer(1),Integer(1)]).parking_permutation() [4, 1, 2, 3] >>> ParkingFunction([Integer(2),Integer(1),Integer(4),Integer(1)]).parking_permutation() [2, 1, 4, 3]
- pretty_print(underpath=True)[source]#
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:
underpath
– if the length of the parking function is less than or equal to 9 then display the labels under the path ifunderpath
is True otherwise display them to the right of the path (default:True
)
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
>>> from sage.all import * >>> PF = ParkingFunction([Integer(6), Integer(1), Integer(5), Integer(2), Integer(2), Integer(1), Integer(5)]) >>> PF.pretty_print() ___ _|1x |7x . _____|3 . . |5x x . . . _|4x . . . . |6x . . . . . |2 . . . . . . >>> PF = ParkingFunction([Integer(6), Integer(1), Integer(5), Integer(2), Integer(2), Integer(1), Integer(5)]) >>> 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
>>> from sage.all import * >>> ParkingFunction([Integer(3), Integer(1), Integer(1), Integer(4)]).pretty_print() _ _|4 ___|1 . |3x . . |2 . . . >>> ParkingFunction([Integer(1),Integer(1),Integer(1)]).pretty_print() _____ |3x x |2x . |1 . . >>> ParkingFunction([Integer(4),Integer(1),Integer(1),Integer(1)]).pretty_print() _ _____|1 |4x x . |3x . . |2 . . . >>> ParkingFunction([Integer(2),Integer(1),Integer(4),Integer(1)]).pretty_print() _ ___|3 _|1x . |4x . . |2 . . . >>> ParkingFunction([Integer(2),Integer(1),Integer(4),Integer(1)]).pretty_print(underpath = false) _ ___| 3 _| x . 1 | x . . 4 | . . . 2 >>> pf = ParkingFunction([Integer(1),Integer(2),Integer(3),Integer(7),Integer(3),Integer(2),Integer(1),Integer(2),Integer(3),Integer(2),Integer(1)]) >>> 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
- primary_dinversion_pairs()[source]#
Return the primary descent inversion pairs of a labelled Dyck path corresponding to the parking function.
OUTPUT:
the pairs \((i, j)\) such that \(i < j\), and \(i^{th}\) area = \(j^{th}\) area, and \(i^{th}\) label < \(j^{th}\) label
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5]) sage: PF.primary_dinversion_pairs() [(0, 4), (1, 5), (2, 5)]
>>> from sage.all import * >>> PF = ParkingFunction([Integer(6), Integer(1), Integer(5), Integer(2), Integer(2), Integer(1), Integer(5)]) >>> 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)]
>>> from sage.all import * >>> ParkingFunction([Integer(3),Integer(1),Integer(1),Integer(4)]).primary_dinversion_pairs() [(0, 3), (2, 3)] >>> ParkingFunction([Integer(4),Integer(1),Integer(1),Integer(1)]).primary_dinversion_pairs() [] >>> ParkingFunction([Integer(2),Integer(1),Integer(4),Integer(1)]).primary_dinversion_pairs() [(0, 3)]
- secondary_dinversion_pairs()[source]#
Return the secondary descent inversion pairs of a labelled Dyck path corresponding to the parking function.
OUTPUT:
the pairs \((i, j)\) such that \(i < j\), and \(i^{th}\) area = \(j^{th}\) area +1, and \(i^{th}\) label > \(j^{th}\) label
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5]) sage: PF.secondary_dinversion_pairs() [(1, 4), (2, 4), (3, 6)]
>>> from sage.all import * >>> PF = ParkingFunction([Integer(6), Integer(1), Integer(5), Integer(2), Integer(2), Integer(1), Integer(5)]) >>> 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)]
>>> from sage.all import * >>> ParkingFunction([Integer(3),Integer(1),Integer(1),Integer(4)]).secondary_dinversion_pairs() [(1, 2)] >>> ParkingFunction([Integer(4),Integer(1),Integer(1),Integer(1)]).secondary_dinversion_pairs() [(1, 3)] >>> ParkingFunction([Integer(2),Integer(1),Integer(4),Integer(1)]).secondary_dinversion_pairs() [(1, 3)]
- to_NonDecreasingParkingFunction()[source]#
Return the non-decreasing parking function which underlies the parking function.
OUTPUT:
a sorted parking function
See also
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5]) sage: PF.to_NonDecreasingParkingFunction() [1, 1, 2, 2, 5, 5, 6]
>>> from sage.all import * >>> PF = ParkingFunction([Integer(6), Integer(1), Integer(5), Integer(2), Integer(2), Integer(1), Integer(5)]) >>> 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]
>>> from sage.all import * >>> ParkingFunction([Integer(3),Integer(1),Integer(1),Integer(4)]).to_NonDecreasingParkingFunction() [1, 1, 3, 4] >>> ParkingFunction([Integer(4),Integer(1),Integer(1),Integer(1)]).to_NonDecreasingParkingFunction() [1, 1, 1, 4] >>> ParkingFunction([Integer(2),Integer(1),Integer(4),Integer(1)]).to_NonDecreasingParkingFunction() [1, 1, 2, 4] >>> ParkingFunction([Integer(4),Integer(1),Integer(2),Integer(1)]).to_NonDecreasingParkingFunction() [1, 1, 2, 4]
- to_area_sequence()[source]#
Return the area sequence of the support Dyck path of the parking function.
OUTPUT:
the area sequence of the Dyck path
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5]) sage: PF.to_area_sequence() [0, 1, 1, 2, 0, 1, 1]
>>> from sage.all import * >>> PF = ParkingFunction([Integer(6), Integer(1), Integer(5), Integer(2), Integer(2), Integer(1), Integer(5)]) >>> 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]
>>> from sage.all import * >>> ParkingFunction([Integer(3),Integer(1),Integer(1),Integer(4)]).to_area_sequence() [0, 1, 0, 0] >>> ParkingFunction([Integer(4),Integer(1),Integer(1),Integer(1)]).to_area_sequence() [0, 1, 2, 0] >>> ParkingFunction([Integer(2),Integer(1),Integer(4),Integer(1)]).to_area_sequence() [0, 1, 1, 0]
- to_dyck_word()[source]#
Return the support Dyck word of the parking function.
OUTPUT:
the Dyck word of the corresponding parking function
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]
>>> from sage.all import * >>> PF = ParkingFunction([Integer(6), Integer(1), Integer(5), Integer(2), Integer(2), Integer(1), Integer(5)]) >>> 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]
>>> from sage.all import * >>> ParkingFunction([Integer(3),Integer(1),Integer(1),Integer(4)]).to_dyck_word() [1, 1, 0, 0, 1, 0, 1, 0] >>> ParkingFunction([Integer(4),Integer(1),Integer(1),Integer(1)]).to_dyck_word() [1, 1, 1, 0, 0, 0, 1, 0] >>> ParkingFunction([Integer(2),Integer(1),Integer(4),Integer(1)]).to_dyck_word() [1, 1, 0, 1, 0, 0, 1, 0]
- to_labelled_dyck_word()[source]#
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.
OUTPUT:
the labelled Dyck word of the corresponding parking function which is twice the size of parking function word
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]
>>> from sage.all import * >>> PF = ParkingFunction([Integer(6), Integer(1), Integer(5), Integer(2), Integer(2), Integer(1), Integer(5)]) >>> 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]
>>> from sage.all import * >>> ParkingFunction([Integer(3),Integer(1),Integer(1),Integer(4)]).to_labelled_dyck_word() [2, 3, 0, 0, 1, 0, 4, 0] >>> ParkingFunction([Integer(4),Integer(1),Integer(1),Integer(1)]).to_labelled_dyck_word() [2, 3, 4, 0, 0, 0, 1, 0] >>> ParkingFunction([Integer(2),Integer(1),Integer(4),Integer(1)]).to_labelled_dyck_word() [2, 4, 0, 1, 0, 0, 3, 0]
- to_labelling_area_sequence_pair()[source]#
Return a pair consisting of a labelling and an area sequence of a Dyck path which corresponds to the given parking function.
OUTPUT:
returns a pair
(L, D)
whereL
is a labelling andD
is the area sequence of the underlying Dyck path
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])
>>> from sage.all import * >>> PF = ParkingFunction([Integer(6), Integer(1), Integer(5), Integer(2), Integer(2), Integer(1), Integer(5)]) >>> 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])
>>> from sage.all import * >>> ParkingFunction([Integer(1), Integer(1), Integer(1)]).to_labelling_area_sequence_pair() ([1, 2, 3], [0, 1, 2]) >>> ParkingFunction([Integer(1), Integer(2), Integer(3)]).to_labelling_area_sequence_pair() ([1, 2, 3], [0, 0, 0]) >>> ParkingFunction([Integer(1), Integer(1), Integer(2)]).to_labelling_area_sequence_pair() ([1, 2, 3], [0, 1, 1]) >>> ParkingFunction([Integer(1), Integer(1), Integer(3), Integer(1)]).to_labelling_area_sequence_pair() ([1, 2, 4, 3], [0, 1, 2, 1])
- to_labelling_dyck_word_pair()[source]#
Return the pair
(L, D)
whereL
is a labelling andD
is the Dyck word of the parking function.OUTPUT:
the pair
(L, D)
, whereL
is the labelling andD
is the Dyck word of the parking function
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])
>>> from sage.all import * >>> PF = ParkingFunction([Integer(6), Integer(1), Integer(5), Integer(2), Integer(2), Integer(1), Integer(5)]) >>> 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])
>>> from sage.all import * >>> ParkingFunction([Integer(3),Integer(1),Integer(1),Integer(4)]).to_labelling_dyck_word_pair() ([2, 3, 1, 4], [1, 1, 0, 0, 1, 0, 1, 0]) >>> ParkingFunction([Integer(4),Integer(1),Integer(1),Integer(1)]).to_labelling_dyck_word_pair() ([2, 3, 4, 1], [1, 1, 1, 0, 0, 0, 1, 0]) >>> ParkingFunction([Integer(2),Integer(1),Integer(4),Integer(1)]).to_labelling_dyck_word_pair() ([2, 4, 1, 3], [1, 1, 0, 1, 0, 0, 1, 0])
- to_labelling_permutation()[source]#
Return the labelling of the support Dyck path of the parking function.
OUTPUT:
the labelling of the Dyck path
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5]) sage: PF.to_labelling_permutation() [2, 6, 4, 5, 3, 7, 1]
>>> from sage.all import * >>> PF = ParkingFunction([Integer(6), Integer(1), Integer(5), Integer(2), Integer(2), Integer(1), Integer(5)]) >>> 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]
>>> from sage.all import * >>> ParkingFunction([Integer(3),Integer(1),Integer(1),Integer(4)]).to_labelling_permutation() [2, 3, 1, 4] >>> ParkingFunction([Integer(4),Integer(1),Integer(1),Integer(1)]).to_labelling_permutation() [2, 3, 4, 1] >>> ParkingFunction([Integer(2),Integer(1),Integer(4),Integer(1)]).to_labelling_permutation() [2, 4, 1, 3]
- touch_composition()[source]#
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).OUTPUT:
the length between the corresponding touch points which of the labelled Dyck path that corresponds to the parking function
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5]) sage: PF.touch_composition() [4, 3]
>>> from sage.all import * >>> PF = ParkingFunction([Integer(6), Integer(1), Integer(5), Integer(2), Integer(2), Integer(1), Integer(5)]) >>> 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]
>>> from sage.all import * >>> ParkingFunction([Integer(3),Integer(1),Integer(1),Integer(4)]).touch_composition() [2, 1, 1] >>> ParkingFunction([Integer(4),Integer(1),Integer(1),Integer(1)]).touch_composition() [3, 1] >>> ParkingFunction([Integer(2),Integer(1),Integer(4),Integer(1)]).touch_composition() [3, 1]
- touch_points()[source]#
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 \((4, 4)\) and \((7, 7)\).OUTPUT:
the sequence of touch points after the initial step of the labelled Dyck path that corresponds to the parking function
EXAMPLES:
sage: PF = ParkingFunction([6, 1, 5, 2, 2, 1, 5]) sage: PF.touch_points() [4, 7]
>>> from sage.all import * >>> PF = ParkingFunction([Integer(6), Integer(1), Integer(5), Integer(2), Integer(2), Integer(1), Integer(5)]) >>> 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]
>>> from sage.all import * >>> ParkingFunction([Integer(3),Integer(1),Integer(1),Integer(4)]).touch_points() [2, 3, 4] >>> ParkingFunction([Integer(4),Integer(1),Integer(1),Integer(1)]).touch_points() [3, 4] >>> ParkingFunction([Integer(2),Integer(1),Integer(4),Integer(1)]).touch_points() [3, 4]
- class sage.combinat.parking_functions.ParkingFunctions[source]#
Bases:
UniqueRepresentation
,Parent
Return the combinatorial class of Parking Functions.
A parking function of size \(n\) is a sequence \((a_1, \ldots,a_n)\) of positive integers such that if \(b_1 \leq b_2 \leq \cdots \leq b_n\) is the increasing rearrangement of \(a_1, \ldots, a_n\), then \(b_i \leq i\).
A parking function of size \(n\) is a pair \((L, D)\) of two sequences \(L\) and \(D\) where \(L\) is a permutation and \(D\) is an area sequence of a Dyck Path of size n such that \(D[i] \geq 0\), \(D[i+1] \leq D[i]+1\) and if \(D[i+1] = D[i]+1\) then \(L[i+1] > L[i]\).
The number of parking functions of size \(n\) is equal to the number of rooted forests on \(n\) vertices and is equal to \((n+1)^{n-1}\).
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]]
>>> from sage.all import * >>> from sage.combinat.parking_functions import ParkingFunctions >>> ParkingFunctions(Integer(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
>>> from sage.all import * >>> PF = ParkingFunctions(); PF Parking functions >>> [] in PF True >>> [Integer(1)] in PF True >>> [Integer(2)] in PF False >>> [Integer(1),Integer(3),Integer(1)] in PF True >>> [Integer(1),Integer(4),Integer(1)] in PF False
If the size \(n\) is specified, then ParkingFunctions returns the combinatorial class of all parking functions of size \(n\).
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]]
>>> from sage.all import * >>> PF = ParkingFunctions(Integer(0)) >>> PF.list() [[]] >>> PF = ParkingFunctions(Integer(1)) >>> PF.list() [[1]] >>> PF = ParkingFunctions(Integer(3)) >>> 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
>>> from sage.all import * >>> PF3 = ParkingFunctions(Integer(3)); PF3 Parking functions of size 3 >>> [] in PF3 False >>> [Integer(1)] in PF3 False >>> [Integer(1),Integer(3),Integer(1)] in PF3 True >>> [Integer(1),Integer(4),Integer(1)] in PF3 False
- class sage.combinat.parking_functions.ParkingFunctions_all[source]#
Bases:
ParkingFunctions
- Element[source]#
alias of
ParkingFunction
- graded_component(n)[source]#
Return the graded component.
EXAMPLES:
sage: PF = ParkingFunctions() sage: PF.graded_component(4) == ParkingFunctions(4) True sage: it = iter(ParkingFunctions()) # indirect doctest sage: [next(it) for i in range(8)] [[], [1], [1, 1], [1, 2], [2, 1], [1, 1, 1], [1, 1, 2], [1, 2, 1]]
>>> from sage.all import * >>> PF = ParkingFunctions() >>> PF.graded_component(Integer(4)) == ParkingFunctions(Integer(4)) True >>> it = iter(ParkingFunctions()) # indirect doctest >>> [next(it) for i in range(Integer(8))] [[], [1], [1, 1], [1, 2], [2, 1], [1, 1, 1], [1, 1, 2], [1, 2, 1]]
- class sage.combinat.parking_functions.ParkingFunctions_n(n)[source]#
Bases:
ParkingFunctions
The combinatorial class of parking functions of size \(n\).
A parking function of size \(n\) is a sequence \((a_1, \ldots,a_n)\) of positive integers such that if \(b_1 \leq b_2 \leq \cdots \leq b_n\) is the increasing rearrangement of \(a_1, \ldots, a_n\), then \(b_i \leq i\).
A parking function of size \(n\) is a pair \((L, D)\) of two sequences \(L\) and \(D\) where \(L\) is a permutation and \(D\) is an area sequence of a Dyck Path of size \(n\) such that \(D[i] \geq 0\), \(D[i+1] \leq D[i]+1\) and if \(D[i+1] = D[i]+1\) then \(L[i+1] > L[i]\).
The number of parking functions of size \(n\) is equal to the number of rooted forests on \(n\) vertices and is equal to \((n+1)^{n-1}\).
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]
>>> from sage.all import * >>> PF = ParkingFunctions(Integer(3)) >>> 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]] >>> [ParkingFunctions(i).cardinality() for i in range(Integer(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.
- Element[source]#
alias of
ParkingFunction
- cardinality()[source]#
Return the number of parking functions of size
n
.The cardinality is equal to \((n+1)^{n-1}\).
EXAMPLES:
sage: [ParkingFunctions(i).cardinality() for i in range(6)] [1, 1, 3, 16, 125, 1296]
>>> from sage.all import * >>> [ParkingFunctions(i).cardinality() for i in range(Integer(6))] [1, 1, 3, 16, 125, 1296]
- random_element()[source]#
Return a random parking function of size \(n\).
The algorithm uses a circular parking space with \(n+1\) spots. Then all \(n\) cars can park and there remains one empty spot. Spots are then renumbered so that the empty spot is \(0\).
The probability distribution is uniform on the set of \((n+1)^{n-1}\) parking functions of size \(n\).
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
>>> from sage.all import * >>> pf = ParkingFunctions(Integer(8)) >>> a = pf.random_element(); a # random [5, 7, 2, 4, 2, 5, 1, 3] >>> a in pf True
- sage.combinat.parking_functions.from_labelled_dyck_word(LDW)[source]#
Return the parking function corresponding to the labelled Dyck word.
INPUT:
LDW
– labelled Dyck word
OUTPUT:
the parking function corresponding to the labelled Dyck word that is half the size of
LDW
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]
>>> from sage.all import * >>> from sage.combinat.parking_functions import from_labelled_dyck_word >>> LDW = [Integer(2), Integer(6), Integer(0), Integer(4), Integer(5), Integer(0), Integer(0), Integer(0), Integer(3), Integer(7), Integer(0), Integer(1), Integer(0), Integer(0)] >>> 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]
>>> from sage.all import * >>> from_labelled_dyck_word([Integer(2), Integer(3), Integer(0), Integer(0), Integer(1), Integer(0), Integer(4), Integer(0)]) [3, 1, 1, 4] >>> from_labelled_dyck_word([Integer(2), Integer(3), Integer(4), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0)]) [4, 1, 1, 1] >>> from_labelled_dyck_word([Integer(2), Integer(4), Integer(0), Integer(1), Integer(0), Integer(0), Integer(3), Integer(0)]) [2, 1, 4, 1]
- sage.combinat.parking_functions.from_labelling_and_area_sequence(L, D)[source]#
Return the parking function corresponding to the labelling area sequence pair.
INPUT:
L
– a labelling permutationD
– an area sequence for a Dyck word
OUTPUT:
the parking function corresponding the labelling permutation
L
andD
an area sequence of the corresponding Dyck path
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]
>>> from sage.all import * >>> from sage.combinat.parking_functions import from_labelling_and_area_sequence >>> from_labelling_and_area_sequence([Integer(2), Integer(6), Integer(4), Integer(5), Integer(3), Integer(7), Integer(1)], [Integer(0), Integer(1), Integer(1), Integer(2), Integer(0), Integer(1), Integer(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]
>>> from sage.all import * >>> from_labelling_and_area_sequence([Integer(1), Integer(2), Integer(3)], [Integer(0), Integer(1), Integer(2)]) [1, 1, 1] >>> from_labelling_and_area_sequence([Integer(1), Integer(2), Integer(3)], [Integer(0), Integer(0), Integer(0)]) [1, 2, 3] >>> from_labelling_and_area_sequence([Integer(1), Integer(2), Integer(3)], [Integer(0), Integer(1), Integer(1)]) [1, 1, 2] >>> from_labelling_and_area_sequence([Integer(1), Integer(2), Integer(4), Integer(3)], [Integer(0), Integer(1), Integer(2), Integer(1)]) [1, 1, 3, 1]