\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools,booktabs,microtype,xcolor}
\usepackage{xurl}
\usepackage[colorlinks=true,allcolors=blue!50!black]{hyperref}
\setlength{\emergencystretch}{2em}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}\newtheorem{definition}[theorem]{Definition}
\newcommand{\Lucky}{\operatorname{Lucky}}
\newcommand{\lean}[1]{{\small\path{#1}}}
\title{Three-Element Lucky Sets of Stirling Permutations}
\author{Yuran Xiu\\IIIS, Tsinghua University\\
\texttt{xiuyr23@mails.tsinghua.edu.cn}}
\hypersetup{pdfauthor={Yuran Xiu}}
\date{14 October 2026}
\begin{document}
\maketitle
\begin{abstract}
We characterize the three-element sets of lucky car indices that occur
when a Stirling permutation of order $n$ is used as a parking function.
A set $\{1,x,y\}$, with $1<x<y<2n$, is admissible precisely when $x$
is odd, or $x$ is even and $y$ is odd with $x<n$, or both are even
with $x+y\leq2n$. Explicit Stirling words realize every permitted case.
The number of admissible sets is
$(n-1)(n-2)+2nh-3h(h+1)/2$, where $h=\lfloor(n-1)/2\rfloor$.
This answers the three-element characterization and enumeration question
in Problem~46 of Colmenarejo et al. The complete classification,
parking constructions, and enumeration have been checked in Lean.
\end{abstract}

\section{Statement and scope}
A \emph{Stirling permutation of order $n$} is a word of length $2n$
containing two copies of each label in $[n]=\{1,\ldots,n\}$, such that
all letters strictly between the two copies of a label $a$ are greater
than $a$. Denote this set of words by $Q_n$.

Interpret a word $w=w_1\cdots w_{2n}$ as preferences of cars arriving
in the order $1,\ldots,2n$. Car $j$ parks at the first unoccupied
position at least $w_j$. All cars park in $[2n]$: the nondecreasing
rearrangement of the preferences is $1,1,2,2,\ldots,n,n$, whose
$j$th entry $\lceil j/2\rceil$ is at most $j$, the usual parking-function
criterion. Car $j$ is \emph{lucky} if it parks at $w_j$ itself. A set
$S$ is \emph{$n$-admissible} if $S=\Lucky(w)$ for some $w\in Q_n$.

Colmenarejo et al.~\cite{CEH} studied these sets, including selected
three-element families. Their Problem~46 first asks for a complete
characterization and enumeration of the three-element admissible sets,
and then asks the more general question for arbitrary cardinalities.
The following theorem answers the first question.

\begin{theorem}\label{thm:classification}
Let $n\geq1$ and let $S$ have three elements. Then $S$ is
$n$-admissible if and only if $S=\{1,x,y\}$ with $1<x<y<2n$ and
one of the following disjoint conditions holds:
\begin{enumerate}
\item[(A)] $x$ is odd;
\item[(B)] $x$ is even, $y$ is odd, and $x<n$;
\item[(C)] $x$ and $y$ are even, and $x+y\leq2n$.
\end{enumerate}
\end{theorem}

\begin{corollary}\label{cor:count}
Let $N(n)$ be the number of three-element $n$-admissible sets and put
$h=\lfloor(n-1)/2\rfloor$. For $n\geq1$,
\begin{equation}\label{eq:count}
 N(n)=(n-1)(n-2)+2nh-\frac{3h(h+1)}2.
\end{equation}
Equivalently,
\begin{equation}\label{eq:paritycount}
 N(2r)=\frac{13r^2-17r+4}{2}\quad(r\geq1),\qquad
 N(2r+1)=\frac{13r^2-3r}{2}\quad(r\geq0).
\end{equation}
\end{corollary}
The first nine values, for $n=1,\ldots,9$, are
$0,0,5,11,23,35,54,72,98$. We count distinct lucky \emph{sets}, not
the number of words realizing each set. No characterization of sets
with four or more elements is asserted.

\section{Necessary conditions}
\begin{lemma}\label{lem:index}
In any successful parking word with two copies of each label in $[n]$,
if car $j$ is lucky with preference $b$, then $j+b\leq2n$.
\end{lemma}
\begin{proof}
Immediately before car $j$, position $b$ is still free. Each earlier
car with preference at most $b$ must have parked below $b$: at its
arrival $b$ was available, but it did not occupy $b$. Thus at most
$b-1$ of the $2b$ occurrences of labels in $[b]$ appeared before
position $j$. At least $b+1$ remain in a suffix of length $2n-j+1$.
This gives $b+1\leq2n-j+1$.
\end{proof}

\begin{lemma}\label{lem:interval}
Let $x$ be the second lucky index and put $a=w_1$. After the first
$j$ cars, for $1\leq j<x$, the occupied positions are exactly
$[a,a+j-1]$. Every preference in that prefix is at least $a$.
\end{lemma}
\begin{proof}
Car 1 occupies $a$. Each subsequent car before $x$ is unlucky, so its
preferred position is in the current occupied interval. It parks at
the first position just to the right of that interval. Induction gives
both assertions.
\end{proof}

\begin{lemma}\label{lem:minimum}
A new strict record minimum in a Stirling word occurs at an odd
position. In particular, the first occurrence of 1 is odd-indexed and
lucky.
\end{lemma}
\begin{proof}
If $w_j$ is smaller than every earlier letter, every label seen before
$j$ must have both copies before $j$. Otherwise its pair would enclose
the smaller label $w_j$, violating the Stirling condition. The prefix
has even length, so $j$ is odd. No preference greater than 1 can occupy
position 1, proving the last assertion.
\end{proof}

Suppose now that $\Lucky(w)=\{1,x,y\}$ with $1<x<y$. Car 1 is
always lucky, and Lemma~\ref{lem:index} gives $y<2n$. If $x$ is odd,
condition (A) holds. Assume $x$ is even, set $a=w_1$, and put $c=w_x$.
By Lemma~\ref{lem:interval}, a lucky preference $c$ must satisfy either
$c<a$ or $c\geq a+x-1$. The former would be a new strict record
minimum, contrary to Lemma~\ref{lem:minimum}. Therefore
$a+x-1\leq c\leq n$, and $x\leq n$. Equality $x=n$ forces
$a=1$ and $c=n$. Immediately after car $x$, every preferred position
in $[n]$ would then be occupied, leaving no possible third lucky car.
Hence
\begin{equation}\label{eq:evensecond}
 x<n\qquad\text{when the second lucky index is even}.
\end{equation}
If $y$ is odd this proves (B). If $y$ is even, the only odd lucky
index is 1. Lemma~\ref{lem:minimum} forces $w_1=1$. Positions
$1,\ldots,x-1$ are occupied before car $x$ and remain occupied, so
the lucky preference $b=w_y$ satisfies $b\geq x$.
Lemma~\ref{lem:index} now gives $x+y\leq b+y\leq2n$, proving (C).

\section{Words realizing every permitted triple}\label{sec:constructions}
For integers $a\leq b$, let
\[
 D(a,b)=a\,a\,(a+1)\,(a+1)\cdots b\,b,
\]
and let $D(a,b)$ be empty for $a>b$. If $U$ is an increasing list of
integers, $D(U)$ doubles each entry in its list order. Juxtaposition
means word concatenation; an arithmetic expression such as $(2r)$
between blocks denotes one letter of that value.

We use two elementary parking observations. A consecutive doubled run
whose first preference is free has exactly one lucky car, its first.
After the second copy of a label $a$ has parked, position $a+1$ is
occupied, so the first copy of the next label is unlucky. This remains
true if some larger positions were occupied before the run. Second,
if the occupied positions form $[L,H]$, an increasing doubled run
starting at an occupied preference and with consecutive label gaps at
most 2 is entirely unlucky. Each pair extends the right endpoint by 2,
so the next preference remains within the occupied interval. Both
observations follow directly by induction from the first-free rule.

\subsection[Odd x, odd y]{Odd $x$, odd $y$}
Write $x=2r+1$ and $y=2r+2t+1$, where $r,t\geq1$, and let
$u=n-r-t\geq1$. Use
\begin{equation}\label{eq:oddodd}
 D(u+t+1,n)\ D(u+1,u+t)\ D(1,u).
\end{equation}
Each of the three runs starts with a preference below all earlier
preferences, hence at a free position. By the first observation, only
the first car of each run is lucky. Their indices are
$1,2r+1,2r+2t+1$.

\subsection[Odd x, even y]{Odd $x$, even $y$}
Write $x=2r+1$ and $y=2r+2t+2$, where $r\geq1$, $t\geq0$, and
$r+t+2\leq n$. Use
\begin{equation}\label{eq:oddeven}
 D(3,r+2)\ 1\ D(r+3,r+t+2)\ 2\ 2\ 1\ D(r+t+3,n).
\end{equation}
The initial run has only its first car lucky and occupies $[3,2r+2]$.
The first 1, at position $x$, is lucky. The following $t$ doubled
labels extend the upper interval to $[3,y]$, since their first
preference $r+3$ is at most $2r+2$. The first 2, at position $y$,
is lucky. The second 2 and the closing 1 extend the occupied interval
to $[1,y+2]$. The final doubled tail is unlucky: its first preference
$r+t+3$ is at most $y+2$, and its labels are consecutive.

\subsection[Even x, even y]{Even $x$, even $y$}
Write $x=2r$, $y=2s$, where $1\leq r<s$ and $r+s\leq n$. Use
\begin{equation}\label{eq:eveneven}
\begin{split}
 &D(1,r-1)\ r\ D(2r+1,r+s)\ (2r)\ (2r)\\
 &\hspace{15mm} D(r+1,2r-1)\ r\ D(r+s+1,n).
\end{split}
\end{equation}
Before position $x$, the occupied interval is $[1,x-1]$, and only
car 1 has been lucky. For $r=1$, the displayed initial letter $r$
is itself car 1. The nonempty upper doubled block starts at preference
$x+1$ and occupies $[x+1,y]$; only its first car, at position $x$,
is lucky. The next letter $2r=x$ is at position $y$ and fills the
gap at $x$, giving the third lucky car. All subsequent preferences
in the middle block and the closing $r$ are occupied. At that point
the occupied interval is $[1,2(r+s)]$. The final tail is also unlucky,
since its initial preference is $r+s+1$.

\subsection[Even x, and y = x+1]{Even $x$, and $y=x+1$}
Write $x=2r$; the condition $x<n$ gives $x+1\leq n$. Use
\begin{equation}\label{eq:adjacent}
\begin{split}
 &D(1,r-1)\ r\ x\ (x+1)\ (x+1)\ x\\
 &\hspace{15mm}D(r+1,x-1)\ r\ D(x+2,n).
\end{split}
\end{equation}
The first $x-1$ cars occupy $[1,x-1]$ with only car 1 lucky.
The next two preferences, $x$ and $x+1$, are free and occur at
positions $x$ and $y$. The next two cars extend occupancy to
$[1,x+3]$. The middle doubled run and closing $r$ extend it to
$[1,2x+2]$, and the final tail stays behind that frontier. Thus
there are exactly three lucky cars. When $r=1$ and $n=3$, this
construction is the word $123321$.

\subsection[Even x, odd y at least x+3]{Even $x$, odd $y\geq x+3$}
Write $x=2r$, where $r\geq1$ and $n\geq x+1$. Let $U$ be the
increasing list $[r+2,n]$ with $x+1$ omitted, and put
$t=(y-x-3)/2$. Then $0\leq t\leq n-r-2=|U|$.
Split $U$ into its first $t$ entries $U_0$ and the remaining entries
$U_1$. Use
\begin{equation}\label{eq:separated}
 D(2,r)\ (r+1)\ (x+1)\ (x+1)\ (r+1)\ D(U_0)\ 1\ 1\ D(U_1).
\end{equation}
After the first $x-1$ cars, the occupied interval is $[2,x]$, with
only car 1 lucky. The first $x+1$ occurs at position $x$ and is
lucky; its second copy and the closing $r+1$ extend occupancy to
$[2,x+3]$. The least element of $U$, if present, is at most $x+3$,
and successive elements differ by at most 2. The frontier observation
shows that $D(U_0)$ extends occupancy to $[2,y]$ and has no lucky
car. The first 1 occurs at position $y$ and is lucky. Its second
copy leaves $[1,y+1]$ occupied. The remaining run $D(U_1)$ is
unlucky by the same frontier bound, including when $U_0$ is empty.

\subsection{Checking the Stirling condition}
Every construction uses each label in $[n]$ exactly twice: the displayed
blocks partition the unused labels, and the separately displayed
letters supply the omitted pairs. In \eqref{eq:oddodd} all pairs
are adjacent. In \eqref{eq:oddeven}, only the pair of 1's can enclose
other letters, all greater than 1. In \eqref{eq:eveneven}, the pair
of $r$'s encloses only labels greater than $r$. In
\eqref{eq:adjacent}, the pair of $x$'s encloses $x+1$, and the
pair of $r$'s encloses only larger letters. In
\eqref{eq:separated}, the pair of $r+1$'s encloses only $x+1>r+1$.
Thus all five words belong to $Q_n$. The preceding parking analyses
give precisely $\{1,x,y\}$ in each case. Together with the necessary
conditions, they prove Theorem~\ref{thm:classification}.

\section{Enumeration}
The cases of Theorem~\ref{thm:classification} are disjoint. In case
(A), put $x=2a+1$ for $1\leq a\leq n-2$. There are
$2n-2a-2$ choices of $y$, giving $(n-1)(n-2)$ triples when $n\geq2$;
the count is also zero at $n=1$.
In case (B), put $x=2a$ and $y=2b+1$. Then
$1\leq a\leq h$ and $a\leq b\leq n-1$, so the count is
\[
 \sum_{a=1}^h(n-a)=nh-\frac{h(h+1)}2.
\]
In case (C), put $x=2a$ and $y=2b$. The constraints are
$1\leq a\leq h$ and $a<b\leq n-a$, giving
\[
 \sum_{a=1}^h(n-2a)=nh-h(h+1).
\]
Their sum proves \eqref{eq:count}. Substituting $h=r-1$ for $n=2r$
and $h=r$ for $n=2r+1$ gives \eqref{eq:paritycount}. In particular,
$n=1,2$ have no admissible triples, as required.

\section{Formal verification}
The project \lean{stirling-lucky-triples} defines Stirling words,
the actual least-free parking process, and lucky-index equality.
It proves the necessity lemmas and all five constructions, including
their nesting, multiplicities, parking success, and absence of further
lucky cars. The declarations \lean{StirlingLucky.classification},
\lean{StirlingLucky.enumeration}, \lean{StirlingLucky.exact_count_even},
and \lean{StirlingLucky.exact_count_odd} are the unconditional
classification and counting endpoints.

The 25-module build uses Lean 4.27.0 and mathlib revision
\lean{a3a10db0e9d66acbebf76c5e6a135066525ac900}.
With the dependencies pinned by \lean{lake-manifest.json} provisioned,
run \texttt{\small python3 scripts/verify.py}. The successful build and
transitive axiom-audit logs are recorded in
\lean{verification/result.json}; the definition correspondence is
documented in \lean{STATEMENT_MATCH_AUDIT.txt} and
\lean{SEMANTIC_STATEMENT_AUDIT.txt}. Only \lean{propext},
\lean{Classical.choice}, and \lean{Quot.sound} occur in the final
transitive axiom lists. The proof uses no placeholders, additional
mathematical axioms, or native computation. The pinned compiler and
cached dependency proof objects are trusted. Formal checking verifies
the declarations rather than this manuscript's prose or its
bibliographic status.

\begin{thebibliography}{9}
\bibitem{CEH}
L. Colmenarejo, A. Dawkins, J. Elder, P. E. Harris,
K. J. Harry, S. Kara, D. Smith, and B. E. Tenner,
\emph{On the lucky and displacement statistics of Stirling permutations},
J. Integer Sequences \textbf{27} (2024), Article 24.6.7.
\url{https://cs.uwaterloo.ca/journals/JIS/VOL27/Tenner/tenner12.pdf}.
\end{thebibliography}
\end{document}