Lucky Cars in Fubini Rankings and Unit Fubini Rankings

Camilo Barreto, Melissa Beerbower, Jennifer Elder, Pamela E. Harris, Lucy Martinez, José L. Ramírez, Samuel Ramírez, Grant Shirley, Julio C. Vásquez · 2025

Read Lucky Cars in Fubini Rankings and Unit Fubini Rankings by Camilo Barreto, Melissa Beerbower, Jennifer Elder, Pamela E. Harris, Lucy Martinez, José L. Ramírez, Samuel Ramírez, Grant Shirley, Julio C. Vásquez (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-27574.txt.

Introduction

Camilo Barreto and eight co-authors study lucky cars in ranked lists where ties are allowed in 2025. A Fubini ranking lists ranks for rivals, and a car is lucky if it is the first to show its rank. Unit Fubini rankings form a smaller, stricter family of the same lists.

For both families, the team gives clear traits and exact count formulas for lucky cars. Links are shown to ranked splits of sets and to sums built from whole numbers. Proof tools include counting arguments, direct matchings, repeat rules, and a computer-aided sum method. The results add sharp counts to a playful corner of counting math.

Catalog record

CREATORCamilo Barreto, Melissa Beerbower, Jennifer Elder, Pamela E. Harris, Lucy Martinez, José L. Ramírez, Samuel Ramírez, Grant Shirley, Julio C. Vásquez
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE61 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-27574

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Lucky Cars in Fubini Rankings and Unit Fubini Rankings Camilo Barreto, Melissa Beerbower, Jennifer Elder, Pamela E. Harris, Lucy Martinez, José L. Ramírez, Samuel Ramírez, Grant Shirley, Julio C. Vásquez Abstract . We study lucky cars in subsets of parking functions, called Fubini rankings and unit Fubini rankings. A Fubini ranking is a sequence of nonnegative integers that encodes a valid ranking of competitors, where ties are allowed. A car (or competitor) is said to be lucky if it is the first instance of that rank appearing in the sequence. We present combinatorial characterizations and enumeration formulas for lucky cars in both Fubini rankings and unit Fubini rankings, and establish connections between these objects and ordered set partitions, as well as integer compositions. To obtain our results, we use several techniques to enumerate statistics over these families of objects. In particular, we employ generating functions, bijective and combinatorial arguments, recurrence relations, and Zeilberger’s creative telescoping method. 2010 Mathematics Subject Classification 05A05, 05A15, 05A18. 1. Introduction Throughout, we let {\mathbb{N}}=\{1,2,3,\ldots\} , and for n\in{\mathbb{N}} define [n]=\{1,2,\ldots,n\} . Recall that the set of parking functions of length n , denoted \mathrm{PF}_{n} , is the set of all n -tuples \alpha=(a_{1},a_{2},\ldots,a_{n})\in[n]^{n} whose weakly increasing rearrangement, denoted \alpha^{\uparrow}=(a_{1}^{\prime},a_{2}^{\prime},\ldots,a_{n}^{\prime}) , satisfy a_{i}^{\prime}\leq i for all i\in[n] . Konheim and Weiss, and independently by Pyke, established that |\mathrm{PF}_{n}|=(n+1)^{n-1} , see [ 16 , 21 ] . Another way to describe parking functions is to consider the tuples in the context of cars trying to park on a one-way street. An n -tuple (a_{1},a_{2},\ldots,a_{n})\in[n]^{n} is considered as a list of parking preferences where a_{i} is the preferred parking spot of the i th car. Each car enters the one-way street one at a time, where the parking spots are numbered consecutively, and attempts to park using the following parking rule: • For each i=1,2,\ldots,n , car i with preference a_{i} drives to that spot and parks if it finds that spot available. • If spot a_{i} is unavailable, car i continues down the street and parks in the first available parking spot it encounters. If all cars are able to park on the street using this procedure, the list of preferences is a parking function. For example, the parking function (3,2,4,4,1) parks the cars in the order car 5, car 2, car 1, car 3 and car 4. In comparison, the preference tuple (1,5,5,2,3) fails to be a parking function as car 3 finds its preferred parking spot occupied and there are no further spots on the street in which it can park. After defining a set of combinatorial objects, one natural direction of study is to consider discrete statistics and statistic generating functions on the set. In the realm of parking functions and subsets of parking functions, the lucky statistic is usually one of the first statistics to consider. Studied by Gessel and Seo [ 10 ] , the lucky statistic counts the number of cars that are able to park in their preferred spot, making these cars lucky . We let \mathsf{Lucky}(\alpha) denote the set of lucky cars in the parking function \alpha , and we let \mathsf{lucky}(\alpha)=|\mathsf{Lucky}(\alpha)| , denote the number of lucky cars in \alpha . For example, for the parking function \alpha_{1}=(3,2,4,4,1) , cars 1,2 , 3 , and 5 are lucky, so \mathsf{Lucky}(\alpha_{1})=\{1,2,3,5\} and \mathsf{lucky}(\alpha_{1})=4 . If \alpha_{2}=(1,1,\ldots,1)\in[n]^{n} , then \mathsf{Lucky}(\alpha_{2})=\{1\} , which is the “unluckiest” parking functions since the only car that parks in its preferred spot is car 1 . Permutations of [n] are the “luckiest” parking functions, as every car gets to park in their preference; that is, if \alpha is a permutation of [n] , then \mathsf{Lucky}(\alpha)=[n] and \mathsf{lucky}(\alpha)=n . Gessel and Seo also gave the following generating function for the lucky car statistic on parking functions [ 10 ] : (1) \displaystyle L_{n}(q)=\displaystyle\sum_{\alpha\in\mathrm{PF}_{n}}q^{\mathsf{lucky}(\alpha)}=q\prod_{i=1}^{n-1}(i+(n-i+1)q), and we refer to L_{n}(q) as the lucky polynomial of \mathrm{PF}_{n} . Their work is related to rooted trees, and the proof relies on ordered set partitions and generating function techniques. Slavík and Vestinická in [ 22 , Equation 11] provide an analogous result for ( 1 ) in the case where cars have different sizes. Other work on the lucky statistic on parking functions includes that of Aguillon et al. [ 2 ] , which studies the subset of parking functions with n-1 lucky cars in which the single unlucky car parks precisely one spot away from its preference. They establish a bijection between this subset of parking functions and ideal states in the tower of Hanoi game [ 2 , Theorem 1] . Harris, Kretschmann, and Martínez Mori [ 12 ] , consider the sequences \alpha\in[n]^{n} (not necessarily parking functions) with exactly n-1 lucky cars. They establish that the number of these sequences is equal to the total number of comparisons performed by the Quicksort algorithm given all possible orderings of an array of size n [ 12 ] . Colmenarejo et al. [ 7 ] consider the set of Stirling permutations of order n , which are a subset of parking functions of length 2n . Among, their results they establish that the number of Stirling permutations with maximally many lucky cars (which is n lucky cars) is a Catalan number, and that there are (n-1)! Stirling permutations with exactly one lucky car (that being the first car). Also, Harris and Martinez determined formulas for the number of parking functions with a fixed set of lucky cars [ 13 ] . They first characterized the outcomes permutations of parking functions with a fixed lucky set, and used the characterization and an argument often referred to as “counting through permutations” to enumerate the parking functions with a fixed lucky set. In this article, we study the properties related to lucky cars and lucky statistics in the following three subsets of \mathrm{PF}_{n} : ( \mathrm{FR}_{n} ): The Fubini rankings with n competitors are n -tuples \alpha=(a_{1},a_{2},\ldots,a_{n})\in[n]^{n} that records a valid ranking of n competitors with ties allowed ( Definition 2.1 ) and the set is denoted by \mathrm{FR}_{n} . We let \mathrm{FR}_{n}^{\uparrow} denote the set of weakly increasing Fubini rankings with n competitors. ( \mathrm{UPF}_{n} ): Unit interval parking functions of length n are parking functions of length n in which cars park in their preference or in the spot in front of their preference ( Definition 3.1 ). We let \mathrm{UPF}_{n} denote the set of unit interval parking functions of length n . Hadaway [ 11 ] established a bijection between \mathrm{UPF}_{n} and \mathrm{FR}_{n} . We let \mathrm{UPF}_{n}^{\uparrow} denote the set of weakly increasing unit interval parking functions. ( \mathrm{UFR}_{n} ): The set of unit Fubini rankings with n competitors consists of the intersection between the set of unit interval parking functions and Fubini rankings, and consists of Fubini rankings in which a competitor can tie with at most one other competitor at that rank ( Definition 3.2 ). We denote this set by \mathrm{UFR}_{n} and let \mathrm{UFR}_{n}^{\uparrow} denote the subset consisting of weakly increasing unit Fubini rankings. Section 2 provides results related to Fubini rankings, followed by the results for weakly increasing Fubini rankings. These results are also true for the unit interval parking functions through the bijective map in

Read the complete text