ParkingFunctions
A name from the enumeratio catalogue with no kernel of its own yet; this page carries its crosswalk only.
Catalogued in the enumeratio database, with crosswalk rows in oeis, sage, wikipedia; not yet written up here.
Wikipedia
Parking functionWikidataQ109037852OEISA000272SageMathsage.combinat.parking_functions.ParkingFunctions(n)ParkingFunctions(...)Catalogued in the enumeratio database, with crosswalk rows in oeis, sage, wikipedia; not yet written up here.Typed signatures
| Type | Package | Applies |
|---|---|---|
(integer<0..>) -> indexed_collection<parking_function> | combinatorics | always |
Definition
Epsil, as the implementation runs it.
count(_n)
0 if _n < 0 else 1 if _n == 0 else (_n + 1) ^ (_n - 1)unrank(_n, _r)
Drop(Fold(
Function(Apply((uh: list<integer>) => Apply(
(uv: list<integer>) => Join(
[uv[1]],
Fold(
Function(ReplaceAt(pe, pj, uh[pj] +
(1 if pj >= uv[3] else 0)), pe, pj),
uh,
Range(1, _n, 1),
),
Drop(us, _n + 1),
[uv[3]],
),
Fold(
Function(ua if ua[2] ==
1 else Apply(
(uc: integer) => [ua[1], 1, uw] if ua[1] < uc else [ua[1] - uc, 0, 0],
Fold(
Function(Apply((pq: list<integer>) => Fold(
Function(ReplaceAt(
pn,
ps + 1,
0 if ps <
pk -
(uh[pk] +
(1 if pk >= uw else 0)) else Fold(Function(pa +
Binomial(ps, pc) *
pq[ps - pc +
1], pa, pc), 0, Range(0, ps, 1)),
), pn, ps),
Map(Function(0, pz), Range(1, _n - ui +
1, 1)),
Range(0, _n - ui, 1),
), pf), pf, pk),
Join([1], Map(
Function(0, pz),
Range(1, _n - ui, 1),
)),
Range(1, _n, 1),
)[_n - ui +
1],
), ua, uw),
[us[1], 0, 0],
Range(1, _n, 1),
),
), Take(Drop(us, 1), _n)), us, ui),
Join([_r], Map(Function(0, pz), Range(1, _n, 1))),
Range(1, _n, 1),
), _n + 1)rank(_n, _x)
Fold(
Function(Apply((rh: list<integer>) => Apply(
(rt: integer) => Join(
[rs[1] +
rt],
Fold(
Function(ReplaceAt(pe, pj, rh[pj] +
(1 if pj >= _x[ri] else 0)), pe, pj),
rh,
Range(1, _n, 1),
),
),
Fold(
Function(rc +
Fold(
Function(Apply((pq: list<integer>) => Fold(
Function(ReplaceAt(
pn,
ps + 1,
0 if ps <
pk -
(rh[pk] +
(1 if pk >= rw else 0)) else Fold(Function(pa +
Binomial(ps, pc) *
pq[ps - pc +
1], pa, pc), 0, Range(0, ps, 1)),
), pn, ps),
Map(
Function(0, pz),
Range(1, _n - ri +
1, 1),
),
Range(0, _n - ri, 1),
), pf), pf, pk),
Join(
[1],
Map(
Function(0, pz),
Range(1, _n - ri, 1),
),
),
Range(1, _n, 1),
)[_n - ri +
1], rc, rw),
0,
Range(1, _x[ri] - 1, 1),
),
), Drop(rs, 1)), rs, ri),
Join([0], Map(Function(0, pz), Range(1, _n, 1))),
Range(1, _n, 1),
)[1]valid(_n, _x)
Length(_x) == _n && Fold(Function(
ok_vj && 1 <= _x[vj] && _x[vj] <= _n,
ok_vj,
vj,
), True, Range(1, Length(_x), 1)) && Fold(
Function(ok_vk &&
Fold(
Function(vc +
(1 if _x[vi] <= vk else 0), vc, vi),
0,
Range(1, Length(_x), 1),
) >=
vk, ok_vk, vk),
True,
Range(1, _n, 1),
)Statistics
On ParkingFunction, called as CombinatorialStat(x, "Name").
- CenterSizeSt001937The length of the longest subsequence a(1), ..., a(k) with a(i) <= i.
- CriticalLeftToRightMaximaSt000942The entries p that are left to right maxima with exactly p - 1 entries smaller and n - p larger.
- DeficienciesSt001905Positions i with p(i) < i.
- InitialIncreasingSegmentLengthSt001904The length of the initial strictly increasing segment.
- LuckyCarsSt000135The cars that park in the spot they prefer.
- MaximalParkingDisplacementSt000943The most spots any car drives past its preferred spot.
- SumLessLengthSt000540The sum of the preferences less their number.
- TiesSt001947Positions i with p(i) = p(i+1).
- TotalParkingDisplacementSt000188The sum, over the cars, of the spots they drive past: the sum of i - p(i).
Maps
Into and out of ParkingFunction, called as CombinatorialMap(x, "Name"). Properties are the laws we state and what FindStat records.
From ParkingFunction
- CarPermutationParkingFunction → PermutationSurjectionGraded mapMp00053Spot j holds the car that parks there, each car taking the first free spot at or after its preference.
- CyclicShiftParkingFunction → ParkingFunctioninverseBijectionGraded mapMp00293Rotate the word one place to the left: the first entry moves to the end.
- InverseCyclicShiftParkingFunction → ParkingFunctioninverseBijectionGraded mapMp00304Rotate the word one place to the right: the last entry moves to the front.
- LabelingPermutationParkingFunction → PermutationSurjectionGraded mapMp00055The labeling of the parking function's support Dyck path: the positions of the entries, smallest entry first and equal entries left to right.
- ReverseParkingFunction → ParkingFunctioninvolutionBijectionGraded mapInvolutionMp00320The word read backwards.
- SupportDyckPathParkingFunction → DyckPathSurjectionGraded mapMp00056The Dyck path whose area sequence is j minus the j-th smallest entry: the parking function's support.
13 more in FindStat, not implemented here
- Mp00052ParkingFunction → ParkingFunctionIdempotentGraded mapto non-decreasing parking function
- Mp00054ParkingFunction → IntegerCompositionSurjectionGraded mapto inverse des composition
- Mp00057ParkingFunction → IntegerCompositionSurjectionGraded mapto touch composition
- Mp00290ParkingFunction → SetCompositionSurjectionGraded mapto ordered set partition
- Mp00297ParkingFunction → OrderedTreeSurjectionGraded mapordered tree
- Mp00298ParkingFunction → ParkingFunctionBijectionGraded maprepeats to leading
- Mp00299ParkingFunction → ParkingFunctionBijectionGraded mapones to leading
- Mp00300ParkingFunction → ParkingFunctionBijectionGraded mapleading to ones
- Mp00301ParkingFunction → ParkingFunctionBijectionGraded mapleading to repeats
- Mp00302ParkingFunction → SemistandardTableauGraded mapinsertion tableau
- Mp00303ParkingFunction → ParkingFunctionBijectionGraded mapInvolutioncomplement
- Mp00305Permutation → ParkingFunctionInjectionGraded mapparking function
- Mp00319ParkingFunction → IntegerCompositionInjectionto composition