<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[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}}}


\usepackage{tikz}
\usepackage{tkz-tab}
\usetikzlibrary{matrix}
\usetikzlibrary{calc}
\usetikzlibrary{fit}
\newcommand{\Lar}{0.5}
\newcommand{\Ray}{0.8}

\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}

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

\begin{center}
\vskip 1cm{\LARGE\bf Two New Integer Sequences Related to \\
\vskip .1in
Crossroads and Catalan Numbers
}
\vskip 1cm
\large
Julien Rouyer and Alain Ninet\\
Laboratoire de Math\'ematiques de Reims (LMR) - CNRS UMR 9008\\
Universit\'e de Reims Champagne-Ardenne \\
U.F.R. Sciences Exactes et Naturelles\\
Moulin de la Housse - BP 1039\\
51687 Reims cedex 2\\
France \\
\href{mailto: julien.rouyer@univ-reims.fr}{\tt julien.rouyer@univ-reims.fr}\\
\href{mailto: alain.ninet@univ-reims.fr}{\tt alain.ninet@univ-reims.fr}\\
\end{center}

\vskip .2 in
\begin{abstract}
 The marriageable singles sequence represents the number of noncrossing partitions of the finite set $\{1,\ldots,n\}$ in which some pair of singleton blocks can be joined while remaining noncrossing.
 The lonely  singles sequence represents the number of all the other noncrossing partitions of the finite set $\{1,\ldots,n\}$ and is the difference between the Catalan numbers sequence and the marriageable singles sequence. 
 The first 16 terms of these sequences are given, as well as some of their properties.
 These sequences appear when one wants to count the number of ways to
 cross certain road intersections simultaneously.
\end{abstract}


\section{Introduction}

The number of noncrossing partitions of the finite set $\{1,\ldots,n\}$ (with $n$ a positive integer) is very well known to be the Catalan number $C_n$. See, for example, Stanley \cite[entry~159, p.\ 43]{Stanley2015} and Roman \cite[pp.\ 51--60]{Roman2015} for a quick introduction to Catalan numbers and noncrossing partitions.
Noncrossing partitions have been hugely studied, since at least Becker \cite{Becker1952}, where they are called \emph{planar rhyme schemes} but their systematic study began with Kreweras \cite{Kreweras1972} and Poupard \cite{Poupard1972}. Simion \cite{Simion2000} presents a summary of the related results available in 2000 and some further work can be found in McCammond \cite{Mccammond2006}, Callan \cite{Callan2008}  and Kim \cite{Kim2011}.

The study of combinatorial properties of crossroads led us to determine the number of noncrossing partitions such that no pair of singleton blocks $\{i\}$ and $\{j\}$ (with $i\neq j$) can be merged into the pair $\{i,j\}$ while the partition remains noncrossing.
These noncrossing partitions appear when one wants to determine the number of possible manners to cross simultaneously a road intersection in which entries and exits alternate, with the constraint that U-turns are prohibited. For a quick introduction to road intersection crossing management for intelligent vehicles, see Rouyer et al.\ \cite{Rouyer2022} and Bai et al.\ \cite{Bai2021}. 

In the remaining part of this section and in the next one, we give definitions and quick examples. We then prove some properties of both marriageable singles and lonely singles sequences. At the end, we give the first values of those sequences and formulate several conjectures concerning them.

In all the text, we let $\mathbb{N}$ denote the set of natural numbers, including 0.

\begin{definition}
For all $n\in\mathbb{N}$, we let $[n]$ denote the $n$-set $\{1,\dots,n\}$. In particular, $[0]=\emptyset$.
\end{definition}

\begin{definition}
Let $n$ be a non-negative integer and let $\pi=\{A_1,\dots,A_k\}$ be a partition of $[n]$ (i.e., $\cup_{i=1}^k A_i=[n]$ and for all $1\leq i&lt; j\leq k, A_i\cap A_j=\emptyset$ and for all $1\leq i\leq k, A_i\neq\emptyset$), this partition $\pi$ is said to be a
\begin{itemize}
\item {\it crossing partition\/} if there exist $1\leq i\leq k$ and $1\leq j\leq k$, $i\neq j$ and $a&lt;b\in A_i$ and $c&lt;d\in A_j$, such as $a&lt;c&lt;b&lt;d$;
\item {\it noncrossing partition\/}  if, for all $1\leq i&lt;j\leq k$, for all $a&lt;b\in A_i$, for all $c&lt;d\in A_j$, we have
\begin{align*}
~ &amp; a&lt;b&lt;c&lt;d,\\
 &amp; \text{ or } c&lt;d&lt;a&lt;b,\\
 &amp; \text{ or } a&lt;c&lt;d&lt;b,\\
 &amp; \text{ or } c&lt;a&lt;b&lt;d.
\end{align*}
\end{itemize}
\end{definition}

\begin{definition} 
A noncrossing partition $\pi$ of $[n]$ is called \emph{marriageable singles partition} if there exists a pair of singleton blocks $\{i\}$ and $\{j\}$ in $\pi$ that can be joined, the partition thus obtained remaining noncrossing.

More precisely, let $\pi=\{\,A_1,\dots,A_k\,\}$ be a noncrossing partition of $[n]$ with at least two singleton blocks $A_1=\{i\}$ and $A_2=\{j\}$. Then $\pi$ is a marriageable singles partition iff $\pi'=\{\,\{i,j\},A_3,\dots,A_k\,\}$ is a noncrossing partition of $[n]$.

Conversely, a noncrossing partition of $[n]$ is called \emph{lonely singles partition} if it is not a marriageable singles partition.

Let $M_n$ and $L_n$ be the number of marriageable singles and lonely singles partitions of $[n]$ respectively. The \emph{marriageable singles} and \emph{lonely singles sequences} are $(M_n)_{n \geq 0}$ and $(L_n)_{n \geq 0}$ respectively.
\label{def:LnMn}
\end{definition}

\begin{remark}
A partition that contains at most one singleton block is clearly a lonely singles partition. In an equivalent way, a marriageable singles partition contains at least two singleton blocks. 
\end{remark}

\begin{example}
The set $[4]$ has $5$ marriageable singles partitions, which are
\begin{align*}
\{\,\{1\}, \{2\}, \{3\}, \{4\}\,\} &amp;, &amp;\{\,\{1\}, \{2\}, \{3,4\}\,\} &amp;, &amp;\{\,\{1\}, \{2,3\}, \{4\}\,\}, \\
\{\,\{1,4\}, \{2\}, \{3\}\,\} &amp;, &amp;\{\,\{1,2\}, \{3\}, \{4\}\,\}&amp;. &amp;
\end{align*}

For example, $\pi=\{\,\{1,2\}, \{3\}, \{4\}\,\}$ is a marriageable singles partition because the singleton blocks $\{3\}$ and $\{4\}$ can be joined to give the noncrossing partition $\pi'=\{\,\{1,2\}, \{3,4\}\,\}$.

The set $[4]$ has $9$ lonely singles partitions, which are
\begin{align*}
\{\,\{1, 2, 3, 4\}\,\}&amp;, &amp; \{\,\{1, 2, 3\}, \{4\}\,\}&amp;, &amp; \{\,\{1, 2, 4\}, \{3\}\,\}, \\ 
\{\,\{1, 3, 4\}, \{2\}\,\}&amp;, &amp; \{\,\{1\}, \{2, 3, 4\}\,\}&amp;, &amp; \{\,\{1, 2\}, \{3, 4\}\,\},\\
\{\,\{1, 4\}, \{2, 3\}\,\}&amp;, &amp; \{\,\{1, 3\}, \{2\}, \{4\}\,\}&amp;, &amp; \{\,\{1\}, \{2, 4\}, \{3\}\,\}. 
\end{align*}
The first seven have no pair of singleton blocks and are clearly not marriageable singles partitions. The last two have only one pair of singleton blocks, but after merging it, they both give $\{\,\{1,3\}, \{2, 4\}\,\}$ which is a crossing partition.
\end{example}

\begin{lemma}
Let $C_n$ (for $n\geq 0$) denote the number of noncrossing partitions of $[n]$. Then we have $C_n=L_n+M_n$.
\label{lemma_somme}
\end{lemma}

\begin{proof}
As the set of noncrossing partitions is the disjoint union of the sets of lonely singles and marriageable singles partitions, the result follows immediately.
\end{proof}

\begin{remark}
It is well known that $C_n=\frac{1}{n+1}\binom{2n}{n}$ is the $n$th Catalan number. The sequence $(C_n)_{n\geq 0}$ is referenced as \seqnum{A000108} in the On-Line Encyclopedia of Integer Sequences \cite{oeis}.
\end{remark}

\begin{remark}
The unique partition of $[0]=\emptyset$ is the empty partition $\emptyset$. This partition is noncrossing (the first Catalan number is $C_0=1$) and it is a lonely singles partition.
\end{remark}

\section{Standard road intersection}

Noncrossing complete matchings of $2n$ points lying on a line and noncrossing complete set of chords are two of the many standard combinatorial objects counted by the Catalan numbers. Noncrossing complete matchings and noncrossing complete set of chords are in natural bijection with the noncrossing partitions, as explained by Stanley \cite[entries 59 and 61, p.\ 28]{Stanley2015}. 

Here we introduce some notions about road intersections corresponding to noncrossing sets of chords.

\begin{definition}
A road intersection with $n$ entries and $n$ exits that alternate is called a {\it standard road intersection of size} $n$. 

Let $E_1,\dots,E_n$ denote the entries and $X_1,\dots,X_n$ denote the exits of a standard road intersection of size $n$. These entries and exits are numbered clockwise (Figure \ref{fig:inter} gives such a representation of a standard road intersection of size $n=4$).

We use a bipartite graph to
graphically represent a way to simultaneously cross a standard road intersection (see Figures \ref{fig:cercle} and \ref{fig:cerclenonmax} for two examples with $n=4$). In these graphs, black vertices represent entries and white vertices represent exits. Each edge represents the crossing of the intersection by a vehicle going from an entry to an exit.

Each entry can be connected to each exit, unless restrictions are indicated.
\end{definition}

\begin{figure}
\centering
\begin{tikzpicture}[line cap=round,line join=round,&gt;=triangle 45,x=0.35cm,y=0.35cm]
\clip(2,-3) rectangle (16,11);
\draw [line width=\Lar pt] (3,6)-- (7,6);
\draw [line width=\Lar pt] (3,2)-- (7,2);
\draw [line width=\Lar pt] (7,6)-- (7,10);
\draw [line width=\Lar pt] (11,6)-- (11,10);
\draw [line width=\Lar pt] (7,2)-- (7,-2);
\draw [line width=\Lar pt] (11,2)-- (11,-2);
\draw [line width=\Lar pt] (11,6)-- (15,6);
\draw [line width=\Lar pt] (11,2)-- (15,2);
\draw [line width=\Lar pt,dash pattern=on 4pt off 4pt] (3,4)-- (7,4);
\draw [line width=\Lar pt,dash pattern=on 4pt off 4pt] (11,4)-- (15,4);
\draw [line width=\Lar pt,dash pattern=on 4pt off 4pt] (9,10)-- (9,6);
\draw [line width=\Lar pt,dash pattern=on 4pt off 4pt] (9,2)-- (9,-2);
\draw [-&gt;,line width=\Lar pt] (4,3) -- (6,3);
\draw [-&gt;,line width=\Lar pt] (12,3) -- (14,3);
\draw [-&gt;,line width=\Lar pt] (14,5) -- (12,5);
\draw [-&gt;,line width=\Lar pt] (6,5) -- (4,5);
\draw [-&gt;,line width=\Lar pt] (10,7) -- (10,9);
\draw [-&gt;,line width=\Lar pt] (8,9) -- (8,7);
\draw [-&gt;,line width=\Lar pt] (8,1) -- (8,-1);
\draw [-&gt;,line width=\Lar pt] (10,-1) -- (10,1);
\draw[color=black] (8,10) node {$E_1$};
\draw[color=black] (10,10) node {$X_1$};
\draw[color=black] (15,5) node {$E_2$};
\draw[color=black] (15,3) node {$X_2$};
\draw[color=black] (10,-2) node {$E_3$};
\draw[color=black] (8,-2) node {$X_3$};
\draw[color=black] (3,3) node {$E_4$};
\draw[color=black] (3,5) node {$X_4$};
\end{tikzpicture}
\caption{A Standard Road Intersection of size $n=4$.}
\label{fig:inter}
\end{figure}

\begin{definition}
For a given standard road intersection, an edge starting from one entry $E_i$ and ending at one exit $X_j$ is a \emph{lane}. We let $E_iX_j$ denote such a lane.
\end{definition}

\begin{definition}
For a given standard road intersection, a lane of the type $E_iX_i$, i.e., an edge starting from one entry $E_i$ and ending at exit $X_i$ is a \emph{U-turn}.
\end{definition}

\begin{definition}
A standard road intersection of size $n$ where U-turns are forbidden is a \emph{restricted standard road intersection}.
\end{definition}

\begin{definition}
For a given standard road intersection, a \emph{Maximal Set of Lanes}, abbreviated \emph{MSL}, is a set of noncrossing lanes (i.e., each pair of lanes have no common point) such that any additional lane would cross at least one of them (i.e., would have a common point with at least one of them).
\end{definition}

\begin{remark}
An MSL corresponds to a set of $n$ nonintersecting chords (or a noncrossing complete matching on $2n$ vertices); see Stanley \cite[entries 59 and 61, p.\ 28]{Stanley2015}. Three examples of MSL are given by Figures \ref{fig:cercle}, \ref{fig:cerclenonmax} and \ref{fig:cerclenonmaxmod}.
\end{remark}

\begin{definition}
For a given standard road intersection, an MSL is said to be \emph{absolute} when it does not contain two U-turns $E_iX_i$ and $E_jX_j$ (with $i\neq j$) that can be changed into two lanes $E_iX_j$ and $E_jX_i$ to give another MSL.
\label{def:abs}
\end{definition}

\begin{figure}
    \begin{minipage}[c]{.46\linewidth}
\centering
\begin{tikzpicture}[line cap=round,line join=round,&gt;=triangle 45,x=0.5cm,y=0.5cm]
\clip(-4,-4) rectangle (4,4);
\draw [line width=10pt] (0,0) circle (6cm);
\draw (-1,3)--(-1,-2.83);
\draw (1,-3)--(2.87,-1.13);
\draw (3,1)--(1.13,2.87);
\draw (-3,-1)--(-3,0.83);
\begin{scriptsize}
\fill [black] (-1,3) circle (2.5pt);
\draw[black] (-1,3.7) node {$E_1$};
\draw [black] (1,3) circle (2.5pt);
\draw[black] (1,3.7) node {$X_1$};
\fill [black] (3,1) circle (2.5pt);
\draw[black] (3.7,1) node {$E_2$};
\draw [black] (3,-1) circle (2.5pt);
\draw[black] (3.7,-1) node {$X_2$};
\fill [black] (1,-3) circle (2.5pt);
\draw[black] (1,-3.7) node {$E_3$};
\draw [black] (-1,-3) circle (2.5pt);
\draw[black] (-1,-3.7) node {$X_3$};
\fill [black] (-3,-1) circle (2.5pt);
\draw[black] (-3.7,-1) node {$E_4$};
\draw [black] (-3,1) circle (2.5pt);
\draw[black] (-3.7,1) node {$X_4$};
\end{scriptsize}
\end{tikzpicture}
\caption{A bipartite graph associated with the intersection represented in Figure \ref{fig:inter}, with an example of absolute MSL corresponding to the noncrossing partition $\{\,\{1,2,3\},\{4\}\,\}$.}
\label{fig:cercle}
    \end{minipage}\hfill
    \begin{minipage}[c]{.46\linewidth}
\centering
\begin{tikzpicture}[line cap=round,line join=round,&gt;=triangle 45,x=0.5cm,y=0.5cm]
\clip(-4,-4) rectangle (4,4);
\draw [line width=10pt] (0,0) circle (6cm);
\draw (-1,3)--(2.85,-0.85);
\draw (3,1)--(1.13,2.87);
\draw (-0.83,-3)--(1,-3);
\draw (-3,-1)--(-3,0.83);
\begin{scriptsize}
\fill [color=black] (-1,3) circle (2.5pt);
\draw[color=black] (-1,3.7) node {$E_1$};
\draw [color=black] (1,3) circle (2.5pt);
\draw[color=black] (1,3.7) node {$X_1$};
\fill [color=black] (3,1) circle (2.5pt);
\draw[color=black] (3.7,1) node {$E_2$};
\draw [color=black] (3,-1) circle (2.5pt);
\draw[color=black] (3.7,-1) node {$X_2$};
\fill [color=black] (1,-3) circle (2.5pt);
\draw[color=black] (1,-3.7) node {$E_3$};
\draw [color=black] (-1,-3) circle (2.5pt);
\draw[color=black] (-1,-3.7) node {$X_3$};
\fill [color=black] (-3,-1) circle (2.5pt);
\draw[color=black] (-3.7,-1) node {$E_4$};
\draw [color=black] (-3,1) circle (2.5pt);
\draw[color=black] (-3.7,1) node {$X_4$};
\end{scriptsize}
\end{tikzpicture}
\caption{A bipartite graph associated with the intersection represented in Figure \ref{fig:inter}, with an example of a nonabsolute MSL corresponding to the noncrossing partition $\{\,\{1,2\},\{3\},\{4\}\,\}$.}
\label{fig:cerclenonmax}
    \end{minipage}\hfill
\end{figure}

\begin{figure}
\begin{minipage}[c]{.46\linewidth}
\centering
\begin{tikzpicture}[line cap=round,line join=round,&gt;=triangle 45,x=0.5cm,y=0.5cm]
\clip(-4,-4) rectangle (4,4);
\draw [line width=10pt] (0,0) circle (6cm);
\draw (0,3)--(0,-3);
\draw (0,-3)--(3,0);
\draw (3,0)--(0,3);
\draw (-3,0)--(-3,0);
\begin{scriptsize}
\fill [color=black] (0,3) circle (2.5pt);
\draw[color=black] (0,3.7) node {$1$};
\fill [color=black] (3,0) circle (2.5pt);
\draw[color=black] (3.7,0) node {$2$};
\fill [color=black] (0,-3) circle (2.5pt);
\draw[color=black] (0,-3.7) node {$3$};
\fill [color=black] (-3,0) circle (2.5pt);
\draw[color=black] (-3.7,0) node {$4$};
\end{scriptsize}
\end{tikzpicture}
\caption{Simplified graph of Figure \ref{fig:cercle}, showing explicitly the noncrossing lonely singles partition $\{\,\{1,2,3\},\{4\}\,\}$.}
\label{fig:cerclesimp}
    \end{minipage}\hfill
    \begin{minipage}[c]{.46\linewidth}
\centering
\begin{tikzpicture}[line cap=round,line join=round,&gt;=triangle 45,x=0.5cm,y=0.5cm]
\clip(-4,-4) rectangle (4,4);
\draw [line width=10pt] (0,0) circle (6cm);
\draw (3,0)--(0,3);
\begin{scriptsize}
\fill [color=black] (0,3) circle (2.5pt);
\draw[color=black] (0,3.7) node {$1$};
\fill [color=black] (3,0) circle (2.5pt);
\draw[color=black] (3.7,0) node {$2$};
\fill [color=black] (0,-3) circle (2.5pt);
\draw[color=black] (0,-3.7) node {$3$};
\fill [color=black] (-3,0) circle (2.5pt);
\draw[color=black] (-3.7,0) node {$4$};
\end{scriptsize}
\end{tikzpicture}
\caption{Simplified graph of Figure \ref{fig:cerclenonmax}, showing explicitly the noncrossing marriageable singles partition $\{\,\{1,2\},\{3\},\{4\}\,\}$.}
\label{fig:cerclenonmaxsimp}
    \end{minipage}
\end{figure}

\begin{figure}
    \begin{minipage}[c]{.46\linewidth}
\centering
\begin{tikzpicture}[line cap=round,line join=round,&gt;=triangle 45,x=0.5cm,y=0.5cm]
\clip(-4,-4) rectangle (4,4);
\draw [line width=10pt] (0,0) circle (6cm);
\draw (-1,3)--(2.85,-0.85);
\draw (3,1)--(1.13,2.87);
\draw (-3,-1)--(-1.13,-2.87);
\draw (-2.87,0.83)--(1,-3);
\begin{scriptsize}
\fill [color=black] (-1,3) circle (2.5pt);
\draw[color=black] (-1,3.7) node {$E_1$};
\draw [color=black] (1,3) circle (2.5pt);
\draw[color=black] (1,3.7) node {$X_1$};
\fill [color=black] (3,1) circle (2.5pt);
\draw[color=black] (3.7,1) node {$E_2$};
\draw [color=black] (3,-1) circle (2.5pt);
\draw[color=black] (3.7,-1) node {$X_2$};
\fill [color=black] (1,-3) circle (2.5pt);
\draw[color=black] (1,-3.7) node {$E_3$};
\draw [color=black] (-1,-3) circle (2.5pt);
\draw[color=black] (-1,-3.7) node {$X_3$};
\fill [color=black] (-3,-1) circle (2.5pt);
\draw[color=black] (-3.7,-1) node {$E_4$};
\draw [color=black] (-3,1) circle (2.5pt);
\draw[color=black] (-3.7,1) node {$X_4$};
\end{scriptsize}
\end{tikzpicture}
\caption{Modification of Figure \ref{fig:cerclenonmax} to obtain an absolute MSL corresponding to the noncrossing partition $\{\,\{1,2\},\{3,4\}\,\}$.}
\label{fig:cerclenonmaxmod}
    \end{minipage}\hfill
    \begin{minipage}[c]{.46\linewidth}
\centering
\begin{tikzpicture}[line cap=round,line join=round,&gt;=triangle 45,x=0.5cm,y=0.5cm]
\clip(-4,-4) rectangle (4,4);
\draw [line width=10pt] (0,0) circle (6cm);
\draw (3,0)--(0,3);
\draw (-3,0)--(0,-3);
\begin{scriptsize}
\fill [color=black] (0,3) circle (2.5pt);
\draw[color=black] (0,3.7) node {$1$};
\fill [color=black] (3,0) circle (2.5pt);
\draw[color=black] (3.7,0) node {$2$};
\fill [color=black] (0,-3) circle (2.5pt);
\draw[color=black] (0,-3.7) node {$3$};
\fill [color=black] (-3,0) circle (2.5pt);
\draw[color=black] (-3.7,0) node {$4$};
\end{scriptsize}
\end{tikzpicture}
\caption{Simplified graph of Figure \ref{fig:cerclenonmaxmod}, showing explicitly the noncrossing lonely singles partition $\{\,\{1,2\},\{3,4\}\,\}$.}
\label{fig:cerclenonmaxmodsimp}
    \end{minipage}
\end{figure}

\begin{lemma}\label{lem:catalan}
For a given standard road intersection of size $n$, the set of MSL is in one-to-one correspondence with the set of noncrossing partitions of $[n]$. The number of MSL of a standard road intersection of size $n$ is equal to the Catalan number $C_n$.
\end{lemma}

\begin{proof}
As a MSL can be seen as a set of $n$ nonintersecting chords joining $2n$ points, this result is very well known. See Stanley \cite[entry~59, p.\ 28]{Stanley2015}.
\end{proof}

The following three corollaries are just reinterpretations of the lonely singles and marriageable singles definitions in the language of road intersections.

\begin{corollary}
The number of nonabsolute MSL of a standard road intersection of size~$n$ is $M_n$.
\end{corollary}

\begin{corollary}
The number of absolute MSL of a standard road intersection of size~$n$ is $L_n$.
\end{corollary}

\begin{corollary}
The number of MSL for a restricted standard road intersection of size~$n$ is $L_n$.
\end{corollary}

\section{Properties}

\begin{proposition}
Both sequences $(L_n)_{n\geq 0}$ and $(M_n)_{n\geq 0}$ are increasing: $L_n&lt;L_{n+1}$ for all $n\geq 2$ and $M_n&lt;M_{n+1}$ for all $n\geq 3$.
\label{prop:increasing}
\end{proposition}

\begin{proof}
We build a simple injective map $f_n$ from the set $\mathrm{LS}_n$ of the lonely singles partitions of $[n]$ to the set $\mathrm{LS}_{n+1}$ of the lonely singles partitions of $[n+1]$ by merging the singleton $\{n+1\}$ to the unique element $A_1$ of a partition $\pi$ that contains the number $1$ (one could equally prefer to use the number $n$ instead of the number 1: the idea is to attach the number $n+1$ to one of its two direct neighbours 1 or $n$):
\begin{align*}
\mathrm{LS}_n &amp; \to \mathrm{LS}_{n+1}\\
f_n\colon \pi=\{\,A_1,\dots,A_k\,\} &amp; \mapsto \{\,A_1\cup\{n+1\},\dots,A_k\,\},
\end{align*}
where $1\in A_1$ and $A_1\cup\dots\cup A_k=[n]$ and $A_i\cap A_j=\emptyset$ for all $i\neq j$. For example,
\begin{align*}
f_3\left(\{\,\{1,2\},\{3\}\,\}\right) &amp;= \{\,\{1,2,4\},\{3\}\,\},\\
f_4\left(\{\,\{1\},\{2,4\},\{3\}\,\}\right)&amp;= \{\,\{1,5\},\{2,4\},\{3\}\,\}.\\
\end{align*}
The map $f_n$ is clearly injective and every lonely singles partition $\pi$ gives a lonely singles partition $f_n(\pi)$. As $L_n$ is the cardinality of $\mathrm{LS}_n$ and $L_{n+1}$ is the cardinality of $\mathrm{LS}_{n+1}$, we obtain $L_n\leq L_{n+1}$. 

In a similar way, we build a simple injective map $g_n$ from the set $\mathrm{MS}_n$ of the marriageable singles partitions of $[n]$ to the set $\mathrm{MS}_{n+1}$ of the marriageable singles partitions of $[n+1]$ by adding the singleton block $\{n+1\}$ to any partition $\pi$:
\begin{align*}
\mathrm{MS}_n &amp; \to \mathrm{MS}_{n+1}\\
g_n \colon \pi &amp; \mapsto \pi\cup \{\,\{n+1\}\,\}.
\end{align*}
For example,
\begin{align*}
%g_3\left(\{\,\{1\},\{2\},\{3\}\,\}\right)&amp;= \{\,\{1\},\{2\},\{3\},\{4\}\,\}\\
g_4\left(\{\,\{1\},\{2,3\},\{4\}\,\}\right)&amp;= \{\,\{1\},\{2,3\},\{4\},\{5\}\,\}.
\end{align*}
The map $g_n$ is clearly injective, and a pair of marriageable singletons $\{i\}$ and $\{j\}$ of $\pi\in \mathrm{MS}_n$ remains marriageable singletons as elements of $g_n(\pi)\in \mathrm{MS}_{n+1}$. As $M_n$ is the cardinality of $\mathrm{MS}_n$ and $M_{n+1}$ is the cardinality of $\mathrm{MS}_{n+1}$, we obtain $M_n\leq M_{n+1}$.

More precisely, we have $L_n&lt;L_{n+1}$ for all $n\geq 2$ and $M_n&lt;M_{n+1}$ for all $n\geq 3$: it is easy to build a lonely singles and a marriageable singles partitions of $[n+1]$ that are not in the images of the maps $f_n$ and $g_n$, e.g., respectively $\{\,[n],\{n+1\}\,\}$ and $\{\,\{1\},\dots,\{n-1\},\{n,n+1\}\,\}$.
\end{proof}

\begin{corollary}
We have
$$\lim_{n\to+\infty}M_n=\lim_{n\to+\infty}L_n=+\infty.$$
\end{corollary}
\begin{proof}
This is an immediate consequence of Proposition \ref{prop:increasing}.
\end{proof}

\begin{proposition}
For all $n\geq 0$, we have $C_n+3M_n\leq M_{n+2}$.
\end{proposition}

\begin{proof}
We build four simple injective maps $h_n, i_n, j_n$ and $k_n$ with disjoint images included in the set $\mathrm{MS}_{n+2}$ of the marriageable singles partitions of $[n+2]$.

\begin{itemize}
\item The map $h_n$ is defined on the set $\mathrm{NC}_n$ of all noncrossing partitions of $[n]$ by adding both the singleton blocks $\{n+1\}$ and $\{n+2\}$ to a noncrossing partition $\pi$:
\begin{align*}
\mathrm{NC}_n&amp;\to \mathrm{MS}_{n+2}\\
h_n\colon \pi&amp;\mapsto \pi\cup \{\,\{n+1\}, \{n+2\}\,\}.
\end{align*}
The maps $i_n, j_n$ and $k_n$ are defined on the set $\mathrm{MS}_n$ of the marriageable singles partitions of $[n]$.

\item The map $i_n$ adds the pair $\{n+1, n+2\}$ to a marriageable singles partition $\pi$:
\begin{align*}
\mathrm{MS}_n &amp;\to \mathrm{MS}_{n+2}\\
i_n\colon \pi &amp;\mapsto \pi\cup \{\,\{n+1,n+2\}\,\}.
\end{align*}

\item The map $j_n$ merges the singleton block $\{n+2\}$ with the unique element $A_1$ of a marriageable singles partition $\pi$ that contains the number $1$ and adds the singleton block $\{n+1\}$ to $\pi$:
\begin{align*}
\mathrm{MS}_n&amp;\to \mathrm{MS}_{n+2}\\
j_n\colon \pi=\{\,A_1,\dots,A_k\,\}&amp;\mapsto \{\,A_1\cup\{n+2\},A_2,\dots,A_k, \{n+1\}\,\},
\end{align*}

where $1\in A_1$, $A_1\cup\dots\cup A_k=[n]$ and $A_i\cap A_j=\emptyset$ for all $i\neq j$.

\item The map $k_n$ merges the singleton block $\{n+1\}$ with the unique element $A_1$ of a marriageable singles partition $\pi$ that contains the number $n$ and adds the singleton block $\{n+2\}$ to $\pi$:
\begin{align*}
\mathrm{MS}_n &amp;\to \mathrm{MS}_{n+2}\\
k_n : \pi=\{\,A_1,\dots,A_k\,\} &amp;\mapsto \{\,A_1\cup\{n+1\},A_2,\dots,A_k, \{n+2\}\,\},
\end{align*}

where $n\in A_1$, $A_1\cup\dots\cup A_k=[n]$ and $A_i\cap A_j=\emptyset$ for all $i\neq j$.
\end{itemize}
For example, 
\begin{align*}
h_4\left(\{\,\{1,2,3\},\{4\}\,\}\right) &amp;= \{\,\{1,2,3\},\{4\},\{5\},\{6\}\,\},\\
%h_4\left(\{\,\{1,2\},\{3\},\{4\}\,\}\right) &amp;= \{\,\{1,2\},\{3\},\{4\},\{5\},\{6\}\,\},\\
i_4\left(\{\,\{1,2\},\{3\},\{4\}\,\}\right) &amp;= \{\,\{1,2\},\{3\},\{4\},\{5,6\}\,\},\\
j_4\left(\{\,\{1,2\},\{3\},\{4\}\,\}\right) &amp;= \{\,\{1,2,6\},\{3\},\{4\},\{5\}\,\},\\
k_4\left(\{\,\{1,2\},\{3\},\{4\}\,\}\right) &amp;= \{\,\{1,2\},\{3\},\{4,5\},\{6\}\,\}.
\end{align*}

We have the immediate following properties:
\begin{itemize}
\item $h_n(\pi)$ is a marriageable singles partition of $[n+2]$ for all noncrossing partition $\pi$ of $[n]$,
\item $i_n(\pi), j_n(\pi)$ and $k_n(\pi)$ are marriageable singles partitions of $[n+2]$ for all marriageable singles partition $\pi$ of $[n]$ (the marriageable pairs can change depending on the map selected),
\item $h_n, i_n, j_n$ and $k_n$ are injective maps; thus,
\begin{itemize}
\item $\mathrm{NC}_n$ and $h_n(\mathrm{NC}_n)$ have the same cardinality $C_n$,
\item $\mathrm{MS}_n$ and $i_n(\mathrm{MS}_n)$ and $j_n(\mathrm{MS}_n)$ and $k_n(\mathrm{MS}_n)$ have the same cardinality $M_n$,
\end{itemize}
\item the sets $h_n(\mathrm{NC}_n)$, $i_n(\mathrm{MS}_n)$, $j_n(\mathrm{MS}_n)$ and $k_n(\mathrm{MS}_n)$ are disjoint; thus,
$$ h_n(\mathrm{NC}_n)\sqcup i_n(\mathrm{MS}_n)\sqcup j_n(\mathrm{MS}_n)\sqcup k_n(\mathrm{MS}_n)\subset \mathrm{MS}_{n+2}, $$
\item as $M_{n+2}$ is the cardinality of $\mathrm{MS}_{n+2}$, we obtain $C_n+3M_n\leq M_{n+2}$.
\end{itemize}
\end{proof}


\begin{definition}
For all nonnegative integers $n$, $m$ and $k$, let $\mathrm{NC}_{n,m,k}$ be the number of noncrossing partitions of $[n]$ in $m$ classes with $k$ singleton blocks.
\end{definition}

\begin{proposition}
For all non-negative integers $n$ and $m$ with $(n,m)\neq(0,0)$, the number of noncrossing partitions of $[n]$ in $m$ classes with no singleton block is 
$$\mathrm{NC}_{n,m,0}=\frac{1}{n-m+1}\binom{n}{m}\binom{n-m-1}{m-1}.$$
When $(n,m)\neq(1,1)$, the number of noncrossing partitions of $[n]$ in $m$ classes with exactly one singleton block is
$$\mathrm{NC}_{n,m,1}=\binom{n}{m-1}\binom{n-m-1}{m-2}.$$
\label{prop:atmost1}
\end{proposition}

\begin{proof}
Poupard \cite{Poupard1972} proved that, when $n\geq 1$ and $m\geq 1$, the number of noncrossing partitions of $[n]$ in $m$ classes with no singleton block is $\mathrm{NC}_{n,m,0}=\frac{1}{n-m+1}\binom{n}{m}\binom{n-m-1}{m-1}$, and $n\geq 2m$. When $n=0$ and $m\geq 1$ or $n\geq 1$ and $m=0$ or $m\geq \lfloor \frac{n}{2}\rfloor+1$, this equality holds and gives a number of such partitions equal to $0$.

When $n\geq 1$ and $m\geq 1$, the set of noncrossing partitions of $[n]$ in $m$ classes with exactly one singleton block is clearly in one-to-one correspondence with the set of couples $(\pi,i)$, where $\pi$ is a noncrossing partition of $[n-1]$ in $m-1$ classes with no singleton block and $1\leq i\leq n$.
Then, when $(n,m)\neq (1,1)$, we obtain that the number of noncrossing partitions of $[n]$ in $m$ classes with exactly one singleton block is $\mathrm{NC}_{n,m,1}=n\times \mathrm{NC}_{n-1,m-1,0}=\frac{n}{n-m+1}\binom{n-1}{m-1}\binom{n-m-1}{m-2}=\binom{n}{m-1}\binom{n-m-1}{m-2}$.
\end{proof}

\begin{remark}
Here are a few details on specific cases:
\begin{itemize}
\item the empty partition is the unique noncrossing partition of the empty set $[0]$ in $0$ class with no singleton block. Thus, $\mathrm{NC}_{0,0,0}=1$,
\item the set $[1]$ has a unique noncrossing partition. This partition has $m=1$ class and it is a singleton block. Thus, $\mathrm{NC}_{1,1,1}=1$ and $\mathrm{NC}_{1,m,k}=0$ when $(m,k)\neq(1,1)$ and, in particular, $\mathrm{NC}_{1,1,0}=0$,
\item for all positive integer $n$, $[n]$ has no noncrossing partition in $m=0$ class. Thus, for all non-negative integer $k$, $\mathrm{NC}_{n,0,k}=0$ and in particular $\mathrm{NC}_{n,0,0}=0$.
\end{itemize}
\end{remark}

\begin{proposition}
For all $n\geq 2$, 
$$L_n\geq \sum_{m=1}^{\lfloor\frac{n}{2}\rfloor}\frac{1}{n-m+1}\binom{n}{m}\binom{n-m-1}{m-1}
+ \sum_{m=2}^{\lfloor\frac{n+1}{2}\rfloor}\binom{n}{m-1}\binom{n-m-1}{m-2}.$$
\end{proposition}
\begin{proof}
As every noncrossing partition with at most one singleton block is a lonely singles partition, we have $L_n\geq \sum_{m=1}^{\lfloor \frac{n}{2}\rfloor} \mathrm{NC}_{n,m,0} + \sum_{m=1}^{\lfloor \frac{n+1}{2}\rfloor} \mathrm{NC}_{n,m,1}$ and the result follows, using Proposition \ref{prop:atmost1}.
\end{proof}

\begin{proposition}
For all $n\geq 3$,
\begin{align*}
M_n\geq \sum_{i=1}^{n-1}\sum_{j=i+1}^{n} &amp;\left(\sum_{m=0}^{\lfloor \frac{n+i-j-1}{2}\rfloor} \frac{1}{n+i-j-m}\binom{n+i-j-1}{m}\binom{n+i-j-m-2}{m-1}\right.\\
&amp;\times \left.\sum_{m=0}^{\lfloor \frac{j-i-1}{2}\rfloor}\frac{1}{j-i-m}\binom{j-i-1}{m}\binom{j-i-m-2}{m-1}\right).%\\
\end{align*}
\end{proposition}

\begin{proof}
Let $\pi$ be a marriageable singles partition of $[n]$ with exactly two singleton blocks $\{i\}$ and $\{j\}$ (with $i&lt;j$). The set of such partitions $\pi$ is clearly in one-to-one correspondence with the set of triples $(\{i,j\},\pi_1,\pi_2)$ where $1\leq i&lt;j\leq n$ and $\pi_1$ and $\pi_2$ are noncrossing partitions of the sets $[n+i-j-1]$ and $[j-i-1]$ respectively, with no singleton blocks. Thus,

%Considering separately the special case where $\{i\}$ and $\{j\}$ are neighbours (i.e.\ $1\leq i\leq n-1$ and $j=i+1$ or $i=1$ and $j=n$), we have
$$M_n\geq \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\left(\sum_{m=0}^{\lfloor \frac{n+i-j-1}{2} \rfloor}\mathrm{NC}_{n+i-j-1,m,0}\sum_{m=0}^{\lfloor \frac{j-i-1}{2} \rfloor}\mathrm{NC}_{j-i-1,m,0}\right).$$
\end{proof}

\begin{remark}
The previous inequality can be improved, considering three or more singleton blocks that can all be joined.
\end{remark}
\section{Known values and conjectures}

Very few values of the sequences $L_n$ and $M_n$ are known at the moment. They are given in Table \ref{table}. $L_n$ and $M_n$ are, respectively, sequences \seqnum{A363448} and \seqnum{A363449} in the {\it On-Line Encyclopedia of Integer Sequences} (OEIS) \cite{oeis}.

The values of $M_n$ were obtained with the algorithms available in the accompanying files, provided in pdf and ipynb formats. The complexity of these algorithms is exponential: they need to be improved and to be run with a more powerful computer to obtain values of $L_n$ and $M_n$ for $n\geq 15$. Calculations were performed under Python 3.7.3 using Jupyter Notebook 5.7.6 with a 3.19 GHz i7-8700 processor and 32 GB RAM. 

\begin{table}[H]
\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
$n$ &amp; $L_n$ &amp; $L_n/L_{n-1}$ &amp; $M_n$ &amp; $M_n/M_{n-1}$ &amp; $C_n$ &amp; $M_n/L_n$ &amp; $M_n/C_n$ &amp; Computing \\
&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp; time for $M_n$\\
\hline
0&amp;1&amp;  &amp;0&amp;  &amp;1&amp;0&amp; 0 &amp;0s\\
\hline
1&amp;1&amp; 1 &amp;0&amp;  &amp;1&amp;0&amp; 0 &amp;0s\\
\hline
2&amp;1&amp; 1 &amp;1&amp;  &amp;2&amp;1&amp; 0.5 &amp;0s\\
\hline
3&amp;4&amp; 4 &amp;1&amp; 1 &amp;5&amp;0.25&amp; 0.2 &amp;0s\\
\hline
4&amp;9&amp; 2.25 &amp;5&amp; 5 &amp;14&amp;0.56&amp; 0.36 &amp;263$\mu$s\\
\hline
5&amp;26&amp; 2.89 &amp;16&amp; 3.2 &amp;42&amp;0.62&amp; 0.38 &amp;657$\mu$s\\
\hline
6&amp;77&amp; 2.96 &amp;55&amp; 3.44 &amp;132&amp;0.71&amp; 0.42 &amp;1.8ms\\
\hline
7&amp;232&amp; 3.01 &amp;197&amp; 3.58 &amp;429&amp;0.85&amp; 0.46 &amp;7.5ms\\
\hline
8&amp;725&amp; 3.13 &amp;705&amp; 3.58 &amp;1430&amp;0.97&amp; 0.49 &amp;24ms\\
\hline
9&amp;2299&amp; 3.17 &amp;2563&amp; 3.64 &amp;4862&amp;1.11&amp; 0.53 &amp;90ms\\
\hline
10&amp;7415&amp; 3.22 &amp;9381&amp; 3.67 &amp;16796&amp;1.27&amp; 0.56 &amp;507ms\\
\hline
11&amp;24223&amp; 2.99 &amp;34563&amp; 3.90 &amp;58786&amp;1.66&amp; 0.62 &amp;3.7s\\
\hline
12&amp;79983&amp; 3.29 &amp;128029&amp; 3.69 &amp;208012&amp;1.86&amp; 0.65 &amp;39.4s\\
\hline
13&amp; 266553&amp; 3.23 &amp;476347&amp; 3.75 &amp;742900&amp;2.16&amp; 0.68 &amp;15m, 36s\\
\hline
14&amp; 895333&amp; 3.25 &amp;1779107&amp; 3.76 &amp;2674440&amp;2.50&amp; 0.71 &amp;6h, 2m, 40s\\
\hline
15&amp; 3028093 &amp; 3.31 &amp; 6666752 &amp; 3.75 &amp; 9694845 &amp; 2.83 &amp; 0.74 &amp; 6days, 7h, 13m \\
\hline
\end{tabular}
\caption{Values of $L_n$, $M_n$, $C_n$, $L_n/L_{n-1}$, $M_n/M_{n-1}$, $M_n/L_n$ and $M_n/C_n$ (given with 2 digits), with computing time of $M_n$, for all $n\leq 15$.}
\label{table}
\end{table}


\begin{conjecture}
We conjecture the five following propositions:
\begin{align}
&amp;\text{for all } n\in\mathbb{N}, n\geq 9 \Rightarrow M_n &gt; L_n,\label{conj1}\\
&amp;\lim_{n\to+\infty}\frac{M_n}{L_n}=+\infty,\label{conj2}\\
&amp;\lim_{n\to+\infty}\frac{M_n}{C_n}=1,\label{conj3}\\
&amp;\lim_{n\to+\infty}\frac{L_n}{C_n}=0,\label{conj4}\\
&amp;\lim_{n\to+\infty}\frac{M_{n+1}}{M_n}=\lim_{n\to+\infty}\frac{L_{n+1}}{L_n}=4.\label{conj5}
\end{align}
\end{conjecture}

\begin{remark}
Obviously, conjecture (\ref{conj2}) implies conjecture (\ref{conj1}).
Table \ref{table} shows that $\frac{M_n}{L_n}$ grows slowly and conjecture \ref{conj2} may stand. More clearly, Table \ref{table} shows that $\frac{M_n}{C_n}$ seems to grow quite quickly and lets think that conjecture \ref{conj3} stands. As $C_n=M_n+L_n$, conjectures (\ref{conj2}), (\ref{conj3}) and (\ref{conj4}) are clearly equivalent. It is well known and easy to prove that $\lim_{n\to+\infty}\frac{C_{n+1}}{C_n}=~4$. Table \ref{table} shows that the similar limits given in conjecture (\ref{conj5}) look very realistic as well.
\end{remark}

\section{Acknowledgements}
We would like to thank Fr\'ed\'eric Blanchard and Rupert Wei Tze Yu for their constant help. Our deepest gratitude goes to the anonymous referee who gave us directions to improve this paper. 

\begin{thebibliography}{99}
  
 \bibitem{Rouyer2022} J.\ Rouyer, A.\ Ninet, H.\ Fouchal and A.\ Keziou, A road intersection control in urban intelligent transportation systems, in {\it ICC 2022: Proc.\ IEEE International Conference on Communications}, Seoul, South Korea, May 2022, pp. 3562--3567.

 \bibitem{Stanley2015} S.\ Stanley, {\it Catalan Numbers}, Cambridge University Press, 2015.

 \bibitem{Bai2021} S.\ Bai and X.\ Bai, A general framework for intersection traffic control with backpressure routing, {\it IEEE Access} {\bf 9} (2021), 102125--102136.

 \bibitem{Roman2015} S.\ Roman, {\it An Introduction to Catalan Numbers}, Birkhauser, 2015.

\bibitem{Kreweras1972} G.\ Kreweras, Sur les partitions non crois\'ees d'un cycle, {\it Discrete Math.} {\bf 1} (1972), 333--350.

\bibitem{Poupard1972} Y.\ Poupard, \'Etude et d\'enombrement parall\`eles des partitions non-crois\'ees d'un cycle et des d\'ecoupages d'un polygone convexe, {\it Discrete Math.} {\bf 2} (1972), 279--288.

\bibitem{Becker1952} H.\ W.\ Becker, Planar rhyme schemes, {\it Bull.\ Amer.\ Math.\ Soc.} {\bf 58} (1952), 39.

\bibitem{Simion2000} R.\ Simion, Noncrossing partitions, {\it Discrete Math.} {\bf 217} (2000), 367--409.

\bibitem{Mccammond2006} J.\ McCammond, Noncrossing partitions in surprising locations, 2006. Available at \url{https://arxiv.org/abs/math/0601687}.

\bibitem{Callan2008} D.\ Callan, Sets, lists and noncrossing partitions, {\it J. Integer Sequences} {\bf 11} (2008), 
\href{https://cs.uwaterloo.ca/journals/JIS/VOL11/Callan/callan412.html}{Article 08.1.3}.

\bibitem{Kim2011} J.\ S.\ Kim, New interpretations for noncrossing partitions of classical types, {\it J.\ Combin.\ Theory Ser.\ A} {\bf 118} (2011), 1168--1189.

\bibitem{oeis}  N.\ J.\ A.\ Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2024. Available at \url{https://oeis.org}.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2020 {\it Mathematics Subject Classification}: Primary 05A18. %; Secondary.

\noindent \emph{Keywords:} noncrossing partition.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000108},
\seqnum{A363448}, and
\seqnum{A363449}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received November 11 2023;
revised versions received  November 12 2023; November 13 2023; 
February 12 2024; October 1 2024.
Published in {\it Journal of Integer Sequences}, January 3 2025.

\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>