Lucky Cars in Fubini Rankings and Unit Fubini Rankings

Basic Information

• Paper ID: 2510.27574
• Title: Lucky Cars in Fubini Rankings and Unit Fubini Rankings
• Authors: Camilo Barreto, Melissa Beerbower, Jennifer Elder, Pamela E. Harris, Lucy Martinez, José L. Ramírez, Samuel Ramírez, Grant Shirley, Julio C. Vásquez
• Classification: math.CO (Combinatorics)
• Submission Date: October 31, 2025 to arXiv
• Paper Link: https://arxiv.org/abs/2510.27574

Abstract

This paper investigates the problem of "lucky cars" in subsets of parking functions, with particular focus on Fubini rankings and unit Fubini rankings. Fubini rankings are sequences of non-negative integers that encode valid rankings of competitors allowing ties. A car (or competitor) is called "lucky" if it is the first instance of its ranking value in the sequence. The paper provides combinatorial characterizations and counting formulas for lucky cars in both classes of rankings, and establishes connections between these objects and ordered set partitions as well as integer compositions. To obtain the results, the authors employ multiple techniques: generating functions, bijections and combinatorial arguments, recurrence relations, and Zeilberger's creative telescoping method.

Research Background and Motivation

Research Questions

The paper addresses the following core questions:

1. Counting lucky cars in Fubini rankings: Given a Fubini ranking of n competitors, how many cars are lucky? How can the set of lucky cars be characterized?
2. Special properties of unit Fubini rankings: As the intersection of Fubini rankings and unit interval parking functions, what combinatorial structures do unit Fubini rankings possess?
3. Enumeration with fixed lucky sets: Given a specific set of lucky cars, how many ranking configurations exist?

Problem Significance

1. Extension of parking function theory: Parking functions are classical objects in combinatorics with deep connections to rooted trees, Catalan numbers, and other structures. The lucky car statistic is one of the fundamental statistics in parking function research.
2. Combinatorial interpretation of Fubini numbers: Fubini numbers (ordered Bell numbers) count ordered set partitions. This paper provides a new combinatorial perspective through Fubini rankings.
3. Applications to algorithm analysis: Harris et al. have shown that the number of sequences with n-1 lucky cars equals the total number of comparisons made by quicksort across all n-element permutations.

Limitations of Existing Methods

1. Complexity of general parking functions: While Gessel and Seo provided the lucky polynomial for general parking functions, research on specific subsets remains insufficient.
2. Lack of systematic study of Fubini rankings: Although Fubini numbers themselves are well-studied, the lucky statistics of Fubini rankings as a subset of parking functions have received limited attention.
3. Unexplored combinatorial significance of unit interval constraints: The lucky statistics of unit interval parking functions have not been systematically investigated.

Research Motivation

This paper aims to systematically study lucky cars in Fubini rankings and their subsets (unit Fubini rankings), establish bijective relationships with ordered set partitions and integer compositions, and provide complete counting formulas and generating functions.

Core Contributions

1. Characterization of lucky cars in Fubini rankings (Theorem 2.3): Proves that lucky cars in Fubini rankings are precisely the first cars in each tied block, and the number of lucky cars equals the number of distinct rankings.
2. Bijection between Fubini rankings and ordered set partitions: Establishes a bijection between Fubini rankings of n competitors with k lucky cars and k-block ordered set partitions of n, yielding $f_{FR}(n,k) = k!S(n,k)$.
3. Recurrence relation (Theorem 2.7): Proves $f_{FR}(n,k) = k(f_{FR}(n-1,k) + f_{FR}(n-1,k-1))$.
4. Concise formula for weakly increasing Fubini rankings (Theorem 2.13): Proves that weakly increasing Fubini rankings satisfy $f^↑_{FR}(n,k) = \binom{n-1}{k-1}$, with total count $2^{n-1}$.
5. Counting formula for unit Fubini rankings (Theorem 3.3): Proves $f_{UFR}(n,k) = \frac{n!}{2^{n-k}}\binom{k}{n-k}$.
6. Connection between weakly increasing unit Fubini rankings and Fibonacci numbers (Theorem 3.12): Proves $|UFR^↑_n| = F_{n+1}$, where $F_n$ is the n-th Fibonacci number.
7. Exponential generating functions: Provides complete exponential generating functions and lucky polynomials for all studied sets.
8. Enumeration with fixed lucky sets: Gives exact counting formulas when the set of lucky cars is fixed (Theorems 2.19 and 3.19).

Detailed Methodology

Task Definitions

Fubini ranking: An n-tuple $\alpha = (a_1, a_2, \ldots, a_n) \in [n]^n$ encoding a valid ranking of n competitors allowing ties. If k competitors share ranking i, the subsequent k-1 rankings $i+1, i+2, \ldots, i+k-1$ are omitted.

Lucky car: Car i is lucky if and only if $a_i \neq a_j$ for all $j < i$, meaning i is the first occurrence of its ranking value.

Unit Fubini ranking: A ranking satisfying both the Fubini ranking condition and the unit interval parking function condition, i.e., each ranking appears at most twice.

Core Methodology

1. Bijection Construction Method

Fubini ranking ↔ Ordered set partition:

Given a Fubini ranking $\alpha = (a_1, \ldots, a_n)$ with k distinct rankings, define blocks: $B_1 = \{j : a_j = 1\}, \quad B_i = \left\{j : a_j = 1 + \sum_{\ell=1}^{i-1}|B_\ell|\right\}$

Conversely, given an ordered partition $(B_1, \ldots, B_k)$, set: $a_i = 1 + \sum_{\ell=1}^{j-1}|B_\ell| \text{ when } i \in B_j$

This bijection preserves the number of lucky cars (equal to the number of blocks k), yielding: $f_{FR}(n,k) = k!S(n,k)$ where $S(n,k)$ is the Stirling number of the second kind.

2. Combinatorial Counting Techniques

Multinomial coefficient method (Theorem 2.6): $f_{FR}(n,k) = \sum_{(c_1,\ldots,c_k) \vdash n} \binom{n}{c_1, c_2, \ldots, c_k}$ where the sum ranges over all k-part compositions of n.

Proof idea: Select $c_1$ positions from n for ranking 1, select $c_2$ positions for ranking $1+c_1$, and so on.

3. Recurrence Relations

Fubini ranking recurrence (Theorem 2.7): $f_{FR}(n,k) = k(f_{FR}(n-1,k) + f_{FR}(n-1,k-1))$

Proof idea: Consider the last car:

• If tied with others: the first n-1 cars form a Fubini ranking with k distinct rankings, and the last car can join any of the k rankings
• If not tied: the first n-1 cars form k-1 rankings, and the last car takes one of k possible positions

4. Generating Function Method

Exponential generating function (Theorem 2.11): $\sum_{n \geq 0} \sum_{k \geq 0} f_{FR}(n,k)q^k \frac{x^n}{n!} = \frac{1}{1-(e^x-1)q}$

Proof uses the exponential generating function for Stirling numbers: $\sum_{n \geq 0} S(n,k)\frac{x^n}{n!} = \frac{(e^x-1)^k}{k!}$

5. Zeilberger's Creative Telescoping Method

For computing the expected value of lucky cars in unit Fubini rankings (Theorem 3.9), Zeilberger's algorithm finds a telescoping proof for hypergeometric terms:

For $F_1(n,k) = 2^k\binom{k}{n-k}$, the algorithm yields a recurrence: $F_1(n+2,k) - 2F_1(n+1,k) - 2F_1(n,k) = G_1(n,k+1) - G_1(n,k)$

Summing yields a recurrence for $f(n)$, which is then solved to obtain the closed form.

Technical Innovations

1. Structural characterization of lucky cars: First proves that lucky cars in Fubini rankings are precisely the first cars in tied blocks, an elegant combinatorial property.
2. Application of restricted Stirling numbers: Introduces restricted ordered set partitions $S_{\leq 2}(n,k)$ (blocks of size ≤2) and establishes connections with unit Fubini rankings.
3. New combinatorial interpretation of Fibonacci numbers: Proves that the number of weakly increasing unit Fubini rankings equals Fibonacci numbers, providing a bijection with integer compositions (parts of 1 or 2).
4. Product formula for fixed lucky sets:
   • Fubini rankings: $|Lucky_{FR_n}(I)| = \prod_{\ell=1}^k \ell^{i_{\ell+1}-i_\ell}$
   • Unit Fubini rankings: $|Lucky_{UFR_n}(I)| = k! \prod_{\ell=1}^{n-k}(u_\ell - 2\ell + 1)$

Experimental Setup

This paper is a pure theoretical combinatorics research without traditional experiments. However, it includes the following verification content:

Computational Verification

1. Small-scale enumeration: For n≤8, explicitly enumerates all Fubini rankings and verifies counting formulas.
2. Array generation: Uses recurrence relations to generate numerical tables for $f_{FR}(n,k)$, $f_{UFR}(n,k)$, etc.
3. OEIS sequence matching: Compares computed results with known sequences in OEIS (Online Encyclopedia of Integer Sequences) for verification.

Example Verification

Complete enumeration of FR₃ (13 elements):

(1,1,1), (1,1,3), (1,3,1), (3,1,1), (1,2,2), (2,1,2), (2,2,1),
(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)

Verification: $|FR_3| = Fub_3 = 13$ ✓

Fixed lucky set example: For $I = \{1,2,5\}$, Theorem 2.19 predicts: $|Lucky_{FR_5}(I)| = 1^{2-1} \cdot 2^{5-2} \cdot 3^{6-5} = 24$ The paper enumerates all 24 rankings, verifying formula correctness.

Experimental Results

Summary of Main Results

Fubini Rankings

Unit Fubini Rankings

Key Findings

1. Asymptotic behavior comparison:
   • Fubini rankings: $E[\text{lucky}] \sim \frac{n}{2\log 2} \approx 0.721n$
   • Weakly increasing Fubini rankings: $E[\text{lucky}] = \frac{n+1}{2}$
   • Unit Fubini rankings: $E[\text{lucky}] \sim 0.634n$
   • Weakly increasing unit Fubini rankings: $E[\text{lucky}] \sim 0.724n$
2. Elegant forms of generating functions:
   • Fubini rankings EGF: $\frac{1}{2-e^x}$ (setting q=1)
   • Unit Fubini rankings EGF: $\frac{1}{1-x-\frac{x^2}{2}}$
   • Weakly increasing Fubini rankings: $\frac{1}{2}(1+e^{2x})$
3. Recurrence properties of lucky polynomials:
   • Weakly increasing Fubini rankings: $L_{FR^↑_n}(q) = q(q+1)^{n-1}$ (extremely simple form)
   • Weakly increasing unit Fubini rankings satisfy: $L_{UFR^↑_{n+2}}(q) = qL_{UFR^↑_{n+1}}(q) + qL_{UFR^↑_n}(q)$

Numerical Examples

Unit Fubini rankings array $[f_{UFR}(n,k)]$ (partial):

n\k   1    2     3     4      5      6
1     1    0     0     0      0      0
2     1    2     0     0      0      0
3     0    6     6     0      0      0
4     0    6    36    24      0      0
5     0    0    90   240    120      0
6     0    0    90  1080   1800    720

Note: This array is new to OEIS and represents a novel discovery of this paper.

Related Work

Parking Function Theory

1. Konheim-Weiss (1966) & Pyke (1959): Established fundamental parking function theory, proving $|PF_n| = (n+1)^{n-1}$.
2. Gessel-Seo (2005): Provided the lucky polynomial for parking functions: $L_n(q) = q\prod_{i=1}^{n-1}(i+(n-i+1)q)$ The Fubini ranking results in this paper generalize this work.
3. Harris-Martinez (2024): Characterized parking functions with fixed lucky sets and their output permutations. This paper extends these results to Fubini rankings.

Fubini Numbers and Ordered Bell Numbers

1. Cayley (1857): Proved $|FR_n| = Fub_n$, establishing connections with rooted trees.
2. Brandt et al. (2024): Introduced r-Fubini rankings, establishing bijections with unit interval parking functions. This paper deepens these connections.

Stirling Number Theory

1. Restricted Stirling numbers $S_{\leq 2}(n,k)$: Jung-Mező-Ramírez (2018) systematically studied set partitions with restricted block sizes. This paper applies these to unit Fubini rankings.

Advantages of This Paper

1. Systematicity: First systematic study of lucky statistics in Fubini rankings with complete counting theory.
2. Technical diversity: Synthesizes multiple combinatorial techniques including bijections, generating functions, recurrences, and Zeilberger's algorithm.
3. Novel connections: Establishes new relationships between unit Fubini rankings, Fibonacci numbers, and restricted compositions.

Conclusions and Discussion

Main Conclusions

1. Structural theorem: Lucky cars in Fubini rankings are precisely the first cars in tied blocks, with the number of lucky cars equaling the number of distinct rankings, which equals the number of blocks in the corresponding ordered set partition.
2. Counting formulas:
   • General Fubini rankings: $f_{FR}(n,k) = k!S(n,k)$
   • Unit Fubini rankings: $f_{UFR}(n,k) = \frac{n!}{2^{n-k}}\binom{k}{n-k}$
   • Weakly increasing variants have more concise formulas
3. Generating function theory: Provides closed forms or recurrence forms for exponential generating functions and lucky polynomials for all studied objects.
4. Asymptotic properties: Expected number of lucky cars exhibits different asymptotic behavior across different sets, ranging from $\sim 0.5n$ to $\sim 0.72n$.

Limitations

1. Theoretical nature: This is pure theoretical research without algorithmic implementation or practical applications.
2. Missing complexity analysis: Does not discuss algorithmic complexity for generating or enumerating these objects.
3. Limited generalization: Primarily focuses on Fubini rankings and unit Fubini rankings; research on ℓ-interval Fubini rankings (ℓ>1) is left for future work.
4. Incomplete probability theory: Provides only expected values; complete probability distributions or variances of lucky car counts are not studied.

Future Directions

The paper explicitly proposes three research directions in Section 4:

1. r-Fubini rankings: Study lucky statistics of r-Fubini rankings (with first r values distinct) as defined by Brandt et al.
2. ℓ-interval Fubini rankings: Investigate lucky properties of ℓ-interval Fubini rankings (cars park at most ℓ positions after preference) introduced by Aguilar-Fraga et al.
3. Restricted variants: Study various restricted Fubini rankings and unit interval parking functions researched by Barreto et al.
4. Implicit directions:
   • Complete distribution and higher moments of lucky car counts
   • Connections with other combinatorial objects (Dyck paths, non-crossing partitions)
   • Algorithmic and computational complexity research

In-Depth Evaluation

Strengths

1. Theoretical depth:
   • Establishes multiple bijections revealing deep connections between Fubini rankings, ordered set partitions, and integer compositions
   • Rigorous and complete proofs employing multiple modern combinatorial techniques
2. Result completeness:
   • Provides counting formulas, recurrence relations, generating functions, and expected values for each studied object
   • Handles both general and weakly increasing cases
   • Includes both total counts and refined counts with fixed lucky sets
3. Methodological innovation:
   • Application of Zeilberger's algorithm demonstrates the power of automated proof methods
   • Elegant combination of combinatorial proofs and generating function methods
4. Clear exposition:
   • Precise definitions with abundant examples
   • Logical progression from simple cases (13 elements of FR₃) to general theory
   • Numerical verification enhances credibility
5. Novel discoveries:
   • The counting array for unit Fubini rankings is new to OEIS
   • Connection between weakly increasing unit Fubini rankings and Fibonacci numbers provides a new combinatorial interpretation

Weaknesses

1. Limited application orientation:
   • Does not discuss practical applications of these theoretical results
   • Connection with Harris et al.'s work on quicksort could be deeper
2. Missing computational complexity:
   • Does not analyze algorithmic efficiency for generating or sampling these objects
   • Enumeration algorithms for fixed lucky sets are not explicitly provided
3. Incomplete distribution theory:
   • Provides only expected values; variance, higher moments, or limiting distributions are not studied
   • Joint distributions with other statistics (inversions, descents) are unexplored
4. Limited generalization:
   • Results for ℓ-interval cases (ℓ>1) are absent
   • Weighted versions or q-analogues are not considered
5. Lack of visualization:
   • Missing graphical representations (Young diagrams, lattice paths) for intuitive understanding of structures

Impact

1. Theoretical contribution:
   • Adds important subset research to parking function theory
   • Provides new combinatorial perspectives on Fubini and Stirling numbers
   • Enriches theory with new Fibonacci number interpretations
2. Methodological contribution:
   • Demonstrates successful synthesis of multiple combinatorial techniques
   • Provides successful case study of Zeilberger's algorithm in combinatorial counting
3. Future research:
   • Explicitly proposed directions promise to generate series of follow-up works
   • Connections with ordered partitions and restricted compositions invite further exploration
4. Practical value:
   • Though theoretical, connections with algorithm analysis (quicksort) suggest potential applications
   • Generating functions could inform random sampling algorithm design

Applicable Scenarios

1. Combinatorics research:
   • Researchers studying parking functions and variants
   • Theoretical work on Stirling, Bell, and related numbers
2. Algorithm analysis:
   • Average-case complexity analysis of sorting and online algorithms
   • Random process and probabilistic algorithm research
3. Algebraic combinatorics:
   • Study of combinatorial objects in symmetric functions and representation theory
   • Hopf algebra structure research
4. Educational purposes:
   • Teaching case study for generating function methods
   • Demonstrating elegance of bijective proofs

Key References

1. Gessel & Seo (2005): "A refinement of Cayley's formula for trees" - Foundational work on lucky statistics of parking functions
2. Konheim & Weiss (1966): "An occupancy discipline and applications" - Original definition of parking functions
3. Brandt et al. (2024): "Unit interval parking functions and the r-Fubini numbers" - Prior work directly built upon by this paper
4. Elder et al. (2025): "Parking functions, Fubini rankings, and boolean intervals in the weak order of Sₙ" - Related work by author team establishing connections with Bruhat order
5. Harris & Martinez (2026): "Parking functions with a fixed set of lucky cars" - General theory of enumeration with fixed lucky sets

Overall Assessment: This is a high-quality theoretical combinatorics paper that systematically and deeply investigates lucky statistics in Fubini rankings, establishing multiple elegant combinatorial identities and bijections. The proofs are rigorous, methods diverse, and results comprehensive. Though purely theoretical, it has potential connections with algorithm analysis and opens multiple directions for future research. The paper exemplifies the technical depth and aesthetic beauty of modern combinatorics, representing an important contribution to the field.