betaFeedback

WorksMathematics

Pattern avoidance classes of parking permutations with fixed lucky sets

Abstract

For a parking function, the resulting sequence after all cars have parked is called the associated parking permutation. For each parking function, cars that park in their preferred spot are called lucky cars. In this paper, we enumerate parking permutations that avoid a specified set of permutation patterns in S3\mathfrak{S}_3 and whose lucky cars are the first kk cars. Often, the enumeration simplifies to a product of a fraction with a binomial coefficient, recovering existing sequences in the OEIS. For two of the classes, the enumerations are new sequences.

Introduction

Parking functions have been central to many active areas of research since they were implicitly studied by Pyke [20] and later on by Konheim and Weiss [18]. As integer sequences associated to permutations, questions of statistics and pattern avoidance for these sequences have also been popular in the literature. One such statistic is the lucky statistic for parking functions. This statistic is closely related to descents and ties, and these are of interest partially due to their algebraic and geometric connections; for example, descents in tieless parking functions have been studied in connection with the Chow polynomial of the noncrossing partition lattice [3, 7], and for vector parking functions with a specified parking protocol, Avila, Ferroni, and Morales recently demonstrated that the lucky statistic appears in a combinatorial interpretation of coefficients for the Ehrhart polynomial of the Pitman–Stanley polytope corresponding to a vector [4 Theorem 1.1]. For other statistics on parking functions, see for example [10, 23], and for a survey on parking functions, see Yan [26].

The study of the lucky statistic for parking functions began with the work of Gessel and Seo, who provided a polynomial expression for the generating function that enumerates parking functions with a fixed number of lucky cars [12 Theorem 10.1]. Later, Shin provided a bijection that maps labeled forests with a certain number of leaders to parking functions with the same number of lucky cars [24]. Harris and Martinez gave a characterization for the set of parking permutations arising from parking functions with a fixed set of lucky cars [16]. More recently, Ferreri, Harris, Martinez, and Swartz proved that every parking permutation admits a decomposition into ∣I∣|I| increasing subsequences, where each subsequence begins with an element of the lucky set II [11]. The lucky statistic was also considered by Colmenarejo et al. [8], who studied Stirling permutations as parking functions and considered the question of how many Stirling permutations have certain lucky sets. For more work on the lucky statistic and its connections, see [6, 15, 25].

Pattern avoidance in parking functions has also been studied in different contexts. Motivated by Remmel and Qiu [21], Adeniran and Pudwell studied pattern avoidance in parking functions by viewing parking functions as labeled Dyck paths [2]. They enumerated parking functions avoiding any set of two or more patterns of length 3, and Adenbaum later completed the enumeration for all single patterns of length 3 [1]. Another notion of pattern avoidance in parking functions was studied by Yan [27]. In this version, Yan studied the parking permutation map, which is the order in which the cars ultimately park on the street, and enumerated all parking functions whose parking permutations avoid any collection of patterns of length three.

Motivated by recent results on pattern avoidance and the lucky statistic for parking functions, we investigate the following question: given a fixed lucky set I=[k]I=[k], what structure is imposed on parking permutations with lucky set II that avoid a prescribed pattern? In the present work, we provide a solution to this question for classical patterns of length 3, and show that the resulting parking permutations admit a structure in terms of ascent and descent statistics of the permutation induced by the lucky cars. Our main enumeration results are as follows. For four of the patterns, the enumeration matched existing sequences in the OEIS [17].

Theorem 3.6 (Lobb numbers, OEIS A039599). The number of parking permutations of length nn that avoid the pattern 123 with lucky set I={1,2,…,k}I=\{1,2,\ldots,k\} is given by

2n−2k+1n+1(2kn).\frac{2n-2k+1}{n+1}\binom{2k}{n}.

Theorem 3.12. Let k≥2k \ge2. The number of parking permutations of length nn that avoid the pattern 321 with lucky set I={1,2,…,k}I=\{1,2,\ldots,k\} is given by

∑i=0n−k(n−ki)((n−i−k+2n−i+1)(n−i+k−1k−1)−(n−i−2k−1)).\sum_{i=0}^{n-k}\binom{n-k}{i}\left(\binom{n-i-k+2}{n-i+1}\binom{n-i+k-1}{k-1}-\binom{n-i-2}{k-1}\right).

Theorems 3.17, 3.27, 3.31 (Catalan’s triangle (read by rows), OEIS A009766). The number of parking permutations of length nn that avoid the pattern 213, or the pattern 231, or the pattern 132, with lucky set I={1,2,…,k}I=\{1,2,\ldots,k\} is given by

n−k+2n+1(n+k−1k−1).\frac{n-k+2}{n+1}\binom{n+k-1}{k-1}.

Theorem 3.22. The number of parking permutations of length nn that avoid the pattern 312 with lucky set I={1,2,…,k}I=\{1,2,\ldots,k\} is given by

n−k+1n+1(n+kk)−(n−1k).\frac{n-k+1}{n+1}\binom{n+k}{k}-\binom{n-1}{k}.

Tables of values for each of these formulas are given in Appendix § 8.

Definitions and notation

Let n∈N={1,2,…}n \in\mathbb{N}=\{1,2,\ldots\}. A parking function of length nn is an integer sequence α=(a1,a2,…,an)\alpha=(a_1,a_2,\ldots,a_n) whose nondecreasing rearrangement (a(1),a(2),…,a(n))(a_{(1)},a_{(2)},\ldots,a_{(n)}) satisfies a(i)≤ia_{(i)} \le i for each 1≤i≤n1 \le i \le n. Such sequences are named for their interpretation in terms of cars parking in a one-way street: the entry aia_i indicates the preferred parking spot of the iith car. Each car first attempts to park in its preferred spot, and if that spot is not available, checks each subsequent spot in order until it finds an available spot, and parks there. The sequence is considered a parking function only if all cars are able to park under this protocol. We let PFn\mathrm{PF}_n denote the set of parking functions of length nn.

Once all nn cars have parked, the resulting arrangement of cars is called the outcome, or parking permutation corresponding to the parking function α\alpha. Let [n]={1,2,…,n}[n]=\{1,2,\ldots,n\} and let Sn\mathcal{S}_n denote the set of permutations of [n][n]. Then the parking permutation of a parking function α\alpha is denoted by

O(α)=π1π2⋯πn.O(\alpha)=\pi_1\pi_2\cdots\pi_n.

where πi\pi_i is the car that parked in spot ii. If a car parks in its preferred spot, that car is said to be lucky; otherwise it is unlucky. For a given parking function α\alpha, we denote by Lucky⁡(α)\operatorname{Lucky}(\alpha) the set of all lucky cars in α\alpha, and define lucky⁡(α)=∣Lucky⁡(α)∣\operatorname{lucky}(\alpha)=|\operatorname{Lucky}(\alpha)|.

A permutation σ∈Sn\sigma\in\mathcal{S}_n is said to have an ascent at position ii if σi<σi+1\sigma_i < \sigma_{i+1}, and σ\sigma has a descent at position ii if σi>σi+1\sigma_i > \sigma_{i+1}. Harris and Martinez proved that in the parking permutation of a given parking function, the location of the descents force certain cars to be in the lucky set [16 Lemma 2.2]. Moreover, the first car to prefer spot 1 will park there; hence that car is a lucky car [16 Theorem 2.3]. These facts are key for our results, and for convenience, we rephrase them below.

Lemma 2.1 ([16], Lemma 2.2). Fix a lucky set I⊆[n]I \subseteq[n] of PFn\mathrm{PF}_n. Let π∈Sn\pi\in\mathcal{S}_n be the parking permutation of a parking function with lucky set II. If π\pi has a descent at position jj, then πj+1∈I\pi_{j+1} \in I. Consequently, if u∉Iu \notin I then uu cannot be directly preceded by any v>uv>u.

Lemma 2.2 ([16], Theorem 2.3). Fix a lucky set I⊆[n]I \subseteq[n] of PFn\mathrm{PF}_n. If π∈Sn\pi\in\mathcal{S}_n is the parking permutation of a parking function of length nn with lucky set II, then π1∈I\pi_1 \in I.

We denote by On(I)O_n(I) the set of parking permutations of length nn corresponding to any parking function with lucky set II. That is,

On(I)={σ∈Sn:σ=O(α) where Lucky⁡(α)=I}.O_n(I)=\{\sigma\in\mathcal{S}_n:\sigma=O(\alpha)\text{ where }\operatorname{Lucky}(\alpha)=I\}.

Throughout this paper, we restrict our results to the case where I={1,2,…,k}I=\{1,2,\ldots,k\}, with k≤nk \le n.

Let σ∈Sm\sigma\in\mathfrak{S}_m. A permutation π∈Sn\pi\in\mathfrak{S}_n is said to contain σ\sigma as a pattern if there is a length-mm subsequence of π\pi whose entries appear in the same relative order as the entries in σ\sigma. Otherwise, π\pi is said to avoid σ\sigma. Let Π={σ1,σ2,…,σi}\Pi= \{\sigma_1, \sigma_2, \ldots, \sigma_i\} be a collection of patterns and let Av⁡n(Π)\operatorname{Av}_n(\Pi) be the set of permutations that avoid all patterns in the set Π\Pi. For more background on pattern avoidance, see Bóna [5, Chapter 4].

Let On(I;σ1,σ2,…,σi)\mathcal{O}_n(I; \sigma_1, \sigma_2, \ldots, \sigma_i) denote the set of parking permutations with lucky set II that avoid each of the patterns σ1,σ2,…,σi\sigma_1, \sigma_2, \ldots, \sigma_i. Although there are Catalan many permutations that avoid a single pattern of length 33, not every such permutation arises as a parking permutation with a fixed set of lucky cars. This is illustrated in the following example.

Example 2.3. Let n=5n = 5 and I={1,2,3}I = \{1, 2, 3\}. We check that O5(I;123)⊊Av⁡5(123)\mathcal{O}_5(I; 123) \subsetneq\operatorname{Av}_5(123). Indeed, consider π=35412∈Av⁡5(123)\pi= 35412 \in\operatorname{Av}_5(123). Since there is a descent at position i=2i = 2, by Lemma 2.1 car 44 must belong to the set II. Hence, 35412∉O5(I;123)35412 \notin\mathcal{O}_5(I; 123).

In some of our results, we make use of the following result by Connolly, Gabor, and Godbole, who considered the question of how many permutations avoid the pattern 123123 and whose first ascent occurs at position kk.

Theorem 2.4 (Connolly, Gabor, and Godbole [9]). The number of 123123-avoiding permutations of length nn whose first ascent occurs at position kk is given by the kk-fold Catalan convolution Cn,kC_{n,k}, where

Cn,k=∑i1+⋯+ik=n,ij≥1∏r=1kCir−1=k2n−k(2n−kn),Cn=1n+1(2nn).C_{n,k} = \sum_{\substack{i_1+\cdots+i_k=n,\\ i_j\geq1}} \prod_{r=1}^{k} C_{i_r-1} = \frac{k}{2n-k}\binom{2n-k}{n}, \qquad C_n = \frac{1}{n+1}\binom{2n}{n}.

Parking permutation decomposition avoiding a single pattern of length three

The following alternative definition of On(I;σ1,σ2,…,σi)\mathcal{O}_n(I; \sigma_1, \sigma_2, \ldots, \sigma_i) gives a characterization of the elements in this set. The first two criteria are shown to be necessary in Theorem 2.3 of [16].

Definition 3.1. Fix a lucky set I⊆[n]I \subseteq[n]. Then π=π1π2⋯πn∈Sn\pi= \pi_1\pi_2 \cdots\pi_n \in\mathfrak{S}_n is in On(I;σ1,σ2,…,σi)\mathcal{O}_n(I; \sigma_1, \sigma_2, \ldots, \sigma_i) if and only if

  1. π1∈I\pi_1 \in I,

  2. if πi−1>πi\pi_{i-1} > \pi_i, then πi∈I\pi_i \in I, and

  3. π\pi avoids each of the patterns σ1,σ2,…,σi\sigma_1, \sigma_2, \ldots, \sigma_i.

Example 3.2. Let n=5n = 5 and I={1,2,3}I = \{1, 2, 3\}. If σ=123\sigma= 123 then

O5(I;123)={25143,32514,35142,35214,35241}.\mathcal{O}_5(I; 123) = \{25143, 32514, 35142, 35214, 35241\}.

Note that there are 4242 permutations that avoid the pattern 123123 of length 55, while the set of 123123-avoiding parking permutations with lucky set II contains only 55 elements.

As a different example, if σ=321\sigma= 321, then the set O5(I;321)\mathcal{O}_5(I; 321) contains the following 3232 elements,

References

  1. [1]Ben Adenbaum, Enumerating pattern avoiding parking functions, 2026. arXiv:2605.24092.arxiv.org/abs/2605.24092
  2. [2]Ayomikun Adeniran and Lara Pudwell, Pattern avoidance in parking functions, Enumer. Comb. Appl. 3 (2023), no. 3, Paper No. S2R17, 21. DOI: 10.54550/eca2023v3s3r17.DOI
  3. [3]Per Alexandersson, Real-rootedness and interlacing for parking functions and chow polynomials, 2026. arXiv:2609.05131.
  4. [4]Nicolas Avila, Luis Ferroni, and Alejandro H. Morales, Luck and magic for pitman-stanley polytopes and parking functions, 2026. arXiv:2603.19194.arxiv.org/abs/2603.19194
  5. [6]Steve Butler, Kimberly Hadaway, Victoria Lenius Preston, Stewart Martens, and Marshall Moats, Lucky cars and lucky spots in parking functions, J. Integer Seq. 29 (2026), no. 1, Art. 26.1.1, 18.
  6. [7]Joseph Chun, Natsuka Hayashida, Ethan Partida, and Zhixing Wang, The chow polynomial of the noncrossing partition lattice, 2026. arXiv:2608.03806.arxiv.org/abs/2608.03806
  7. [8]Laura Colmenarejo, Aleyah Dawkins, Jennifer Elder, Pamela E. Harris, Kimberly J. Harry, Selvi Kara, Dorian Smith, and Bridget Eileen Tenner, On the lucky and displacement statistics of Stirling permutations, J. Integer Seq. 27 (2024), no. 6, Article 24.6.7.arxiv.org/abs/2403.03280
  8. [9]Samuel Connolly, Zachary Gabor, and Anant Godbole, The location of the first ascent in a 123-avoiding permutation, Integers 15 (2015), Paper No. A13, 8. DOI: 10.5281/zenodo.10456132.arxiv.org/abs/1401.2691
  9. [10]Ari Cruz, Pamela E. Harris, Kimberly J. Harry, Jan Kretschmann, Matt McClinton, Alex Moon, and John O. Museus, On some discrete statistics of parking functions, J. Integer Seq. 27 (2024), no. 8, Art. 24.8.6, 34.arxiv.org/abs/2312.16786
  10. [11]Melanie Ferreri, Pamela E. Harris, Lucy Martinez, and Eric Swartz, Enumerating vector parking functions and their outcomes based on specified lucky cars, 2025. arXiv:2508.13917.arxiv.org/abs/2508.13917
  11. [12]Ira M. Gessel and Seunghyun Seo, A refinement of Cayley’s formula for trees, Electron. J. Combin. 11 (2004/06), no. 2, Research Paper 27, 23. DOI: 10.37236/1884.
  12. [13]H. W. Gould, New convolution identities for Vandermonde’s convolution, Amer. Math. Monthly 63 (1956), 84–91. DOI: 10.2307/2306429.
  13. [14]Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete mathematics, Second, Addison-Wesley Publishing Company, Reading, MA, 1994. A foundation for computer science.
  14. [15]Pamela E. Harris, Jan Kretschmann, and J. Carlos Martínez Mori, Lucky cars and the quicksort algorithm, Amer. Math. Monthly 131 (2024), no. 5, 417–423. DOI: 10.1080/00029890.2024.2309103.DOI
  15. [16]Pamela E. Harris and Lucy Martinez, Parking functions with a fixed set of lucky cars, Bull. Inst. Combin. Appl. 108 (2026), 104–150.
  16. [17]OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, 2026. Published electronically at http://oeis.org.
  17. [18]Alan G. Konheim and Benjamin Weiss, An occupancy discipline and applications, SIAM J. Appl. Math. 14 (1966), no. 6, 1266–1274.DOI
  18. [19]Peter J. Larcombe and David R. French, The Catalan number k-fold self-convolution identity: the original formulation, J. Combin. Math. Combin. Comput. 46 (2003), 191–204. 15th MCCCC (Las Vegas, NV, 2001).
  19. [20]Ronald Pyke, The supremum and infimum of the Poisson process, Ann. Math. Statist. 30 (1959), 568–576. DOI: 10.1214/aoms/1177706269.DOI
  20. [21]Dun Qiu and Jeffrey Remmel, Patterns in words of ordered set partitions, J. Comb. 10 (2019), no. 3, 433–490. DOI: 10.4310/JOC.2019.v10.n3.a2.DOI
  21. [22]Alon Regev, A proof of Catalan’s convolution formula, Integers 12 (2012), no. 5, 929–934. DOI: 10.1515/integers-2012-0014.DOI
  22. [23]Paul R. F. Schumacher, Descents in parking functions, J. Integer Seq. 21 (2018), no. 2, Art. 18.2.3, 8.
  23. [24]Heesung Shin, A new bijection between forests and parking functions, 2008. arXiv:0810.0427.arxiv.org/abs/0810.0427
  24. [25]Antonín Slavík and Marie Vestenická, Lucky cars: expected values and generating functions, Amer. Math. Monthly 131 (2024), no. 4, 343–348. DOI: 10.1080/00029890.2023.2293616.DOI
  25. [26]Catherine H. Yen, Parking functions, Handbook of enumerative combinatorics, 2015, pp. 835–893.
  26. [27]Jun Yan, Results on pattern avoidance in parking functions, Enumer. Comb. Appl. 5 (2025), no. 1, Paper No. S2R2, 29. DOI: 10.54550/eca2025v5s1r2.DOI

Paper details

vlnc:W_2x5kufsk
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents