<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage{longtable}
\usepackage{enumitem}   
\usepackage{mathtools}
\usepackage{multirow}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{problem}[theorem]{Problem}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}


\begin{center}
\vskip 0.6cm{\Large\bf 
On the Lucky and Displacement Statistics\\
\vskip .1in
of Stirling Permutations
}
\vskip 0.6cm
    \begin{minipage}[t]{0.49\textwidth}
        \begin{center}
            Laura Colmenarejo\\
            Department of Mathematics\\
            North Carolina State University\\
            Raleigh, NC 27685\\
            USA\\
            \href{mailto:lcomen@ncsu.edu}{\tt lcomen@ncsu.edu}\\
            \ \\
            Jennifer Elder\footnotemark[1]{}\\
            Department of Computer Science, Mathematics and Physics\\
            Missouri Western State University\\
            St.~Joseph, MO 64507\\
            USA\\
            \href{mailto:jelder8@missouriwestern.edu}{\tt jelder8@missouriwestern.edu}\\
            \ \\
            Kimberly J.~Harry\\
            Department of Mathematical Sciences\\
            University of Wisconsin-Milwaukee\\
            Milwaukee, WI 53211\\
            USA\\
            \href{mailto:kjharry@uwm.edu}{\tt kjharry@uwm.edu}\\
            \ \\
            Dorian Smith\\
            School of Mathematics\\
            University of Minnesota\\
            Minneapolis, MN 55455\\
            USA\\
            \href{mailto:smi01055@umn.edu}{\tt smi01055@umn.edu}\\
        \end{center}
    \end{minipage}
    \begin{minipage}[t]{0.49\textwidth}
        \begin{center}
            Aleyah Dawkins\\
            Department of Mathematical Sciences\\
            Carnegie Mellon University\\
            Pittsburgh, PA 15213\\
            USA\\
            \href{mailto:adawkins@andrew.cmu.edu}{\tt adawkins@andrew.cmu.edu}\\
            \ \\
            Pamela E. Harris\footnotemark[2]{}\\
            Department of Mathematical Sciences\\
            University of Wisconsin-Milwaukee\\
            Milwaukee, WI 53211\\
            USA\\
            \href{mailto:peharris@uwm.edu}{\tt peharris@uwm.edu}\\
	    \ \\
            \ \\
            Selvi Kara\\
            Department of Mathematics\\
            Bryn Mawr College\\
            Bryn Mawr, PA 19010\\
            USA\\
            \href{mailto:skara@brynmawr.edu}{\tt skara@brynmawr.edu}\\
            \ \\
            Bridget Eileen Tenner\footnotemark[3]{}\\
            Department of Mathematical Sciences\\
            DePaul University\\
            Chicago, IL 60614\\
            USA\\
            \href{mailto:bridget@math.depaul.edu}{\tt bridget@math.depaul.edu}
        \end{center}
    \end{minipage}
\end{center}



\footnotetext[1]{J.~Elder was partially supported by an AWM Mentoring Travel Grant.}
\footnotetext[2]{P.~E.~Harris was partially supported by a Karen Uhlenbeck EDGE Fellowship.}
\footnotetext[3]{B.~E.~Tenner was partially supported by the NSF grant DMS-2054436.}










\begin{abstract}
Stirling permutations are parking functions, and we investigate two parking function statistics in the context of these objects: lucky cars and displacement. 
Among our results, we consider two extreme cases of the lucky statistic, both of which are enumerated by important integer sequences: extremely lucky Stirling permutations (those with maximally many lucky cars) and extremely unlucky Stirling permutations (those with exactly one lucky car). 
We show that the number of extremely lucky Stirling permutations of order $n$ is the Catalan number $C_n$, and the number of extremely unlucky Stirling permutations is $(n-1)!$.
We also give a selection of results for luck that lies between these two extremes. 
Further, we establish that the displacement of all the Stirling permutations of order $n$ is $n^2$, and we prove several results about displacement composition vectors. 
We conclude with directions for further study.
\end{abstract}

\section{Introduction}

Throughout the paper, we let $\mathbb{N}\coloneqq\{0,1,2,3,\ldots\}$,
and we write $[i,j] \coloneqq\{i,i+1,\ldots, j-1,j\}$ for integers $i \le j$ and $[n] \coloneqq [1,n]$.
A \textit{parking function of length} $n$ is a tuple $\alpha=(a_1,a_2,\ldots,a_n)\in [n]^n$ whose rearrangement into weakly increasing order 
$\alpha^{\uparrow}=(b_1,b_2,\ldots,b_n)$ satisfies $b_i\leq i$ for all $i\in[n]$.
For example, the sequences 
$\alpha_{1}=(1,3,1,5,6,3)$ and $\alpha_{2}=(4,4,1,2,2,3,3,1)$
are parking functions since their rearrangements are 
$\alpha^{\uparrow}_1=(1,1,3,3,5,6)$ and  $ \alpha^{\uparrow}_2=(1,1,2,2,3,3,4,4)$,
respectively.
However, the sequence $\alpha_3=(2,2,3,1,6,6)$ is not a parking function since $\alpha^{\uparrow}_3=(1,2,2,3,6,6)$ and $b_5=6 \nleq 5$.
We let $\operatorname{PF}_n$ denote the set of parking functions of length~$n$. 

We recall another equivalent interpretation of parking functions. 
\begin{definition}
    Consider a one-way street with exactly $n$ parking spots and a line-up of $n$ cars, each with a preferred spot that we record as a sequence $\alpha=(a_1,a_2,\ldots,a_n)\in [n]^n$.
    Car $i$ tries to park in its preferred spot  $a_i$. 
    If spot $a_i$ is available, then car $i$ parks there; otherwise, car $i$ continues down the street until car $i$ finds the first available spot to park and parks there.
    If all cars park, then the tuple $\alpha$ is a \emph{parking function}.
\end{definition}
Throughout the paper, we use the language from the above definition when referring to parking functions.
Parking functions were introduced by Konheim and Weiss~\cite{konheim1966occupancy} in their study of hashing functions, and they established that $|\operatorname{PF}_n|=(n+1)^{n-1}$.
Since their introduction, past work studied this family of combinatorial objects, their statistics, and numerous generalizations
~\cite{MR3408702, unit_pf, inv_assort, knaple, DIAZLOPEZ20191674, flat_pf, unit_perm, Schumacher_Descents_PF}.

One such work, motivating the current, is that of Gessel and Seo~\cite{GesselandSeo} on so-called ``lucky'' cars in parking functions. 

\begin{definition}\label{defn:lucky}
In a parking function $\alpha = (a_1, a_2, \ldots, a_n)$, car $i$ is said to be \textit{lucky} if car $i$ parks in its preferred spot $a_i$. 
Given $\alpha\in\operatorname{PF}_n$, write
$\mathrm{Lucky}(\alpha)$ for the set of lucky cars in $\alpha$, and write $\mathrm{lucky}(\alpha)\coloneqq |\mathrm{Lucky}(\alpha)|$
for the number of lucky cars in $\alpha$. 
\end{definition}


For example,  for $\alpha_1=(1,1,\ldots,1)\in[n]^n$, we know $\mathrm{Lucky}(\alpha_1)=\{1\}$ and $\alpha_1$ is one of the ``unluckiest'' parking functions since the only car that parks in its preferred spot is car $1$. The lucky cars of a different parking function $\alpha_2=(n,1,1,\ldots,1)\in[n]^n$
are $1$ and $2$; that is, we have $\mathrm{Lucky}(\alpha_2) = \{1,2\}$ and so $\alpha_2$ is luckier than $\alpha_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 $\mathrm{Lucky}(\alpha)=[n]$ and $\mathrm{lucky}(\alpha)=n$. 

Gessel and Seo~\cite{GesselandSeo} established that the generating function for the lucky car statistic on parking functions is
\begin{equation}\label{eq:GesselSeo}
  \sum_{\alpha \in \operatorname{PF}_n} q^{\mathrm{lucky}(\alpha)} = q\prod_{i=1}^{n-1} (i+(n-i+1)q).  
\end{equation}

Their work is related to rooted trees, and the proof relies on ordered set partitions and generating function techniques. More recently, Harris, Kretschmann, and Mart\'inez Mori~\cite{harris2023lucky} established that the sequences $\alpha \in [n]^n$
(not necessarily parking functions) with exactly $n-1$ cars parking in their preferred spot is equal to the total number of comparisons performed by the Quicksort algorithm given all possible orderings of an array of size $n$. 

We recall another related statistic for parking functions known as  \textit{displacement}.

\begin{definition}
 Let $\alpha=(a_1,\ldots, a_n) \in [n]^n$ be a parking function. If car $i$ parks in spot $p(i)\in [n]$, then the \textit{displacement} of car $i$ is defined by $d(i)= p(i)-a_i$, the difference between where car $i$ parks and its preference $a_i$. The \textit{total displacement} of $\alpha$ is given by  $d(\alpha)=\sum_i d(i)$.   In this way, cars with zero displacement are lucky cars, while every car whose displacement is positive is unlucky.
\end{definition}


Displacement has been widely studied in the literature.  Knuth~\cite{Knuth1998} established a bijection between the total displacement of parking functions and the number of inversions of labeled trees. 
Beissinger and Peled~\cite{Beissinger1997} constructed a bijection from parking functions to labeled trees that carries the displacement of parking functions to the external activity of trees. 
Yan~\cite{MR3408702} studied recurrence relations for generalized displacement in $u$-parking functions, and Aguillon, Alvarenga, Harris, Kotapati, Mori, Monroe, Saylor, Tieu, and Williams~II~\cite{displacement_hanoi} found a bijection with the set of ideal states in the  Tower of Hanoi game and parking functions of length $n$ with displacement equal to one. For more on the lucky statistic and displacement, we point the reader to the $2023$ work of Stanley and Yin~\cite{stanley2023enumerative}. 
Researchers have also studied the displacement statistic within a more probabilistic framework, examining its relationship to the area/cost construction statistic for hashing tables with linear probing. They showed that the displacement statistic converges to normal, Poisson, or Airy distributions, depending on the ratio of cars to spots  ~\cite{Diaconis-Hicks,flajolet-poblete-viola,Janson}. 


In this paper, we focus on a subset of parking functions consisting of Stirling permutations. 

\begin{definition}\label{defn:stirling permutations}
A permutation of the multiset
$\{1,1,2,2,3,3,\ldots,n,n\}$ is a \textit{Stirling permutation of order $n$} 
if every value $j$ appearing between the two instances of $i$ satisfies $j&gt;i$.
We write $Q_n$ to denote the set of Stirling permutations of order $n$, 
and we write $w \in Q_n$ as a word $w(1) w(2) \cdots w(2n)$. 
\end{definition}

For example, we have $123321 \in Q_3$, but $123231 \notin Q_3$ as $2$ appears between the two instances of $3$.


Gessel and Stanley~\cite{MR462961} studied Stirling permutations.  
The Stirling polynomial $Q_n(t)=\sum_{w\in Q_n}t^{\mathrm{des}(w)}$, where $\mathrm{des}(w)$ refers to the descent statistic in permutations, arises as the numerator for the generating function
\[\sum_{m\geq 0}S(m+n,n)t^m=\frac{Q_n(t)}{(1-t)^{2n+1}},\]
where $S(m+n,n)$ are the Stirling numbers of the second kind~\cite[\seqnum{A008277}]{OEIS}. 
The Stirling numbers of the second kind $S(n,k)$ count the number of set partitions of $[n]$ consisting of exactly $k$ blocks~\cite[p.\ 81]{StanleyECVol1}.
Gessel and Stanley~\cite{MR462961} showed $|Q_n|=(2n-1)!!$.
Since then, others have studied Stirling permutations to include work on enumerating descents, mesa sets, and other statistics related to generalized permutations~\cite{buck2023flattenedstirlingpermutations,ELIZALDE2021105429, elizalde2022descents, MesaPaper, shankar2023enumeration}.


Stirling permutations of order $n$ can be interpreted as parking functions of length $2n$.
Given a Stirling permutation $w=w(1)w(2)\cdots w(2n)\in Q_n$, the weakly increasing rearrangement of $w$ is always $(1,1,2,2,3,3,\ldots, n,n)$, which satisfies the required inequality condition characterizing parking functions. Thus, we have $ w\in  \operatorname{PF}_{2n}$.
Henceforth, we abuse notation and drop parenthesis and commas when talking about parking functions. We instead adopt the one-line notation used in Stirling permutations.


Since Stirling permutations can be viewed as a subset of parking functions, it is natural to explore the behavior of parking function statistics within this subset. Our focus is on the displacement and lucky statistics of Stirling permutations. 
Furthermore, we investigate their admissible sets in the context of lucky statistics. Given a subset $S\subset[2n]$, we say $S$ is an \emph{admissible lucky set} (or just \emph{admissible}) if there exists $w\in Q_n$ such that $\mathrm{Lucky}(w)=S$. Otherwise, we say that $S$ is \emph{not admissible}.


Our paper is organized in the following way.
In Section~\ref{sec:extreme cases}, we consider two extreme cases and prove the following:
\begin{itemize}[leftmargin=.3in]
    \item The so-called ``extremely unlucky'' Stirling permutations (those with exactly one lucky car) are enumerated by $(n-1)!$ (Theorem~\ref{thm:extremely unlucky}).
    \item The so-called ``extremely lucky'' Stirling permutations (those with exactly $n$ lucky cars) are enumerated by Catalan numbers (Theorem~\ref{thm:extremely lucky bijection with parentheses}).
\end{itemize}

In Sections~\ref{sec:admissible} and~\ref{sec:small cardinality}, we look between these extremes by considering possible admissible sets of Stirling permutations.
As a foray into this broad topic, our results are as follows:
\begin{itemize}[leftmargin=.3in]
\item If $S$ is an admissible lucky set for $Q_n$, then $S$ is also admissible for all $Q_{m}$ with $m&gt;n$ (Theorem~\ref{thm:n to n+1 admissible}).
\item We provide conditions under which there are exactly two lucky cars ({Theorem}~\ref{thm:exactly two lucky cars}).
The set $\{1, n-1, 2n-2\}$ is admissible if and only if $n$ is even (Proposition~\ref{prop:admissible n even}).
\end{itemize}
In Section~\ref{sec:displacement}, we consider the displacement statistic 
of Stirling permutations and prove the following: 
\begin{itemize}[leftmargin=.3in]
    \item The displacement of every Stirling permutation is $n^2$ (Corollary~\ref{cor:displacement}).
    \item For every Stirling permutation, the number of cars displaced is between (inclusively) $n$ and $2n-1$ (Corollary~\ref{cor:bounds for m_D}).
    \item We show that extremely lucky  Stirling permutations are uniquely determined by their displacement composition, a tuple that describes the displacement of the unlucky cars (Theorem~\ref{thm:displacement_implies_unique} and Corollary~\ref{cor:displace_num}). 
\end{itemize}

We conclude the paper in Section~\ref{sec:open problems} with a selection of open problems. 


\section{Extremely unlucky/lucky Stirling permutations}\label{sec:extreme cases}

The $\mathrm{lucky}$ statistic of Stirling permutations in $Q_n$ has a well-defined range, as we show in the upcoming Lemma~\ref{lem:lucky_range}. It is natural  
to look at the  
Stirling permutations that achieve the extreme values in this range. The main results of this section are characterizations and enumerations of those two families of Stirling permutations -- one enumerated by $(n-1)!$, and the other enumerated by the $n$th Catalan number.

\begin{lemma}\label{lem:lucky_range}
  Let  $w = w(1) \cdots w(2n) \in Q_n$.   
    \begin{enumerate}
    \item[(a)]  Car $1$ is always lucky. 
    \item[(b)]  If car $i$ is the first car with $w(i) = 1$, then $i \in  \mathrm{Lucky}(w)$.
      \item[(c)] Then $1 \leq \mathrm{lucky}(w)  \leq n$. 
    \end{enumerate}
 \end{lemma}   

\begin{proof}
\leavevmode
\begin{enumerate}

\item[(a)] Car $1$ is always lucky in each $ w\in Q_n$, as car $1$ is the first car to park when all the spots (including the desired spot by car $1$) are available. Thus, we have $1\in \mathrm{Lucky}(w)$ for  every $w\in Q_n$.

\item[(b)] Let $i\in[n]$ be the smallest $i$ such that $w(i)=1$, i.e., car $i$ is the first car to prefer spot $1$. Then car $i$ parks in spot $1$.  Hence, we know $i \in \mathrm{Lucky}(w)$. 

\item[(c)] It follows from (a) that $ 1\leq \mathrm{lucky}(w)$ for every $w\in Q_n$. For the upper bound, note that each car prefers one of the first $n$ parking spots by the definition of Stirling permutations. Thus, at most $n$ cars get to park in their desired spots, meaning $ \mathrm{lucky}(w) \leq n$.
\end{enumerate}
\end{proof}


In the context of unlucky cars, the following complementary observation is immediate yet useful.

\begin{remark}\label{rem:2n never lucky}
Every car whose preference is the second instance of a value in $w\in Q_n$ is unlucky. In particular, the last car $2n$ is always unlucky. 
\end{remark}
 
The main results of the next two subsections consider the extremes described by Lemma~\ref{lem:lucky_range}(c). Namely, we establish that the number of ``extremely unlucky'' Stirling permutations (those with only one lucky car) is $(n-1)!$ (see Theorem~\ref{thm:extremely unlucky}) and that ``extremely lucky'' Stirling permutations (those with $n$ lucky cars) are counted by Catalan numbers (see Corollary~\ref{cor:extremely lucky are catalan}). 


\subsection{Stirling permutations with extremely bad luck}

The lower bound in Lemma~\ref{lem:lucky_range}(c) suggests that having exactly one lucky car is of ``extremely bad luck'' for Stirling permutations.

\begin{definition}\label{defn:unlucky stirling}
    A Stirling permutation $w$ with $\mathrm{Lucky}(w) = \{1\}$ is an \emph{extremely unlucky} (Stirling) permutation.
\end{definition}

One necessary condition for having exactly one lucky car is that $w(1) = 1$. Similarly, we must also have $w(2) = 1$, since otherwise $w(2)$ would be lucky.

\begin{example}
    The only extremely unlucky Stirling permutations of order $3$ are $112233$ and $112332$.
\end{example}

We now prove a technical result that helps us characterize extremely unlucky Stirling permutations. The upshot of this result is that if the first $x$ values of $w$ are all less than $x$, then $x$ is not lucky.

\begin{lemma}\label{lem:early small values ruin luck}
    Let $w=w(1)w(2)\cdots w(2n) \in Q_n$ and $x \in [2n]$.
    If $w(i) &lt; x$ for all $i \le x$, then $x \not\in \mathrm{Lucky}(w)$.
\end{lemma}

\begin{proof}
    Assume that $w(i) &lt; x$ for all $i \le x$, for some $x \ge 2$ (the statement is meaningless for $x &lt; 2$). Thus, the first $x$ cars all want to park in the first $x-1$ spaces. By the pigeonhole principle, at least one car is unlucky and has to take the next available space. Consequently, one of these initial $x$ cars parks in spot $x$. By the assumption, the first appearance of $w(j) = x$ occurs for $j &gt; x$. Thus, car $j$ does not get to park in its preferred spot because spot $x$ has already been claimed. Hence, we have $x \not\in \mathrm{Lucky}(w)$.
\end{proof}

\begin{example}
    Let $w=122133 \in Q_3$. Consider $x=3$, and note that $\{w(1), w(2), w(3)\} = \{1,2\}$. Indeed, we have $3 \not\in \mathrm{Lucky}(w)$, confirming the result of Lemma~\ref{lem:early small values ruin luck}. Now consider $x = 2$. Given $\{w(1),w(2)\} = \{1,2\}$, the assumption of Lemma~\ref{lem:early small values ruin luck} does not hold.  This still leaves open the possibility for car $2$ to be unlucky. However, car $2$ parks in its preferred spot $2$, indicating that car $2$ is not unlucky after all. 
\end{example}

In fact, as the above example suggests, the property described in Lemma~\ref{lem:early small values ruin luck} is a necessary and sufficient condition to characterize the extremely unlucky Stirling permutations.

\begin{corollary}\label{cor:extremely unlucky iff}
    A Stirling permutation $w \in Q_n$ is extremely unlucky if and only if for all $x \in [2,n]$, we have $w(i) &lt; x$ for all $i \le x$.
\end{corollary}

\begin{proof}
Let $w \in Q_n$ be a Stirling permutation. If for all $x \in [2,n]$, we have $w(i) &lt; x$ for all $i \le x$, then $w$ is extremely unlucky by Lemma~\ref{lem:early small values ruin luck}. 

Now, suppose that $w$ is extremely unlucky. 
Recall that $2 \not\in \mathrm{Lucky}(w)$ and this means that $w(2) = 1$, giving the result for $x = 2$. Fix $x \in [3,n]$ and suppose, inductively, that for all $y \in [2,x-1]$, we have $w(i) &lt; y$ for all $i \le y$. Suppose, for the purpose of obtaining a contradiction, that $w(x)\ge x$. For $w$ to be extremely unlucky, for each $y \in [2,x-1]$, the first $y$ cars must have parked in spots $[1,y]$. Thus, the first $x-1$ cars have parked in spots $[1,x-1]$, meaning that spot $w(x)$ is available for car $x$ to park in. Thus, car $x$ is lucky, which contradicts the assumption that $w$ is extremely unlucky.
\end{proof}


The following set is useful in our proof of the enumeration of the extremely unlucky Stirling permutations. 

\begin{definition}
    For a finite, nonempty set $S$ of integer numbers, we define $S^{\triangledown}$ to be the subset of $S$ consisting of everything but the largest element of $S$; that is,
    $$S^{\triangledown} \coloneqq S \setminus \{\max(S)\}.$$
\end{definition}

Next, we enumerate extremely unlucky Stirling permutations via a constructive proof. 
In this proof we build extremely unlucky Stirling permutations of order $n$ by first positioning the two copies of $n$.  
Then we position the two copies of $n-1$, and so on. 
At each step, we always ensure that the only lucky car is the first car whose preferred spot is $1$. 
The construction is demonstrated after the proof of the theorem, in Example~\ref{ex:extremely unlucky}.


\begin{theorem}\label{thm:extremely unlucky}
    Given an integer $n \ge 1$, there are $(n-1)!$ extremely unlucky Stirling permutations of order $n$.
\end{theorem}
\begin{proof}
    Following Corollary~\ref{cor:extremely unlucky iff}, we can construct the extremely unlucky Stirling permutations of order $n$ as follows. 
    First, we position two (necessarily consecutive) copies of $n$, with the leftmost of those appearing as $w(i_n)$ for some $i_n \in [n+1, 2n]^{\triangledown}$.  There are $2n-(n+1) + 1 - 1 = n-1$ ways to do this. The rightmost $n$ necessarily appears at $w(i_n^+)$, where $i_n^+$ is the smallest element larger than $i_n$ in the set $[n+1,2n]$; that is, we have $i_n^+ = i_n+1$.
    
    Next, we position the two copies of $n-1$. Because we are building a Stirling permutation, these are either consecutive or they immediately surround the two copies of $n$. Thus, by Corollary~\ref{cor:extremely unlucky iff}, the leftmost of these appears as $w(i_{n-1})$ for some
    $$i_{n-1} \in \Big([n, 2n] \ \setminus \ \{i_n, i_n^+\}\Big)^{\triangledown},$$
    and the rightmost $n-1$ necessarily have position $w(i_{n-1}^+)$, where $i_{n-1}^+$ is the smallest element larger than $i_{n-1}$ in the set $[n, 2n] \setminus \{i_n, i_n^+\}$. There are $2n - n + 1 - 2 - 1 = n-2$ choices for $i_{n-1}$. 
    
    We continue this process until we find two available positions for the leftmost $3$, one available position for the leftmost $2$, and finally insert the two $1$s as $w(1)$ and $w(2)$. For example, the leftmost $x$ appears as $w(i_x)$ for some
    $$i_x \in \Big([x+1,2n] \ \setminus \ \{i_n,i_n^+\} \ \setminus \ \{i_{n-1},i_{n-1}^+\} \ \setminus \ \cdots \ \setminus \ \{i_{x+1},i_{x+1}^+\}\Big)^{\triangledown},$$
and thus there are $2n-(x+1)+1 - 2(n-x) - 1 = x-1$ choices for $i_x$. The second appearance of $x$ is at $w(i_x^+)$, where $i_x^+$ is the smallest element larger than $i_x$ in the set
    $$[x+1,2n] \ \setminus \ \{i_n,i_n^+\} \ \setminus \ \{i_{n-1},i_{n-1}^+\} \ \setminus \ \cdots \ \setminus \ \{i_{x+1},i_{x+1}^+\}.$$
    This process has constructed $(n-1)(n-2)\cdots 3\cdot 2 \cdot 1 = (n-1)!$ distinct Stirling permutations, which are exactly the extremely unlucky Stirling permutations of order $n$.
\end{proof}

Therefore extremely unlucky Stirling permutations are enumerated, with a small shift of index, by~\cite[\seqnum{A000142}]{OEIS}.

We demonstrate the construction in the proof of Theorem~\ref{thm:extremely unlucky} with an example.

\begin{example}\label{ex:extremely unlucky}
    Let $n = 6$.
    \begin{itemize}[leftmargin=.3in]
        \item The index $i_6$ can be all of the five values in $[7,12]^{\triangledown} = \{7,8,9,10,11\}$. Suppose $i_6 = 9$, and so $i_6^+ = 10$.
        \item The index $i_5$ can be all of the four values in $\big([6,12] \, \setminus \, \{9,10\}\big)^{\triangledown} = \{6,7,8,11\}$. Suppose $i_5 = 6$, and so $i_5^+ = 7$.
        \item The index $i_4$ can be all of the three values in $\big([5,12] \, \setminus \, \{9,10\} \, \setminus \, \{6,7\}\big)^{\triangledown} = \{5,8,11\}$. Suppose $i_4 = 8$, and so $i_4^+ = 11$.
        \item The index $i_3$ can be all of the two values in $\big([4,12] \, \setminus \, \{9,10\} \, \setminus \, \{6,7\} \, \setminus \, \{8,11\}\big)^{\triangledown} = \{4,5\}$. Suppose $i_3 = 5$, and so $i_3^+ = 12$.
        \item The index $i_2$ must be the one value in $\big([3,12] \, \setminus \, \{9,10\} \, \setminus \, \{6,7\} \, \setminus \, \{8,11\} \, \setminus \, \{5,12\}\big)^{\triangledown} = \{3\}$. 
        Thus, we must have $i_2=3$ (in fact, the value of $i_2$ is always $3$),
        and hence $i_2^+ = 4$.
    \end{itemize}
    Thus, we have produced the Stirling permutation
    $$1 \ 1 \ 2 \ 2 \ 3 \ 5 \ 5 \ 4 \ 6 \ 6 \ 4 \ 3,$$
    which is, indeed, extremely unlucky.
\end{example}



\subsection{Stirling permutations with extremely good luck}

In contrast to the extremely unlucky Stirling permutations of Theorem~\ref{thm:extremely unlucky}, we now consider the very fortunate ones. 
To begin, note that by Lemma~\ref{lem:lucky_range}(c), if $w  \in Q_n$, then $\mathrm{Lucky}(w) \subseteq [2n]$ with $\mathrm{lucky}(w)\leq n$. 
In other words, at most half of the cars are lucky.


\begin{definition}\label{defn:lucky stirling}
    A Stirling permutation $w \in Q_n$ for which $\mathrm{lucky}(w) =n$ is an \emph{extremely lucky} (Stirling) permutation.
\end{definition}

Note, in particular, that $w \in Q_n$ is extremely lucky if and only if lucky cars park in each of the first $n$ available parking spots.
In particular, extremely lucky Stirling permutations are \emph{Catalan objects}; that is, they are enumerated by the Catalan numbers~\cite[\seqnum{A000108}]{OEIS}.
\begin{definition}\label{defn:catalan}
    The \emph{Catalan numbers} are the sequence $(C_n)_{n\geq 0}$ defined by $C_n=\frac{1}{n+1}\binom{2n}{n}$. 
\end{definition}

Many families of combinatorial objects are Catalan objects, and we refer the interested reader to Stanley's work ~\cite{stanley_2015} for a comprehensive book on the subject.
Our proof that extremely lucky permutations are another family of Catalan objects is established by giving a bijection to valid parenthesizations of $n$ pairs of parentheses; that is, expressions that contain $n$ pairs of parentheses that are correctly matched. 
It is well-known that valid parenthesizations are Catalan objects~\cite[Prop.\ 6.2.1, p.\ 169]{StanleyECVol2}, a result which was proven by  Eug\`{e}ne Charles Catalan, although the sequence was known much earlier by Mingantu, a Mongolian mathematician~\cite{Larcombe}. 
In preparation for that main enumerative result, we first characterize extremely lucky Stirling permutations.

\begin{proposition}\label{prop:extremely lucky second cars in order}
    A Stirling permutation $w \in Q_n$ is extremely lucky if and only if the subword of $w(1)\cdots w(2n)$ consisting of the second appearances of each number is the word $n\cdots 321$; that is, the second appearances of each number in $w$ occur in decreasing order.
\end{proposition}

\begin{proof}
    Suppose first that there is some $x &lt; n$ 
    for which the second appearance $x = w(j)$ appears to the left of the second appearance of $x+1$ in $w(1)\cdots w(2n)$. Since $w$ is a Stirling permutation, we must therefore have
    $$w = \cdots x \cdots x \cdots (x+1) \cdots (x+1) \cdots.$$
    But then $x+1$ would not be the parking spot of a lucky car because either car $j$  would park in spot $x+1$ or 
    some car $h$ with $h &lt; j$ and $w(h) &lt; w(j)$ would have parked in spot $x+1$, before the cars preferring spot $x+1$ have had a chance to do so. Thus, the Stirling permutation $w$ is not extremely lucky.

    For the other direction of the argument, suppose that the second appearances of each number in $w$ occur in decreasing order. 
    Then certainly the first appearance of a value  $x \in [1,n]$ in $w(1)\cdots w(2n)$ also appears to the left of the second appearance of all numbers in $[1,x-1]$. 
    In fact, all the entries to the left of the first appearance of $x$ are either larger than $x$ or the first appearance of a number in $[1,x-1]$. Thus, spot $x$ is available for the first car preferring spot $x$ for each $x \in [1,n]$. In other words, each car whose preference is the first appearance of a number in $[1,n]$ is a lucky car, and hence $\mathrm{lucky}(w)=n$. 
   \end{proof} 

Proposition~\ref{prop:extremely lucky second cars in order} characterizes extremely lucky Stirling permutations and allows us to give a bijective correspondence between extremely lucky Stirling permutations of order $n$ and valid parenthesizations of $n$ pairs of parentheses.
For example, the $C_3=5$ valid parenthesizations of $3$ pairs of parentheses are 
\[( \ ( \ ( \ ) \ ) \ ), \ \ ( \ ( \ ) \ ( \ ) \ ), \ \ ( \ ( \ ) \ ) \ ( \ ), \ \ ( \ ) \ ( \ ( \ ) \ ), \ \ \mbox{and}\ \ ( \ ) \ ( \ ) \ ( \ ).\]

\begin{theorem}\label{thm:extremely lucky bijection with parentheses}
    Extremely lucky Stirling permutations of order $n$ are in bijection with valid parenthesizations of $n$ pairs of parentheses.
\end{theorem}

\begin{proof}
    Given an extremely lucky $w \in Q_n$, replace the first occurrence of each $x$ by ``('' and the second by ``).'' Because $w$ is a Stirling permutation, this produces a valid parenthesization.

    Now, given a valid pairing of $n$ pairs of parentheses, replace each ``)'' by $n, \ldots,1$ in decreasing order from left to right. For each ``)'' replaced by $x$, replace its partner ``('' by $x$ too. This construction necessarily produces a Stirling permutation, and Proposition~\ref{prop:extremely lucky second cars in order} means that we get exactly those Stirling permutations that are extremely lucky.
\end{proof}

We demonstrate the argument in the proof of Theorem~\ref{thm:extremely lucky bijection with parentheses} with the following example.

\begin{example}\label{ex:extremely lucky}
    By the bijection described above, the valid parenthesization
    $$ ( \ ) \ ( \ ) \ ( \ ( \ ) \ ( \ ( \ ) \ ) \ )$$
    is matched with the extremely lucky Stirling permutation 
    $$6 \ 6 \ 5 \ 5 \ 1 \ 4 \ 4 \ 2 \ 3 \ 3 \ 2 \ 1 \in Q_6.$$
\end{example}

It is important to note that, as in the proof of Theorem~\ref{thm:extremely lucky bijection with parentheses}, 
every Stirling permutation can be paired with a valid parenthesization. 
Thus, many Stirling permutations could describe the same string of parentheses, and among those, only one is extremely lucky. For instance, the Stirling permutations $112235546643$ and $665514423321$ both correspond to $( \ ) \ ( \ ) \ ( \ ( \ ) \ ( \ ( \ ) \ ) \ )$, but only the latter permutation is extremely lucky (cf.\ Examples~\ref{ex:extremely unlucky} and~\ref{ex:extremely lucky}). 

\begin{corollary}\label{cor:extremely lucky are catalan}
     For every positive integer $n$, the number of extremely lucky Stirling permutations of order $n$ is the Catalan number $C_n$.
\end{corollary}


\section{Admissible lucky sets}\label{sec:admissible}
In this section, we give initial results towards characterizing the subsets of cars that can be lucky for Stirling permutations.  To this end, we recall the following definition from the introduction. 

\begin{definition}\label{def:addmissibleLucky}
    A subset $S\subseteq[2n]$ is an \emph{$n$-admissible lucky set} (or just \emph{admissible} if context is clear) if there exists $w\in Q_n$ such that $\mathrm{Lucky}(w)=S$. Otherwise, we say that $S$ is \emph{not $n$-admissible} (or \emph{not admissible}).  
\end{definition}

In what follows, we characterize when a set with two elements is an admissible lucky set and prove several properties of three-element admissible lucky sets. It remains an open problem to give a complete characterization of all admissible lucky sets. 

\begin{example}\label{ex: admissible 1}
    For $n=4$, the set $S=\{1,3,6\}$ is a $4$-admissible lucky set since  $\mathrm{Lucky}(w)=S$ for $w=3 3 1 4 4 2 2   1 \in Q_4$.
    In contrast, the set $S'=\{1,4,8\}$ is not $4$-admissible since there is no $w \in Q_4$ such that  $\mathrm{Lucky}(w)=S'$. (Indeed, recall from Remark~\ref{rem:2n never lucky} that $8$ is unlucky for all $w \in Q_4$.) Table~\ref{table:4-admissible sets} was generated via exhaustive research and lists all $4$-admissible lucky sets. 
\end{example}

\begin{table}[htbp]
\centering
\begin{tabular}{cccc}
\{1\} &amp; \{1, 2\} &amp; \{1, 2, 3\} &amp; \{1, 2, 3, 4\}\\
&amp; \{1, 3\} &amp; \{1, 2, 4\} &amp; \{1, 2, 3, 5\}\\
&amp; \{1, 4\} &amp; \{1, 2, 5\} &amp; \{1, 2, 3, 6\}\\
&amp; \{1, 5\} &amp; \{1, 2, 6\} &amp; \{1, 2, 3, 7\}\\
&amp; \{1, 7\} &amp; \{1, 2, 7\} &amp; \{1, 2, 4, 5\}\\
&amp; &amp; \{1, 3, 4\} &amp; \{1, 2, 4, 6\}\\
&amp; &amp; \{1, 3, 5\} &amp; \{1, 2, 4, 7\}\\
&amp; &amp; \{1, 3, 6\} &amp; \{1, 2, 5, 6\}\\
&amp; &amp; \{1, 3, 7\} &amp; \{1, 2, 5, 7\}\\
&amp; &amp; \{1, 5, 6\} &amp; \{1, 3, 4, 5\}\\
&amp; &amp; \{1, 5, 7\} &amp; \{1, 3, 4, 6\}\\
&amp; &amp; &amp; \{1, 3, 4, 7\}\\
&amp; &amp; &amp; \{1, 3, 5, 6\}\\
&amp; &amp; &amp; \{1, 3, 5, 7\}
\end{tabular}
\caption{The thirty-one admissible lucky sets for Stirling permutations of order $4$, arranged by size.}\label{table:4-admissible sets}
\end{table}

Determining the properties of admissible lucky sets is the focus of the remainder of this section.
We begin with a stability result, which establishes that if a set is $n$-admissible, then the set is $m$-admissible
 for all $m\geq n$.
 
\begin{theorem}\label{thm:n to n+1 admissible}
If $S$ is an $n$-admissible lucky set, then the sets $S$ and $S\cup \{2n+1\}$ are both $(n+1)$-admissible lucky sets.
\end{theorem}

\begin{proof}
Suppose that $S$ is an $n$-admissible lucky set and that $w \in Q_n$ satisfies $\mathrm{Lucky}(w)=S$. Then the Stirling permutation $w'=w(n+1)(n+1) \in Q_{n+1}$, created by appending the value $(n+1)$ twice to the end of $w$, ensures that the last two cars whose preference is $n+1$ end up parking in spots $2n+1$ and $2n+2$, respectively. 
Thus, we have $\mathrm{Lucky}(w') = S$ as well. 

Now consider the Stirling permutation $w'' \in Q_{n+1}$ defined by $w''(i) \coloneqq w(i) + 1$ for all $1\leq i \le 2n$ and $w''(2n+1) = w''(2n+2) \coloneqq 1$. 
By construction, we have $\mathrm{Lucky}(w'') = \mathrm{Lucky}(w) \cup \{2n+1\}$, meaning that $S \cup \{2n+1\}$ is $(n+1)$-admissible, as desired.
\end{proof}

Next, we recall a consequence of Lemma~\ref{lem:lucky_range}(a) and Remark~\ref{rem:2n never lucky}, which involves elements of admissible lucky sets.
\begin{corollary}\label{lem:2n_never_lucky}
If $S$ is $n$-admissible lucky set, then $1 \in S$ and $2n \not\in S$. 
\end{corollary}

In fact, the preferred parking spot of the first lucky car  (car $1$) determines the preferences of the initial unlucky cars. 
 
\begin{lemma}\label{lem:initial unlucky preferences are forced}
    Let $w \in Q_n$ with $\mathrm{lucky}(w) \ge 2$, and let $x$ be the second-smallest element of $\mathrm{Lucky}(w)$. Then the first set of unlucky cars $2,3, \ldots, x-1$ park, in order, in spots
    $$w(1) + 1, \, w(1) + 2, \, \ldots, \, w(1)+x-2.$$
\end{lemma}

\begin{proof}
    In order for cars $2, 3, \ldots, x-1$ to be unlucky, they must each prefer spots that have already been occupied when cars $2,3,\ldots,x-1$ attempt to park. This implies that the preference of car $2$ must be $w(2) = w(1)$, ensuring that car $2$ parks in spot $w(1) + 1$. As the value $w(1)$ has now appeared twice, the value $w(3)$ (that is, the preference for car $3$) can only be $w(1) + 1$, and thus car $3$  parks in spot $w(1) + 2$. Similarly, regardless of its preference, car $4$ ends up parking in spot $w(1)+3$. Continuing in this manner, car $y$ parks in spot $w(1) + y-1$ for all $y \in [2,x-1]$. 
\end{proof}

\begin{remark}\label{rk: values of w(i)}
    Under the assumptions of Lemma~\ref{lem:initial unlucky preferences are forced}, note that $w(i)\geq w(1)$ for $i \in [2,x-1]$.
\end{remark}
The nature of Stirling permutations can impact the parity of certain relevant values, as we see in the following lemma. 

\begin{lemma}\label{lem:stubborn stirling}
    Let $w \in Q_n$ and $k \in [1,n]$. Let $j$ be minimal such that $w(j) = k$; that is, this $j$ is the first car to prefer spot $k$ in this parking function.  
    If $w(i)&gt;w(j)$ for all $i\in[1,j-1]$, then $j$ must be odd.
\end{lemma}

\begin{proof}
Let $w$, $k$, and $j$ be as described in the assumptions of the statement. Suppose, for the purpose of obtaining a contradiction, that $j$ is even.
Then $j-1$ is odd, so there exist some $h$ and $h'$ with $w(h) = w(h')$, and $h &lt; j &lt; h'$ as each number appears with $2$ copies in $w$. 
We have $w(h) &gt; w(j)$ by assumption, which contradicts the fact that $w$ is a Stirling permutation.
\end{proof}

In particular, the first car to prefer spot $1$ must be an odd-indexed car. In the spirit of the previous lemmas, we can deduce the parity of the second lucky car if the second lucky car is in the second half of the queue.  

\begin{proposition}\label{prop:if second lucky is big, then it's odd}
    Let $w \in Q_n$ with $\mathrm{lucky}(w) \ge 2$, and let $x$ be the second-smallest element of $\mathrm{Lucky}(w)$. If $x &gt; n$, then $x$ is odd. 
\end{proposition}
\begin{proof}
Suppose that $x &gt; n$. 
By Lemma~\ref{lem:initial unlucky preferences are forced}, after the first $x-1$ cars have parked, the only unused parking spots are $[1,w(1)-1] \cup [w(1)+x-1,2n]$.
    Because $w(1)+x - 1 &gt; 1 + n - 1 = n$, and cars can only prefer the first $n$ spots, the only way for car $x$ to be lucky would be if car $x$ prefers to park in spot $y$ for some $y &lt; w(1)$. 
From this, Remark~\ref{rk: values of w(i)} and Lemma~\ref{lem:stubborn stirling} ensure that $x$ must be odd. 
\end{proof}

Having established several important foundational properties of admissible lucky sets, we spend the remainder of this section developing some of the more technical properties of these sets, which becomes relevant in our later examinations of admissible lucky sets of small cardinality. 
Many of these upcoming results focus on the second-smallest element of an admissible lucky set.

\begin{lemma}\label{lem:second_lucky}
Let $w\in Q_n$ with $\mathrm{lucky}(w)\geq 2$, and let $x$ be the second-smallest element of $\mathrm{Lucky}(w)$.
    If $w(1)=1$, then $x \le w(x) \le n$. 
\end{lemma}
\begin{proof}
Suppose that \(w(1) = 1\) and that car $x$ is the second lucky car.
By Lemma~\ref{lem:initial unlucky preferences are forced},
cars $2,3,\ldots, x-1$ park to the right of car~$1$, in spots $2,3,\ldots,x-1$, respectively.
Thus, if car $x$ is to be lucky, then car $x$ must be in the first half of the queue and prefer one of the spots in the set \(\{ x, \dots, n\}\). In other words, \( x \le w(x) \le n\). 
\end{proof}


When the second-smallest element of $\mathrm{Lucky}(w)$ is sufficiently large, the preference of other lucky cars must be suitably small.

\begin{lemma}\label{lem:first preference}
    Let $w \in Q_n$ with $\mathrm{lucky}(w) \ge 3$, and let $x$ be the second-smallest element of $\mathrm{Lucky}(w)$. 
    If $x\geq n$, then $w(1) \ge \mathrm{lucky}(w)$. 
    Moreover, the lucky cars park among the first $w(1)$ spots.
\end{lemma}

\begin{proof}
   By Lemma~\ref{lem:initial unlucky preferences are forced}, for all $i \in [2,x-1]$, car $i$ parks in spot $w(1)+i-1$. Because $x \ge n$, spots $w(1)$ through $n$ are all occupied before  car $x$ parks. 
   Thus, to ensure there are $\mathrm{lucky}(w) - 1$ unused parking spots for the remaining lucky cars to park in, we must have that $w(1) - 1 \ge \mathrm{lucky}(w) - 1$; that is, we have $w(1) \ge \mathrm{lucky}(w)$. 
   Finally, because spots $w(1)+1$ through $n$ are occupied by unlucky cars, all lucky cars must park among spots $[1, w(1)]$.
 \end{proof}

Next, we characterize when the penultimate car in a Stirling permutation is lucky.

\begin{theorem}\label{thm:2n-1lucky}
    For $w \in Q_n$, we have $2n-1 \in \mathrm{Lucky}(w)$ if and only if $w(2n-1) = 1$.
\end{theorem}

\begin{proof}
First suppose that $w(2n-1) = 1$. If $w(2n) &gt; 1$, then the value $1$ would appear between the two instances of $w(2n)$, meaning that $w$ is not a Stirling permutation. Thus, we have $w(2n) = 1$, and so car $2n-1$ is the first car to prefer spot $1$. Therefore, car $2n-1$ parks in spot $1$, and hence car $2n-1$ is lucky. 
    
    Now, suppose that $2n-1 \in \mathrm{Lucky}(w)$. Thus, car $2n-1$ is the first car to prefer $w(2n-1)$, and so $w(2n-1) = w(2n)$. If $w(2n-1) &gt; 1$, then consider the two cars, say cars $i$ and $j$ with $i&lt;j$, with preferred spot  $w(2n-1)-1$. If car $i$ is lucky, then either car $j$ or car $h$ for some $i &lt; h &lt; j$ parks in spot $w(2n-1)$. On the other hand, if car $i$ is not lucky, then for some $h \le i$, car $h$  parks in spot $w(2n-1)$. In either case, this contradicts the assumption that $2n-1 \in \mathrm{Lucky}(w)$. Therefore, we must have $w(2n-1) = 1$.
\end{proof}


\section{Admissible lucky sets of small cardinality}\label{sec:small cardinality}
In this section, we fully characterize and enumerate admissible lucky sets of size two. We also provide a first result toward a characterization for admissible lucky sets of size three.

\subsection{Admissible lucky sets of size two}
As discussed earlier $1 \in S$ for all the admissible sets (see Corollary~\ref{lem:2n_never_lucky}). In order to characterize admissible sets of size two, one needs to identify which cars can be the second lucky car.

\begin{theorem}\label{thm:exactly two lucky cars}
    A set $S = \{h,  i\}$ with $h&lt;i$ is an $n$-admissible lucky set if and only if $h = 1$ and either
    \begin{enumerate}
        \item[(a)] both $i&gt;n$ and $i$ is odd, or
        \item[(b)] we have $i \le n$.
    \end{enumerate}  
\end{theorem}

\begin{proof}
    By Proposition~\ref{prop:if second lucky is big, then it's odd}, the sets described in the statement are the only possible lucky sets. For the other direction, we provide Stirling permutations to demonstrate that all such $\{1,i\}$ can be obtained as lucky sets.  Let $w=112233 \cdots (n-1)(n-1)nn \in Q_n$. 
    \begin{itemize}
        \item Suppose $i$ is odd, with $i=2k+1$. Let $\alpha$ be the Stirling permutation obtained from $w$ by  inserting $11$ in between $(k+1)(k+1)$ and $(k+2)(k+2)$, namely, 
        $$\alpha= 2\,2\,3\,3\,\cdots \,(k+1)\,(k+1)\,1\,1\,(k+2)\,(k+2)\,(k+3)\,(k+3)\,\cdots\, n\,n.$$
        Regardless of whether $i\leq n$ or $i&gt;n$, one can verify that $\mathrm{Lucky}(\alpha) = \{1, i\}$.
        \item Suppose $i\leq n$ and $i$ is even, with $i=2k$. Let $\alpha'$ be the Stirling permutation obtained from $w$ by inserting $k (2k)(2k)$ in between $(k-1)(k-1)$ and $(k+1)(k+1)$, and placing the remaining copy of $k$ at the end after $nn$, namely, 
        \begin{multline*}
        \alpha'=1\,1\,\cdots \,(k-1)\,(k-1) \, k \,(2k) \,(2k) \, (k+1)\,(k+1)\,\cdots \\ 
        \cdots \,(2k-1)\,(2k-1)(2k+1)\,(2k+1)\, \cdots\, n \,n \,k.         
        \end{multline*}
One can verify that $\mathrm{Lucky}(\alpha') = \{1, i\}$. \qedhere
    \end{itemize}
    \end{proof}

Enumeration of $n$-admissible lucky sets of size two follows from the above characterization. 

\begin{corollary}
    For $n\geq 1$, there are 
    $\displaystyle{n-1+\left\lceil\frac {n-1}{2}\right\rceil}$ $n$-admissible lucky sets of size two.
\end{corollary}

Next, we conclude that if  $n$ is the second-smallest element in $\mathrm{Lucky}(w)$ for $w \in Q_n$, then $\mathrm{Lucky}(w) = \{1,n\}$. 

\begin{lemma}\label{lem:cardinality_2_with_n}
    Let $S$ be an $n$-admissible lucky set with 
    second-smallest element~$n$. 
    \begin{enumerate}
        \item[(a)] If $n$ is even, then $w(1)=1, w(n)=n$, and $|S|=2$. 
        \item[(b)] If $n$ is odd and $w(1)=1$, then $w(n)=n$ and $|S|=2$. 
    \end{enumerate}
\end{lemma}


\begin{proof}
Let $w\in Q_n$ with $\mathrm{Lucky}(w)=S$ and such that $1$ and $n$ are the two smallest elements in $S$. 

We first show that for $n$ even, we have $w(1)=1$. 
Suppose that $n$ is even and assume, for the purpose of obtaining a contradiction, that $w(1) &gt; 1$. Then, by Lemma~\ref{lem:initial unlucky preferences are forced}, cars 2 through $n-1$ park in spots $w(1)+1,w(1)+2,\ldots, w(1) + n - 2$ where $w(1) + n - 2 \ge n$. So, lucky car $n$ must prefer a spot in the set $ [1, w(1)-1]$. Moreover, the value $w(n)$ must be smaller than every element of $\{w(1), \ldots, w(n-1)\}$.
By Lemma~\ref{lem:stubborn stirling}, the index $n$ must be odd. This is a contradiction. Thus, if $n$ is even, then $w(1) = 1$. 

Now assume that $w(1) = 1$ and make no assumptions on the parity of $n$. By Lemma~\ref{lem:initial unlucky preferences are forced}, the first $n-1$ cars park in the first $n-1$ spots, so the only way car $n$ can be lucky is if car $n$ prefers to park in spot $n$; i.e., if $w(n) = n$. There can be no additional lucky cars because the first $n$ spots are occupied by the first $n$ cars. Thus, we have $|S| = 2$.
\end{proof}

\subsection{On admissible lucky sets of size three}\label{subsec:three lucky cars}

For $n=4$, Table~\ref{table:4-admissible sets}
 gives the $11$ distinct $4$-admissible lucky sets of cardinality three. 
In this section, we characterize certain families of three-element admissible lucky sets depending on the parity of $n$. It remains an open problem to characterize all three-element admissible lucky sets.

\begin{proposition}\label{prop:admissible n even}
The set $\{1,n-1,2n-2\}$ is an $n$-admissible lucky set if and only if $n$ is even.
\end{proposition}

\begin{proof}
First suppose that $w \in Q_n$ with $\mathrm{Lucky}(w) = \{1, n-1, 2n-2\}$. Assume $n &gt; 3$, with the result being easy to check in small cases. 

Recall that the first car to prefer spot $1$ is always lucky, and, by Lemma~\ref{lem:stubborn stirling}, that first car with preference for spot $1$ must be an odd-indexed car. Since $2n-2$ is always even, either car $1$ or car $n-1$, with $n$ even, must be the first car to prefer spot $1$. 

If $w(1) = 1$, by Lemma~\ref{lem:initial unlucky preferences are forced}, the only possible spots for the lucky car $n-1$ to prefer are $n-1$ or $n$. Since car $n$ is unlucky, car $n$ must have the same preference as a previous car, or its preferred spot is occupied. In order to satisfy the Stirling condition, we have $w(n-1) = w(n)$.  If $w(n-1) = n-1$, then the first $n$ cars park in the first $n$ spots, meaning that car $2n-2$ cannot possibly be lucky. On the other hand, if $w(n-1) = n$, then the only available spot for lucky car $2n-2$ to park is spot $n-1$. However, the preference of car $n+1$ is at most $n-1$. So, car $n+1$ ends up parking in the next available spot $n-1$, preventing car $2n-2$ from being lucky. Thus,  we know $w(1) = 1$ is not possible, and car $n-1$, with $n$ even, is the first car to prefer spot $1$. In other words, the set $\{1, n-1, 2n-2\}$ is $n$-admissible implies $n$ is even.

To prove the other direction of the result, it suffices to produce a Stirling permutation $w \in Q_{2k}$ for which $\mathrm{Lucky}(w) = \{1, 2k-1, 4k-2\}$.
Such a permutation is 
\[3\,3\,4\,4\,\cdots\,k\,k\,(k+1)\,(k+1)\,1\,(k+2)\,(k+2)\,\cdots\,(2k)\,(2k)\,2\,2\,1 \in Q_{2k}.\qedhere\]
\end{proof}

\section{Displacement statistic}\label{sec:displacement}

In this section, we study the displacement statistics of Stirling permutations. As discussed in the introduction, this statistic measures how far cars park from their preferred parking spots in a parking function.  

\begin{definition}\label{def:displacement}
    For every $w\in Q_n$, if car $i$ 
    parks in spot $p(i)\in[2n]$, then the \textit{displacement} of car $i$ is $d(i)\coloneqq p(i)-w(i)$. 
    The \textit{(total)  displacement} of $w\in Q_n$ is
    \[\displaystyle{d(w)=\sum_{i=1}^{2n} d(i)}.\]
\end{definition}

Because every Stirling permutation is a parking function, the displacement of a car is always nonnegative. Moreover, by definition, cars with displacement equal to zero are lucky cars, while cars whose displacement is positive are unlucky.

We begin by recalling a result from Elder, Harris, Kretschmann, and Mart\'inez Mori~\cite{elder2023costsharing} that if $w\in Q_n$, then the displacement of $w$ is invariant under permutations of the entries of $w$, even though the resulting strings are not necessarily Stirling permutations. 
This result is a special case of~\cite[Lemma 3.1]{elder2023costsharing}, hence we omit its proof but state the result formally below.

\begin{lemma}\label{lem:constant displacement}\cite[Lemma 3.1]{elder2023costsharing}
    For every $w \in Q_n$, the displacement $d(w)$ is invariant under permuting the numbers in the one-line notation of $w$.
   In other words, for every permutation $\sigma$ of $[1,2n]$ 
    and every Stirling permutation $w\in Q_n$, let $\sigma(w)=w(\sigma(1))w(\sigma(2))\cdots w(\sigma(2n))$. Then $d(\sigma(w))=d(w)$.
\end{lemma}

We now determine the displacement of Stirling permutations.

\begin{corollary}\label{cor:displacement} 
For $w\in Q_n$, we have $d(w)=n^2$.   
\end{corollary}

\begin{proof}
For every parking function $\pi \in \operatorname{PF}_m$, the total displacement can be written as
$$d(\pi) = \binom{m+1}{2} - \sum_{k=1}^m \pi_m.$$
Thus, for $w \in Q_n$, we have
\[d(w) = \binom{2n+1}{2} - 2\sum_{k=1}^n k = n^2.\qedhere\]
\end{proof}

Definition~\ref{def:displacement} provides two versions of displacement. One version is for each car and the other version is for the entire Stirling permutation. Corollary~\ref{cor:displacement} addresses the latter of these for Stirling permutations. Now we turn our attention to the former and investigate ``compositions'' of $n^2$ that record the displacement data for each car when $w$ is in $Q_n$. 

\begin{definition}
    For $w\in Q_n$, the \textit{displacement composition} of $w$ is the $2n$-tuple encoding the displacements of each car, which is 
     \[(d(1),d(2),\ldots,d(2n))\in\mathbb{N}^{2n}.\]
     Let $\mathrm{dis}(w)$ denote the displacement composition of $w$.
\end{definition}

As discussed before, the displacement $d(i)=0$ if and only if car $i$ is lucky. In particular, the first entry of $\mathrm{dis}(w)$ is always $0$.

\begin{example} 
For the Stirling permutation $w = 11244233$, the displacement composition is $\mathrm{dis}(w) = (0,1,1,0,1,4,4,5)$.
\end{example}


Recall that $1\leq \mathrm{lucky}(w)\leq n$ by Lemma~\ref{lem:lucky_range}(c). Thus, we can bound the number of nonzero entries in $\mathrm{dis}(w)$, whenever $w\in Q_n$.

\begin{corollary}\label{cor:bounds for m_D}
For every $w\in Q_n$, we have 
$1 \le |\{i \in [2n] : d(i) = 0\} | \le n$.
\end{corollary}

Two distinct Stirling permutations may share the same displacement composition, indicating that displacement compositions do not uniquely identify a Stirling permutation. For instance, the displacement composition 
$(0, 1, 0, 1, 3, 4)$ corresponds to both 
$113322$ and $331122$. 
However, 
extremely lucky Stirling permutations are uniquely determined by their displacement compositions. 
That is,
no two distinct extremely lucky Stirling permutations have the same displacement composition. This is the main result in this section, and we start with a technical lemma used in the proof of that result.

\begin{lemma}\label{lem:unlucky preference and displacement}
    Let $w \in Q_n$ be an extremely lucky permutation.  For $i\in[n]$, the following properties hold.
    \begin{enumerate}
        \item[(a)] The $i$th unlucky car of $w$ prefers spot $n - i +1$. 
        \item[(b)] The $i$th unlucky car of $w$ has displacement $2i-1$.
    \end{enumerate}
\end{lemma}
\begin{proof}
    Let $w \in Q_n$ be an extremely lucky permutation. 
    Hence, we have $\mathrm{lucky}(w)=n$ and there are $n$ unlucky cars. 
    \begin{enumerate}
    \item[(a)] This is an immediate consequence of Proposition~\ref{prop:extremely lucky second cars in order}.

    \item[(b)] We proceed by induction. Suppose that car $j$ is the first unlucky car. By (a) we have that car $j$ must prefer spot $n$. Since car $j$ is the second car to prefer spot $n$, and no other cars have yet been unlucky, then car $j$ parks in spot $n+1$. Thus, its displacement is $(n+1) - n = 2(1)-1$, as claimed.

    Now fix $i \ge 1$ and assume that the result holds for all $j \le i$. Thus, the $j$th unlucky car parks in spot $(n-j+1)+(2j-1) = n+j$ for all $j\le i$.
    Let car $k$ be the $(i+1)$th unlucky car.
    By (a), this car $k$ must prefer spot $n-i$.
    Since car $k$ is unlucky, 
    and by Proposition~\ref{prop:extremely lucky second cars in order}, we know that spots in $[n-i, n+i]$ are already occupied and the next available spot is $n+i+1$. 
    Thus, car $k$ parks in spot $n+i+1$. Hence, its displacement is $(n+i+1) - (n-i) = 2i+1 = 2(i+1)-1$, completing the proof. \qedhere
    \end{enumerate}
\end{proof}

We are now ready to establish the injectivity of the map $w \mapsto \mathrm{dis}(w)$ where $w$ belongs to the set of extremely lucky Stirling permutations of order~$n$.

\begin{theorem}\label{thm:displacement_implies_unique} 
Let $w$ be an extremely lucky Stirling permutation. The displacement composition $\mathrm{dis}(w)$ of $w$ uniquely determines  $w$. 
\end{theorem}

\begin{proof}
Suppose that $w \in Q_n$ is an extremely lucky Stirling permutation, and consider its displacement composition $\mathrm{dis}(w)$. Suppose that there exists another $w' \in Q_n$ such that $\mathrm{dis}(w') = \mathrm{dis}(w)$. 

The $0$ entries in a displacement composition correspond to the lucky cars in the parking function, so we must have $\mathrm{Lucky}(w) = \mathrm{Lucky}(w')$, and hence $w'$ must be extremely lucky as well. By Proposition~\ref{prop:extremely lucky second cars in order}, the values of $w'$ in each of the positions of nonzero entries of $\mathrm{dis}(w)$ must be $n, n-1, \ldots, 1$, in order from left to right. Moreover, these must be the second appearances of each of these numbers in the one-line notation of $w'$.

Now, to obey the Stirling property, the first occurrence of $n$ in $w'$ must be in the rightmost unclaimed (lucky) position appearing to the left of the (already determined) second appearance of $n$ in $w'$. Similarly, the first occurrence of $n-1$ in $w'$ must be in the rightmost unclaimed position appearing to the left of the second appearance of $n-1$, and so on.

Each of these positions is entirely determined by $\mathrm{dis}(w)$, and so in fact we must have $w = w'$.
\end{proof}

We demonstrate the result above in the following example. 
\begin{example}
    The displacement composition $(0, 0, 0, 1, 3, 0, 0, 5, 7, 9)$ for $w \in Q_5$ tells us that $\mathrm{Lucky}(w) = \{1,2,3,6,7\}$. Moreover, Proposition~\ref{prop:extremely lucky second cars in order} tells us that
    $$ w = \underline{\ \phantom{1} \ } \ \underline{\ \phantom{1} \ } \ \underline{\ \phantom{1} \ } \ \ 5 \ \  4 \ \ \underline{\ \phantom{1} \ } \ \underline{\ \phantom{1} \ } \ \ 3 \ \ 2 \ \ 1.$$
    The Stirling condition tells us that the first appearance of $5$ in $w$ must be in position $3$. Then we see that the first appearance of $4$ in $w$ must be in position $2$. Similarly, the first position of $3$ in $w$ must be $w(7)$, the first position of $2$ must be $w(6)$, and the first position of $1$ must be $w(1)$. Therefore, we have
    $$w = \underline{\ 1 \ } \ \underline{\ 4 \ } \ \underline{\ 5 \ } \ \ 5 \ \ 4 \ \ \underline{\ 2 \ } \ \underline{\ 3 \ } \ \ 3 \ \ 2 \ \ 1.$$
\end{example}


To conclude this section, we give a restatement of Corollary~\ref{cor:extremely lucky are catalan} in terms of displacement compositions.

\begin{corollary}\label{cor:displace_num}
     The number of Stirling permutations whose displacement composition has exactly $n$ nonzero parts is $C_n$, 
    the $n$th Catalan number.
\end{corollary}


\section{Open problems}\label{sec:open problems}

Finally, we propose a selection of open problems related to lucky cars and the displacement statistic on Stirling permutations.

To begin with, recall that in Section~\ref{sec:small cardinality}, we gave several properties of three-element admissible lucky sets. The following problems remain unanswered. 

\begin{problem}
    Characterize and enumerate the three-element $n$-admissible lucky sets.
    More generally, for fixed $n$, how many $n$-admissible lucky sets are there?
\end{problem}


Equation~\eqref{eq:GesselSeo} gives a generating function for the lucky statistic on parking functions. 
Table~\ref{table:gen fun} was generated via an exhaustive search and provides analogous data for the generating function defined by the lucky statistic on Stirling permutations defined by
$$T_n(q)=\sum_{w\in Q_n}q^{\mathrm{lucky}(w)}.$$
The sequences of coefficients in Table~\ref{table:gen fun} appear to be new, as a search on the OEIS~\cite{OEIS} did not yield these sequences at the time of publication. We do not have conjecture for formulas for these coefficients.
Corollary~\ref{cor:extremely lucky are catalan}
implies that, for all $n\geq 1$, the leading coefficient of $T_n(q)$ is the Catalan number $C_n$. Theorem~\ref{thm:extremely unlucky} shows that the coefficient of $q$ in $T_n(q)$ is given by $(n-1)!$.
\begin{table}[htbp]
{\renewcommand{\arraystretch}{1.5}
\begin{center}
\begin{tabular}{|c||r|} \hline
\ $n$ \ &amp; \multicolumn{1}{|c|}{$T_n(q)$}\\\hline
\hline
2 &amp; $2q^2+q$ \\\hline
3 &amp; $5q^3 + 8q^2 + 2q$ \\\hline
4 &amp; $14q^4 + 49q^3 + 36q^2 + 6q$\\\hline
5 &amp; $42q^5 + 268q^4 + 417q^3 + 194q^2 + 24q$\\\hline
6 &amp; $132q^6 + 1374q^5 + 3876q^4 + 3665q^3 + 1228q^2 + 120q$\\\hline
7 &amp; $429q^7 + 6752q^6 + 31231q^5 + 52353q^4 + 34675q^3 + 8975q^2 + 720q$\\\hline
\end{tabular}
\end{center}
}
\caption{The polynomials $T_n(q)$ for $2\leq n\leq 7$.}\label{table:gen fun}
\end{table}
We thus pose the following questions.
\begin{problem}
    Determine a formula for $T_n(q)$ for all $n\geq 1$.
        Are the polynomials $T_n(q)$ unimodal? 
        Are they real-rooted?
\end{problem}
The bound determined in Corollary~\ref{cor:bounds for m_D}, suggests the following avenue of research.

\begin{problem}\label{problem:existance}
Determine if, for $i\in[n,2n-1]$, there exists $w\in Q_n$ such that $\mathrm{dis}(w)$ has exactly $i$ nonzero entries. Equivalently, can we always find a Stirling permutation with $i$ unlucky cars?
\end{problem}

Table~\ref{tab:displacement comps} provides some data in the case where $n=3$, listing all possible displacement compositions and the Stirling permutations that give rise to those displacement compositions. 

Theorem~\ref{thm:extremely unlucky} establishes that there are $(n-1)!$ Stirling permutations in $Q_n$ whose displacement composition has exactly $1$ zero entry. Moreover, by Corollary~\ref{cor:displace_num}, there are $C_n$ Stirling permutations in $Q_n$ whose displacement composition has exactly $n$ nonzero parts. As a follow-up question to Problem~\ref{problem:existance}, we can thus try to interpolate between these two extreme cases,  enumerating the Stirling permutations whose displacement compositions have $k$ zero parts.

\begin{problem}
    For $k \in [2, n-1]$, determine
    $$\big| \{w \in Q_n: \mathrm{dis}(w) \text{ has $k$ zero parts}\} \big|.$$
    Equivalently, how many $w \in Q_n$ have exactly $k$ lucky cars?
\end{problem}

It is also of interest to understand displacement compositions arising from general Stirling permutations.  

\begin{problem}\label{problem:displacement comps}
Let 
$\mathcal{D}_n\coloneqq\{\mathrm{dis}(w):w\in Q_n\}$.
    Characterize and enumerate the elements of $\mathcal{D}_n$.
\end{problem}

On a more specific level, one can try to understand the fibers of the map $w \mapsto \mathrm{dis}(w)$. In that direction, a related problem is to determine the number of Stirling permutations with a fixed displacement composition.
\begin{problem}
 Fix $\textbf{m} \in \mathcal{D}_n$. 
Characterize and enumerate the elements of the set
$$\mathcal{S}_n({\textbf{m}})\coloneqq\{w\in Q_n: \mathrm{dis}(w)=\textbf{m}\}.$$
Put another way, what properties define the collection of Stirling permutations whose displacement compositions are equal to a given vector? Also, are there operations on Stirling permutations whose orbits define the fibers of that map?
\end{problem}

\section{Acknowledgments}
We appreciate the thoughtful comments and suggestions of an anonymous referee. We are also grateful to the organizers of the workshop GEMS of Combinatorics, during which this project began, and the American Institute of Mathematics for hosting the GEMS workshop.

\begin{table}[H]
\centering
{\renewcommand{\arraystretch}{1.2}
    \centering
    \begin{tabular}{|c||c|}
\hline 
&amp; $\mathrm{dis}(w)$, where $w\in Q_3$\\[-.05in]
\ \ $k$ \ \ &amp; has $k$ nonzero parts \\ \hline \hline
\multirow{5}*{$3$} &amp;  $\mathrm{dis}(123321)=(0,0,0,1,3,5)$\\
 &amp; $\mathrm{dis}(133221)=(0,0,1,0,3,5)$\\ 
&amp;$\mathrm{dis}(233211)=(0,0,1,3,0,5)$\\
&amp;$\mathrm{dis}(331221)=(0,1,0,0,3,5)$\\
&amp;$\mathrm{dis}(332211)=(0,1,0,3,0,5)$\\\hline
\multirow{8}*{$4$} 
&amp;$\mathrm{dis}(122331)=(0,0,1,1,2,5)$\\
&amp;$\mathrm{dis}(122133)=(0,0,1,3,2,3)$\\
&amp;$\mathrm{dis}(133122)=(0,0,1,1,3,4)$\\
&amp;$\mathrm{dis}(221331)=(0,1,0,1,2,5)$\\
&amp;$\mathrm{dis}(113322)=(0,1,0,1,3,4)$\\
&amp;$\mathrm{dis}(331122)=(0,1,0,1,3,4)$\\
&amp;$\mathrm{dis}(221133)=(0,1,0,3,2,3)$\\
&amp;$\mathrm{dis}(223311)=(0,1,1,2,0,5)$\\\hline
\multirow{2}*{$5$} 
&amp;$\mathrm{dis}(112233)=(0,1,1,2,2,3)$\\
&amp;$\mathrm{dis}(112332)=(0,1,1,1,2,4)$\\\hline
\end{tabular}
}
 \caption{Displacement compositions arising from Stirling permutations in $Q_3$, aggregated by the number of nonzero parts; i.e., by the number of unlucky cars.}
    \label{tab:displacement comps}
\end{table}



\begin{thebibliography}{10}

\bibitem{displacement_hanoi}
Yasmin Aguillon, Dylan Alvarenga, Pamela~E. Harris, Surya Kotapati,
  J.~Carlos~MartÃƒÂ­nez Mori, Casandra~D. Monroe, Zia Saylor, Camelle Tieu, and
  Dwight Anderson~Williams II, On parking functions and the tower of {H}anoi,
  {\em Amer. Math. Monthly} {\bf 130} (2023), 618--624.

\bibitem{Beissinger1997}
Janet~S. Beissinger and Uri~N. Peled, A note on major sequences and external
  activity in trees, {\em Electron. J. Combin.} {\bf 4} (1997), Paper \#R4.

\bibitem{MR3408702}
Mikl\'{o}s B\'{o}na, editor, {\em Handbook of Enumerative Combinatorics},
  Discrete Mathematics and its Applications, CRC Press, 2015.

\bibitem{unit_pf}
S.~Alex Bradt, Jennifer Elder, Pamela~E. Harris, Gordon Rojas~Kirby, Eva
  Reutercrona, Yuxuan~(Susan) Wang, and Juliet Whidden, Unit interval parking
  functions and the $r$-{F}ubini numbers, {\em Matematica}  (2024), 370--384.

\bibitem{buck2023flattenedstirlingpermutations}
Adam Buck, Jennifer Elder, Azia~A. Figueroa, Pamela~E. Harris, Kimberly~J.
  Harry, and Anthony Simpson, Flattened {S}tirling permutations.
\newblock Arxiv preprint arXiv:2306.13034 [math.CO], 2023. Available at
  \url{https://arxiv.org/abs/2306.13034}.

\bibitem{inv_assort}
Douglas Chen, Pamela~E. Harris, J.~Carlos~Martinez Mori, Eric~J. Pabon-Cancel,
  and Gabriel Sargent, Permutation invariant parking assortments, {\em Enumer.
  Comb. Appl.} {\bf 4}(1) (2023), Article \#S2R4.

\bibitem{knaple}
Laura Colmenarejo, Pamela~E. Harris, Zakiya Jones, Christo Keller, Andr\'{e}s
  Ramos~Rodr\'{\i}guez, Eunice Sukarto, and Andr\'{e}s~R. Vindas-Mel\'{e}ndez,
  Counting {$k$}-{N}aples parking functions through permutations and the
  {$k$}-{N}aples area statistic, {\em Enumer. Comb. Appl.} {\bf 1}(2) (2021),
  \#S2R11.

\bibitem{Diaconis-Hicks}
Persi Diaconis and Angela Hicks, Probabilizing parking functions, {\em Adv. in
  Appl. Math.} {\bf 89} (2017), 125--155.

\bibitem{DIAZLOPEZ20191674}
Alexander Diaz-Lopez, Pamela~E. Harris, Erik Insko, Mohamed Omar, and Bruce~E.
  Sagan, Descent polynomials, {\em Discrete Math.} {\bf 342} (2019),
  1674--1686.

\bibitem{elder2023costsharing}
Jennifer Elder, Pamela~E. Harris, Jan Kretschmann, and J.~Carlos~MartÃƒÂ­nez
  Mori, Cost-sharing in parking games.
\newblock Arxiv preprint arXiv:2309.12265 [math.CO], 2023. Available at
  \url{https://arxiv.org/abs/2309.12265}.

\bibitem{flat_pf}
Jennifer Elder, Pamela~E. Harris, Zoe Markman, Izah Tahir, and Amanda Verga, On
  flattened parking functions, {\em J. Integer Sequences} {\bf 26} (2023),
  \href{https://cs.uwaterloo.ca/journals/JIS/VOL26/Harris/harris3.html}{Paper 23.5.8}.

\bibitem{ELIZALDE2021105429}
Sergi Elizalde, Descents on quasi-{S}tirling permutations, {\em J. Combin.
  Theory Ser. A} {\bf 180} (2021), 105429.

\bibitem{elizalde2022descents}
Sergi Elizalde, Descents on nonnesting multipermutations, {\em S\'em. Lothar.
  Combin.} {\bf 89B} (2023), 103846.

\bibitem{flajolet-poblete-viola}
Philippe Flajolet, Patricio Poblete, and Alfredo Viola, {On the analysis of
  linear probing hashing}, Research Report RR-3265, {INRIA}, 1997.  
\newblock Available at \url{https://inria.hal.science/inria-00073424}.

\bibitem{GesselandSeo}
Ira Gessel and Seunghyun Seo, A refinement of {C}ayley's formula for trees,
  {\em Electron. J. Combin.} {\bf 11} (2005), \#R27.

\bibitem{MR462961}
Ira Gessel and Richard~P. Stanley, {S}tirling polynomials, {\em J. Combin.
  Theory Ser. A} {\bf 24} (1978), 24--33.

\bibitem{MesaPaper}
Nicolle Gonz\'alez, Pamela~E. Harris, Gordon Rojas~Kirby, Mariana Smit
  Vega~Garcia, and Bridget~E. Tenner, Mesas of {S}tirling permutations.
\newblock Arxiv preprint arXiv:2306.12158 [math.CO], 2023. Available at
  \url{https://arxiv.org/abs/2306.12158}.

\bibitem{harris2023lucky}
Pamela~E. Harris, Jan Kretschmann, and J.~Carlos~MartÃƒÂ­nez Mori, Lucky cars and
  the {Q}uicksort algorithm, {\em Amer. Math. Monthly} {\bf 131} (2024),
  417--423.

\bibitem{Janson}
Svante Janson, Asymptotic distribution for the cost of linear probing hashing,
  {\em Random Structures Algorithms} {\bf 19} (2001), 438--471.

\bibitem{Knuth1998}
Donald~E. Knuth, {\em The Art of Computer Programming},
 {\it Volume 3: Sorting and Searching}, 2nd ed.,
 Addison Wesley Longman, 1998.

\bibitem{konheim1966occupancy}
Alan~G. Konheim and Benjamin Weiss, An occupancy discipline and applications,
  {\em SIAM J. Appl. Math.} {\bf 14} (1966), 1266--1274.

\bibitem{Larcombe}
Peter~J. Larcombe, The $18$th century {C}hinese discovery of the {C}atalan
  numbers, {\em Mathematical Spectrum} {\bf 32} (1999/2000), 5--7.

\bibitem{unit_perm}
Lucas~Chaves Meyles, Pamela~E. Harris, Richter Jordaan, Gordon~Rojas Kirby, Sam
  Sehayek, and Ethan Spingarn, Unit-interval parking functions and the
  permutohedron.
\newblock To appear in \emph{J. Comb.} Arxiv preprint arXiv:2305.15554
  [math.CO], 2023. Available at \url{https://arxiv.org/abs/2305.15554}.

\bibitem{OEIS}
{OEIS Foundation Inc.}, The {O}n-{L}ine {E}ncyclopedia of {I}nteger
  {S}equences, 2023.
\newblock Published electronically at \url{https://oeis.org}.

\bibitem{Schumacher_Descents_PF}
Paul R.~F. Schumacher, Descents in parking functions, {\em J. Integer Sequences}
  {\bf 21} (2018), \href{https://cs.uwaterloo.ca/journals/JIS/VOL21/Schumacher/schu5.html}{Paper 18.2.3}.

\bibitem{shankar2023enumeration}
Umesh Shankar, Enumeration of flattened $k$-{S}tirling permutations with
  respect to descents.
\newblock Arxiv preprint arXiv:2307.07730 [math.CO], 2023. Available at
  \url{https://arxiv.org/abs/2307.07730}.

\bibitem{StanleyECVol2}
Richard~P. Stanley, {\em Enumerative Combinatorics, {V}ol. 2}, 2nd ed.,
  Vol.~62 of {\em Cambridge Studies in Advanced Mathematics}, Cambridge
  University Press, 1999.

\bibitem{StanleyECVol1}
Richard~P. Stanley, {\em Enumerative Combinatorics. {V}ol. 1}, 2nd ed.,
  Vol.~49 of {\em Cambridge Studies in Advanced Mathematics}, Cambridge
  University Press, 2012.

\bibitem{stanley_2015}
Richard~P. Stanley, {\em Catalan Numbers}, Cambridge University Press, 2015.

\bibitem{stanley2023enumerative}
Richard~P. Stanley and Mei Yin, Some enumerative properties of parking
  functions.
\newblock Arxiv preprint arXiv:2306.08681 [math.CO], 2023. Available at
  \url{https://arxiv.org/abs/2306.08681}.

\end{thebibliography}



\bigskip
\hrule
\bigskip

\noindent 2020 {\it Mathematics Subject Classification}:
Primary 05A05; Secondary 05A15.

\noindent \emph{Keywords:} parking function, Stirling permutation, lucky statistic, displacement statistic, Catalan number.


\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000108},
\seqnum{A000142},
\seqnum{A008277}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received April 19 2024;
revised versions received  April 21 2024; August 9 2024.
Published in {\it Journal of Integer Sequences}, August 9 2024.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                
</pre></body></html>