Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEnumerating $k$-Naples Parking Functions Through Catalan Objects
127
0
0.0
(
0
)
Added by
Andr\\'es R. Vindas-Mel\\'endez
Publication date
2021
fields
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
This paper studies a generalization of parking functions named $k$-Naples parking functions, where backward movement is allowed. One consequence of backward movement is that the number of ascending $k$-Naples is not the same as the number of descending $k$-Naples. This paper focuses on generalizing the bijections of ascending parking functions with combinatorial objects enumerated by the Catalan numbers in the setting of both ascending and descending $k$-Naples parking functions. These combinatorial objects include Dyck paths, binary trees, triangulations of polygons, and non-crossing partitions. Using these bijections, we enumerate both ascending and descending $k$-Naples parking functions.
rate research
Read More
We recall that the $k$-Naples parking functions of length $n$ (a generalization of parking functions) are defined by requiring that a car which finds its preferred spot occupied must first back up a spot at a time (up to $k$ spots) before proceeding forward down the street. Note that the parking functions are the specialization of $k$ to $0$. For a fixed $0leq kleq n-1$, we define a function $varphi_k$ which maps a $k$-Naples parking function to the permutation denoting the order in which its cars park. By enumerating the sizes of the fibers of the map $varphi_k$ we give a new formula for the number of $k$-Naples parking functions as a sum over the permutations of length $n$. We remark that our formula for enumerating $k$-Naples parking functions is not recursive, in contrast to the previously known formula of Christensen et al [CHJ+20]. It can be expressed as the product of the lengths of particular subsequences of permutations, and its specialization to $k=0$ gives a new way to describe the number of parking functions of length $n$. We give a formula for the sizes of the fibers of the map $varphi_0$, and we provide a recurrence relation for its corresponding logarithmic generating function. Furthermore, we relate the $q$-analog of our formula to a new statistic that we denote $texttt{area}_k$ and call the $k$-Naples area statistic, the specialization of which to $k=0$ gives the $texttt{area}$ statistic on parking functions.
The classical parking functions, counted by the Cayley number (n+1)^(n-1), carry a natural permutation representation of the symmetric group S_n in which the number of orbits is the nth Catalan number. In this paper, we will generalize this setup to rational parking functions indexed by a pair (a,b) of coprime positive integers. We show that these parking functions, which are counted by b^(a-1), carry a permutation representation of S_a in which the number of orbits is a rational Catalan number. We compute the Frobenius characteristic of the S_a-module of (a,b)-parking functions. Next we propose a combinatorial formula for a q-analogue of the rational Catalan numbers and relate this formula to a new combinatorial model for q-binomial coefficients. Finally, we discuss q,t-analogues of rational Catalan numbers and parking functions (generalizing the shuffle conjecture for the classical case) and present several conjectures.
Given a strictly increasing sequence $mathbf{t}$ with entries from $[n]:={1,ldots,n}$, a parking completion is a sequence $mathbf{c}$ with $|mathbf{t}|+|mathbf{c}|=n$ and $|{tin mathbf{t}mid tle i}|+|{cin mathbf{c}mid cle i}|ge i$ for all $i$ in $[n]$. We can think of $mathbf{t}$ as a list of spots already taken in a street with $n$ parking spots and $mathbf{c}$ as a list of parking preferences where the $i$-th car attempts to park in the $c_i$-th spot and if not available then proceeds up the street to find the next available spot, if any. A parking completion corresponds to a set of preferences $mathbf{c}$ where all cars park. We relate parking completions to enumerating restricted lattice paths and give formulas for both the ordered and unordered variations of the problem by use of a pair of operations termed textbf{Join} and textbf{Split}. Our results give a new volume formula for most Pitman-Stanley polytopes, and enumerate the signature parking functions of Ceballos and Gonzalez DLeon.
We study Schroder paths drawn in a (m,n) rectangle, for any positive integers m and n. We get explicit enumeration formulas, closely linked to those for the corresponding (m,n)-Dyck paths. Moreover we study a Schroder version of (m,n)-parking functions, and associated (q,t)-analogs.
For each skew shape we define a nonhomogeneous symmetric function, generalizing a construction of Pak and Postnikov. In two special cases, we show that the coefficients of this function when expanded in the complete homogeneous basis are given in terms of the (reduced) type of $k$-divisible noncrossing partitions. Our work extends Haimans notion of a parking function symmetric function.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
