Generalizing parking functions with randomness

DOI10.37236/10884MaRDI QIDQ2161197zbMATH OpenOpenAlexFDO

Authors Melanie Tian, Enrique Treviño

Publication date 4 August 2022

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2111.12850

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

random modelNaples parking function

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorial probability (60C05) Factorials, binomial coefficients, combinatorial functions (05A10) Transportation, logistics and supply chain management (90B06)

Abstract: Consider $n$ cars $C_1,C_2,ldots,C_n$ that want to park in a parking lot with parking spaces $1,2,ldots,n$ that appear in order. Each car $C_i$ has a parking preference $alph{a}_{i}in1,2,ldots,n$. The cars appear in order, if their preferred parking spot is not taken, they take it, if the parking spot is taken, they move forward until they find an empty spot. If they do not find an empty spot, they do not park. An $n$-tuple $(alph{a}_1,alph{a}_2,ldots,alph{a}_n)$ is said to be a parking function, if this list of preferences allows every car to park under this algorithm. For an integer $k$, we say that an $n$-tuple is a $k$-Naples parking function if the cars can park with the modified algorithm, where park $C_i$ backs up $k$-spaces (one by one) if their spot is taken before trying to find a parking spot in front of them. We introduce randomness to this problem in two ways: 1) For the original parking function definition, for each car $C_i$ that has their preference taken, we decide with probability $p$ whether $C_i$ moves forwards or backwards when their preferred spot is taken; 2) For the $k$-Naples definition, for each car $C_i$ that has their preference taken, we decide with probability $p$ whether $C_i$ backs up $k$ spaces or not before moving forward. In each of these models, for an $n$-tuple $alphain{1,2,ldots,n}^n$, there is now a probability that the model ends in all cars parking or not. For each of these random models, we find a formula for the expected value. Furthermore, for the second random model, in the case $k=1$, $p=1/2$, we prove that for any $1letle{2}^{n-2}$, there is exactly one $alphain{1,2,ldots,n}^n$ such that the probability that $alpha$ parks is $(2t-1)/2^{n-1}$.

Recommendations

• Probabilizing parking functions
• A generalization of parking functions allowing backward movement
• Parking functions: from combinatorics to probability
• Generalizations of the parking problem
• Probabilistic parking functions

Cites work

• A generalization of parking functions allowing backward movement
• An Occupancy Discipline and Applications
• Ballots and trees
• Parking Functions: Choose Your Own Adventure
• Parking functions
• Probabilizing parking functions

Cited in

(5)

• Lucky Cars: Expected Values and Generating Functions
• Probabilistic parking functions
• Connecting k-Naples parking functions and obstructed parking functions via involutions
• A generalization of parking functions allowing backward movement
• On Parking Functions and The Tower of Hanoi

This page was built for publication: Generalizing parking functions with randomness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2161197)