\documentclass[12pt,titlepage]{article}

\usepackage{amsmath}
\usepackage{mathrsfs}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{mathtools}
\usepackage{graphicx}
\usepackage{color}
\usepackage{ucs}
\usepackage[utf8x]{inputenc}
\usepackage{xparse}
\usepackage{hyperref}

%----Macros----------
%
% Unresolved issues:
%
%  \righttoleftarrow
%  \lefttorightarrow
%
%  \color{} with HTML colorspec
%  \bgcolor
%  \array with options (without options, it's equivalent to the matrix environment)

% Of the standard HTML named colors, white, black, red, green, blue and yellow
% are predefined in the color package. Here are the rest.
\definecolor{aqua}{rgb}{0, 1.0, 1.0}
\definecolor{fuschia}{rgb}{1.0, 0, 1.0}
\definecolor{gray}{rgb}{0.502, 0.502, 0.502}
\definecolor{lime}{rgb}{0, 1.0, 0}
\definecolor{maroon}{rgb}{0.502, 0, 0}
\definecolor{navy}{rgb}{0, 0, 0.502}
\definecolor{olive}{rgb}{0.502, 0.502, 0}
\definecolor{purple}{rgb}{0.502, 0, 0.502}
\definecolor{silver}{rgb}{0.753, 0.753, 0.753}
\definecolor{teal}{rgb}{0, 0.502, 0.502}

% Because of conflicts, \space and \mathop are converted to
% \itexspace and \operatorname during preprocessing.

% itex: \space{ht}{dp}{wd}
%
% Height and baseline depth measurements are in units of tenths of an ex while
% the width is measured in tenths of an em.
\makeatletter
\newdimen\itex@wd%
\newdimen\itex@dp%
\newdimen\itex@thd%
\def\itexspace#1#2#3{\itex@wd=#3em%
\itex@wd=0.1\itex@wd%
\itex@dp=#2ex%
\itex@dp=0.1\itex@dp%
\itex@thd=#1ex%
\itex@thd=0.1\itex@thd%
\advance\itex@thd\the\itex@dp%
\makebox[\the\itex@wd]{\rule[-\the\itex@dp]{0cm}{\the\itex@thd}}}
\makeatother

% \tensor and \multiscript
\makeatletter
\newif\if@sup
\newtoks\@sups
\def\append@sup#1{\edef\act{\noexpand\@sups={\the\@sups #1}}\act}%
\def\reset@sup{\@supfalse\@sups={}}%
\def\mk@scripts#1#2{\if #2/ \if@sup ^{\the\@sups}\fi \else%
  \ifx #1_ \if@sup ^{\the\@sups}\reset@sup \fi {}_{#2}%
  \else \append@sup#2 \@suptrue \fi%
  \expandafter\mk@scripts\fi}
\def\tensor#1#2{\reset@sup#1\mk@scripts#2_/}
\def\multiscripts#1#2#3{\reset@sup{}\mk@scripts#1_/#2%
  \reset@sup\mk@scripts#3_/}
\makeatother

% \slash
\makeatletter
\newbox\slashbox \setbox\slashbox=\hbox{$/$}
\def\itex@pslash#1{\setbox\@tempboxa=\hbox{$#1$}
  \@tempdima=0.5\wd\slashbox \advance\@tempdima 0.5\wd\@tempboxa
  \copy\slashbox \kern-\@tempdima \box\@tempboxa}
\def\slash{\protect\itex@pslash}
\makeatother

% math-mode versions of \rlap, etc
% from Alexander Perlis, "A complement to \smash, \llap, and lap"
%   http://math.arizona.edu/~aprl/publications/mathclap/
\def\clap#1{\hbox to 0pt{\hss#1\hss}}
\def\mathllap{\mathpalette\mathllapinternal}
\def\mathrlap{\mathpalette\mathrlapinternal}
\def\mathclap{\mathpalette\mathclapinternal}
\def\mathllapinternal#1#2{\llap{$\mathsurround=0pt#1{#2}$}}
\def\mathrlapinternal#1#2{\rlap{$\mathsurround=0pt#1{#2}$}}
\def\mathclapinternal#1#2{\clap{$\mathsurround=0pt#1{#2}$}}

% Renames \sqrt as \oldsqrt and redefine root to result in \sqrt[#1]{#2}
\let\oldroot\root
\def\root#1#2{\oldroot #1 \of{#2}}
\renewcommand{\sqrt}[2][]{\oldroot #1 \of{#2}}

% Manually declare the txfonts symbolsC font
\DeclareSymbolFont{symbolsC}{U}{txsyc}{m}{n}
\SetSymbolFont{symbolsC}{bold}{U}{txsyc}{bx}{n}
\DeclareFontSubstitution{U}{txsyc}{m}{n}

% Manually declare the stmaryrd font
\DeclareSymbolFont{stmry}{U}{stmry}{m}{n}
\SetSymbolFont{stmry}{bold}{U}{stmry}{b}{n}

% Manually declare the MnSymbolE font
\DeclareFontFamily{OMX}{MnSymbolE}{}
\DeclareSymbolFont{mnomx}{OMX}{MnSymbolE}{m}{n}
\SetSymbolFont{mnomx}{bold}{OMX}{MnSymbolE}{b}{n}
\DeclareFontShape{OMX}{MnSymbolE}{m}{n}{
    <-6>  MnSymbolE5
   <6-7>  MnSymbolE6
   <7-8>  MnSymbolE7
   <8-9>  MnSymbolE8
   <9-10> MnSymbolE9
  <10-12> MnSymbolE10
  <12->   MnSymbolE12}{}

% Declare specific arrows from txfonts without loading the full package
\makeatletter
\def\re@DeclareMathSymbol#1#2#3#4{%
    \let#1=\undefined
    \DeclareMathSymbol{#1}{#2}{#3}{#4}}
\re@DeclareMathSymbol{\neArrow}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\neArr}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\seArrow}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\seArr}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\nwArrow}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\nwArr}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\swArrow}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\swArr}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\nequiv}{\mathrel}{symbolsC}{46}
\re@DeclareMathSymbol{\Perp}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\Vbar}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\sslash}{\mathrel}{stmry}{12}
\re@DeclareMathSymbol{\bigsqcap}{\mathop}{stmry}{"64}
\re@DeclareMathSymbol{\biginterleave}{\mathop}{stmry}{"6}
\re@DeclareMathSymbol{\invamp}{\mathrel}{symbolsC}{77}
\re@DeclareMathSymbol{\parr}{\mathrel}{symbolsC}{77}
\makeatother

% \llangle, \rrangle, \lmoustache and \rmoustache from MnSymbolE
\makeatletter
\def\Decl@Mn@Delim#1#2#3#4{%
  \if\relax\noexpand#1%
    \let#1\undefined
  \fi
  \DeclareMathDelimiter{#1}{#2}{#3}{#4}{#3}{#4}}
\def\Decl@Mn@Open#1#2#3{\Decl@Mn@Delim{#1}{\mathopen}{#2}{#3}}
\def\Decl@Mn@Close#1#2#3{\Decl@Mn@Delim{#1}{\mathclose}{#2}{#3}}
\Decl@Mn@Open{\llangle}{mnomx}{'164}
\Decl@Mn@Close{\rrangle}{mnomx}{'171}
\Decl@Mn@Open{\lmoustache}{mnomx}{'245}
\Decl@Mn@Close{\rmoustache}{mnomx}{'244}
\makeatother

% Widecheck
\makeatletter
\DeclareRobustCommand\widecheck[1]{{\mathpalette\@widecheck{#1}}}
\def\@widecheck#1#2{%
    \setbox\z@\hbox{\m@th$#1#2$}%
    \setbox\tw@\hbox{\m@th$#1%
       \widehat{%
          \vrule\@width\z@\@height\ht\z@
          \vrule\@height\z@\@width\wd\z@}$}%
    \dp\tw@-\ht\z@
    \@tempdima\ht\z@ \advance\@tempdima2\ht\tw@ \divide\@tempdima\thr@@
    \setbox\tw@\hbox{%
       \raise\@tempdima\hbox{\scalebox{1}[-1]{\lower\@tempdima\box
\tw@}}}%
    {\ooalign{\box\tw@ \cr \box\z@}}}
\makeatother

% \mathraisebox{voffset}[height][depth]{something}
\makeatletter
\NewDocumentCommand\mathraisebox{moom}{%
\IfNoValueTF{#2}{\def\@temp##1##2{\raisebox{#1}{$\m@th##1##2$}}}{%
\IfNoValueTF{#3}{\def\@temp##1##2{\raisebox{#1}[#2]{$\m@th##1##2$}}%
}{\def\@temp##1##2{\raisebox{#1}[#2][#3]{$\m@th##1##2$}}}}%
\mathpalette\@temp{#4}}
\makeatletter

% udots (taken from yhmath)
\makeatletter
\def\udots{\mathinner{\mkern2mu\raise\p@\hbox{.}
\mkern2mu\raise4\p@\hbox{.}\mkern1mu
\raise7\p@\vbox{\kern7\p@\hbox{.}}\mkern1mu}}
\makeatother

%% Fix array
\newcommand{\itexarray}[1]{\begin{matrix}#1\end{matrix}}
%% \itexnum is a noop
\newcommand{\itexnum}[1]{#1}

%% Renaming existing commands
\newcommand{\underoverset}[3]{\underset{#1}{\overset{#2}{#3}}}
\newcommand{\widevec}{\overrightarrow}
\newcommand{\darr}{\downarrow}
\newcommand{\nearr}{\nearrow}
\newcommand{\nwarr}{\nwarrow}
\newcommand{\searr}{\searrow}
\newcommand{\swarr}{\swarrow}
\newcommand{\curvearrowbotright}{\curvearrowright}
\newcommand{\uparr}{\uparrow}
\newcommand{\downuparrow}{\updownarrow}
\newcommand{\duparr}{\updownarrow}
\newcommand{\updarr}{\updownarrow}
\newcommand{\gt}{>}
\newcommand{\lt}{<}
\newcommand{\map}{\mapsto}
\newcommand{\embedsin}{\hookrightarrow}
\newcommand{\Alpha}{A}
\newcommand{\Beta}{B}
\newcommand{\Zeta}{Z}
\newcommand{\Eta}{H}
\newcommand{\Iota}{I}
\newcommand{\Kappa}{K}
\newcommand{\Mu}{M}
\newcommand{\Nu}{N}
\newcommand{\Rho}{P}
\newcommand{\Tau}{T}
\newcommand{\Upsi}{\Upsilon}
\newcommand{\omicron}{o}
\newcommand{\lang}{\langle}
\newcommand{\rang}{\rangle}
\newcommand{\Union}{\bigcup}
\newcommand{\Intersection}{\bigcap}
\newcommand{\Oplus}{\bigoplus}
\newcommand{\Otimes}{\bigotimes}
\newcommand{\Wedge}{\bigwedge}
\newcommand{\Vee}{\bigvee}
\newcommand{\coproduct}{\coprod}
\newcommand{\product}{\prod}
\newcommand{\closure}{\overline}
\newcommand{\integral}{\int}
\newcommand{\doubleintegral}{\iint}
\newcommand{\tripleintegral}{\iiint}
\newcommand{\quadrupleintegral}{\iiiint}
\newcommand{\conint}{\oint}
\newcommand{\contourintegral}{\oint}
\newcommand{\infinity}{\infty}
\newcommand{\bottom}{\bot}
\newcommand{\minusb}{\boxminus}
\newcommand{\plusb}{\boxplus}
\newcommand{\timesb}{\boxtimes}
\newcommand{\intersection}{\cap}
\newcommand{\union}{\cup}
\newcommand{\Del}{\nabla}
\newcommand{\odash}{\circleddash}
\newcommand{\negspace}{\!}
\newcommand{\widebar}{\overline}
\newcommand{\textsize}{\normalsize}
\renewcommand{\scriptsize}{\scriptstyle}
\newcommand{\scriptscriptsize}{\scriptscriptstyle}
\newcommand{\mathfr}{\mathfrak}
\newcommand{\statusline}[2]{#2}
\newcommand{\tooltip}[2]{#2}
\newcommand{\toggle}[2]{#2}

% Theorem Environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{cor}{Corollary}
\newtheorem*{utheorem}{Theorem}
\newtheorem*{ulemma}{Lemma}
\newtheorem*{uprop}{Proposition}
\newtheorem*{ucor}{Corollary}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem{example}{Example}
\newtheorem*{udefn}{Definition}
\newtheorem*{uexample}{Example}
\theoremstyle{remark}
\newtheorem{remark}{Remark}
\newtheorem{note}{Note}
\newtheorem*{uremark}{Remark}
\newtheorem*{unote}{Note}

%-------------------------------------------------------------------

\begin{document}

%-------------------------------------------------------------------


\section*{Catalan number}

\hypertarget{context}{}\subsubsection*{{Context}}\label{context}

\hypertarget{combinatorics}{}\paragraph*{{Combinatorics}}\label{combinatorics}

[[!include combinatorics - contents]]

\hypertarget{contents}{}\section*{{Contents}}\label{contents}

\noindent\hyperlink{idea}{Idea}\dotfill \pageref*{idea} \linebreak
\noindent\hyperlink{some_structural_bijections}{Some structural bijections}\dotfill \pageref*{some_structural_bijections} \linebreak
\noindent\hyperlink{rooted_planar_binary_trees_and_magma_words}{Rooted planar binary trees and magma words}\dotfill \pageref*{rooted_planar_binary_trees_and_magma_words} \linebreak
\noindent\hyperlink{magma_words_and_rooted_planar_trees}{Magma words and rooted planar trees}\dotfill \pageref*{magma_words_and_rooted_planar_trees} \linebreak
\noindent\hyperlink{rooted_planar_trees_and_mountain_ranges}{Rooted planar trees and mountain ranges}\dotfill \pageref*{rooted_planar_trees_and_mountain_ranges} \linebreak
\noindent\hyperlink{mountain_ranges_and_stayahead_races}{Mountain ranges and stay-ahead races}\dotfill \pageref*{mountain_ranges_and_stayahead_races} \linebreak
\noindent\hyperlink{mountain_ranges_and_monotonic_lattice_paths}{Mountain ranges and monotonic lattice paths}\dotfill \pageref*{mountain_ranges_and_monotonic_lattice_paths} \linebreak
\noindent\hyperlink{monotonic_lattice_paths_and_pointed_inflationary_maps}{Monotonic lattice paths and pointed inflationary maps}\dotfill \pageref*{monotonic_lattice_paths_and_pointed_inflationary_maps} \linebreak
\noindent\hyperlink{structural_enumeration}{Structural enumeration}\dotfill \pageref*{structural_enumeration} \linebreak
\noindent\hyperlink{method_1}{Method 1}\dotfill \pageref*{method_1} \linebreak
\noindent\hyperlink{method_2}{Method 2}\dotfill \pageref*{method_2} \linebreak
\noindent\hyperlink{method_3}{Method 3}\dotfill \pageref*{method_3} \linebreak
\noindent\hyperlink{relation_to_cyclic_objects}{Relation to cyclic objects}\dotfill \pageref*{relation_to_cyclic_objects} \linebreak
\noindent\hyperlink{related_concepts}{Related concepts}\dotfill \pageref*{related_concepts} \linebreak
\noindent\hyperlink{references}{References}\dotfill \pageref*{references} \linebreak


\hypertarget{idea}{}\subsection*{{Idea}}\label{idea}

Catalan numbers are a specific sequence of [[negative number|nonnegative]] [[integers]], here denoted $C_n$, with a ubiquitous [[combinatorics|combinatorial]] interpretations. In terms of [[binomial coefficients]] they are given by

\begin{displaymath}
C_n = \frac{1}{n+1}\binom{2 n}{n} = \frac1{2n+1}\binom{2n+1}{n} = \frac{(2n)!}{n!(n+1)!}
  \,.
\end{displaymath}
The Catalan numbers $C_n$ count a myriad of different families of objects, including:

\begin{itemize}%
\item nonisomorphic (rooted planar) binary [[trees]] with $n$ internal [[vertices]];


\item ways of unambiguously defining the product of elements $x_0,\dots,x_n$ within an arbitrary (not necessarily [[associative]]) [[magma]], or equivalently, ways of fully parenthesizing a string of $n+1$ letters;


\item elements of the free magma $Mag(x)$ generated by a singleton $x$ (called \emph{words}) that have $n+1$ instances of the letter $x$;


\item nonisomorphic rooted planar [[trees]] with $n$ [[edges]];


\item strings consisting of $n$ well-balanced pairs of parentheses (also known as ``Dyck words''), or equivalently, [[surjective]] [[monotone functions]] $w : (n) + (n) \to (2n)$ such that $w(\iota_1 j) \le w(\iota_2 j)$ for all $1 \le j \le n$ (where we write $(k)$ for the finite [[ordinal]] $(k) = \{1,\dots,k\}$);


\item monotonic lattice paths in an $n\times n$ grid which do not cross below the diagonal, or equivalently, [[injective]] [[monotone functions]] $p : [2n] \to [n] \times [n]$ such that $\pi_1 p(i) \le \pi_2 p(i)$ for all $0 \le i \le 2n$ (where we write $[k]$ for the non-empty finite [[ordinal]] $[k] = \{0,\dots,k\}$);


\item [[monotone functions]] $f : [n] \to [n]$ such that $f(0) = 0$ and $x \le f(x)$ for all $0 \le x \le n$, or in other words, 1-cells $f : [n] \to [n]$ in $\Delta_\bot$ (the sub-2-category of the [[simplex category|simplex 2-category]] $\Delta$ spanned by the first-element-preserving functions) which are \emph{pointed} in the sense of being equipped with a 2-cell $\id_{[n]} \Rightarrow f$;


\item ``mountain ranges'', i.e., functions $f: [2n] \to \mathbb{N}$ such that $f(0) = 0 = f(2n)$ and $f(j+1) - f(j) \in \{1, -1\}$ for $0 \leq j \lt 2n$ (so called because graphs of such depict mountain ranges);


\item ``stay-ahead races'', i.e., functions $f: [2n] \to \{1, -1\}$ such that $\sum_{i=0}^j f(i) \gt 0$ for $0 \leq j \leq 2n$, and $\sum_{i=0}^{2n} f(i) = 1$ (see below for explanation of terminology);



\end{itemize}
and many, many more besides (see the \hyperlink{Stanley2015}{Stanley} references and OEIS \hyperlink{a000108}{A000108}).

\hypertarget{some_structural_bijections}{}\subsection*{{Some structural bijections}}\label{some_structural_bijections}

In this section we describe some ``canonical'' isomorphisms between various structures named above. Most of these can be seen as isomorphisms between various [[species]] of structures, which collectively might be called ``the Catalan species''.

\hypertarget{rooted_planar_binary_trees_and_magma_words}{}\subsubsection*{{Rooted planar binary trees and magma words}}\label{rooted_planar_binary_trees_and_magma_words}

Each (finite) rooted planar binary tree $T$ with $n$ internal vertices (i.e., vertices that have a left child and a right child) either consists of only a root (the case $n=0$), or has a left subtree $T_l$ and a right subtree $T_r$ adjacent to the root. The associated magma word $m(T) \in Mag(x)$ is defined recursively according to these cases:

\begin{itemize}%
\item $m(T) = x$ in the case $n=0$;


\item $m(T) = m(T_l) m(T_r)$ expressing the magma product by simple juxtaposition in the case $n \gt 0$.



\end{itemize}
Put slightly differently, the collection of isomorphism classes of rooted planar binary trees carries a magma structure, defined by $(T_l, T_r) \mapsto T$ using the notation above, and we have the following result.

\begin{prop}
\label{}\hypertarget{}{}
The mapping $T \mapsto m(T)$ defines a bijection from the set $Bin_n$ of isomorphism clases of rooted planar binary trees with $n$ internal vertices to the set $Mag(x)_n$ of magma words with $n+1$ instances of $x$.

\end{prop}
The inverse is given by the unique magma map $Mag(x) \to Bin$ that takes $x$ to the isomorphism class of trees consisting of just a root.

\hypertarget{magma_words_and_rooted_planar_trees}{}\subsubsection*{{Magma words and rooted planar trees}}\label{magma_words_and_rooted_planar_trees}

It is often suggestive to use exponential notation to denote the magma operation: $(x, y) \mapsto x^y$. For each element $a$ of the free magma $Mag(x)$, there is thus an unary operation $(-)^a$. If $Mag(x)^\ast$ denotes the free monoid on the set $Mag(x)$, there is a unique monoid map

\begin{displaymath}
\phi: Mag(x)^\ast \to \hom(Mag(x), Mag(x))
\end{displaymath}
that carries $a \in Mag(x)$ to the unary operation $(-)^a$. For $a \in Mag(x)$, it is reasonable to denote the composite

\begin{displaymath}
Mag(x)^\ast \stackrel{\phi}{\to} \hom(Mag(x), Mag(x)) \stackrel{eval_a}{\to} Mag(x)
\end{displaymath}
by $w \mapsto a^w$. Denote the monoid product in $Mag(x)^\ast$ by simple juxtaposition. Under these conventions, we have for $a, b, c \in Mag(x)$ the exponential equation

\begin{displaymath}
(a^b)^c = a^{b c}.
\end{displaymath}
If we regard the right-hand side of the exponential equation as a reduction of the left-hand side, then for any formal magma expression $a^d$, either $a = x$, or we may write $a = b^c$ and then reduce $a^d$ to $b^{c d}$.

Continuing recursively in this manner, every word $a \in Mag(x)$ can be eventually expressed as a ``reduced form'' (where no further reductions are possible), where we formally define a \textbf{reduced form} as follows:

\begin{itemize}%
\item The expression $x$ is a reduced form;


\item If $w_1, w_2, \ldots, w_n$ are reduced forms, then so is $x^{w_1 w_2 \ldots w_n}$.



\end{itemize}
The reader who is following where this is going will have observed that this recursive description of reduced forms matches precisely the recursive description of rooted planar trees, formalized by saying the set $Tree$ of isomorphism classes of rooted planar trees is the least fixed point, or [[initial algebra of an endofunctor|initial algebra]], of the [[endofunctor]] $T \mapsto T^\ast$ on $Set$.

To put it more visually: let us designate the term $x$ appearing as the base of a reduced form $x^{w_1 \ldots w_n}$ as the root of a corresponding tree. (If the reduced form is just $x$, then that $x$ is designated the root of a tree consisting of only a root.) The reduced forms $w_i$ themselves have roots, and we draw an edge connecting those roots to the root $x$ appearing in the base. Continuing this pattern, we climb recursively up the stacked exponentials, eventually obtaining a structure of rooted planar tree from a reduced form, whose vertices are just the instances of $x$ appearing in the reduced form.

In fact, there is no harm in identifying rooted planar trees with reduced forms, and we will repeatedly use this identification below.

Letting $Red(w)$ denote the reduced form of a magma word $w \in Mag(x)$, we thus have the following result.

\begin{prop}
\label{}\hypertarget{}{}
The mapping $w \mapsto Red(w)$ defines a bijection from $Mag(x)_n$ to $Tree_n$, i.e., from magma words having $n+1$ instances of $x$ to isomorphism classes of rooted planar trees with $n$ edges.

\end{prop}
The inverse takes a reduced form $x^w = x^{w_1 w_2 \ldots w_n}$ to the magma word $\mu(x^w)$ defined recursively by

\begin{displaymath}
(\ldots ((x^{\mu(w_1)})^{\mu(w_2)})\ldots )^{\mu(w_n)}
\end{displaymath}
and $\mu(x) = x$.

\hypertarget{rooted_planar_trees_and_mountain_ranges}{}\subsubsection*{{Rooted planar trees and mountain ranges}}\label{rooted_planar_trees_and_mountain_ranges}

To each rooted planar tree or reduced form $x^{w_1 \ldots w_n}$ with $k$ edges, we associate a mountain range $f: [2k] \to \mathbb{N}$ as follows.

In the first place, there is a monoid structure on the set of mountain ranges, essentially given by juxtaposition. Formally, if $f: [2m] \to \mathbb{N}$ and $g: [2n] \to \mathbb{N}$ are mountain ranges, then their product

\begin{displaymath}
f \ast g: [2(m+n)] \to \mathbb{N}
\end{displaymath}
is defined by $j \mapsto f(j)$ if $0 \leq j \leq 2m$, and $j \mapsto g(j-2m)$ if $2m \leq 2(m+n)$, noting that $(f \ast g)(2m) = 0$ in either case by definition of mountain range ($f(2m) = 0 = g(0)$).

We define $Moun: Tree^\ast \to Range$, from the free monoid on trees to mountain ranges, by the following recursive rules:

\begin{itemize}%
\item $Moun(x): \{0\} \to \mathbb{N}$ takes the value $0$.


\item If $Moun(w_1), \ldots Moun(w_n)$ have been defined for reduced forms $w_1, \ldots, w_n$, then

\begin{itemize}%
\item $Moun(w_1 \ldots w_n) = Moun(w_1) \ast \ldots \ast Moun(w_n)$, as a function $[2k] \to \mathbb{N}$ for some $k$, in which case


\item $Moun(x^{w_1 \ldots w_n}): [2(k+1)] \to \mathbb{N}$ takes $j$ for $1 \leq j \leq 2k+1$ to $1 + Moun(w_1 \ldots w_n)(j-1)$.



\end{itemize}


\end{itemize}
Then define $\rho: Tree \to Range$ to be the mapping that takes a tree $T = x^w$ to $Moun(w)$.

\begin{prop}
\label{}\hypertarget{}{}
The mapping $T \mapsto \rho(T)$ defines a bijection from $Tree_n$ to $Range_n$ , consisting of mountain ranges of the form $f: [2n] \to \mathbb{N}$.

\end{prop}
The inverse mapping can be described as follows. For each mountain range $f: [2n] \to \mathbb{N}$, we may subdivide the interval $[2n]$ into subintervals according to subdivision points $2n_k$ where $f(2n_k) = 0$. If there is at least one internal subdivision point given by an $n_k$ such that $0 \lt n_k \lt n$, then the restriction of $f$ to the subintervals (before and after $n_k$) gives mountain ranges $f_1, f_2$, which by strong induction on $n$ have assigned reduced trees $x^{w_1} = \rho^{-1}(f_1), x^{w_2} = \rho^{-1}(f_2)$, and then we put $\rho^{-1}(f) = x^{w_1 w_2}$. If there are no internal subdivision points, then $f \geq 1$ on the subinterval $\{1, 2, \ldots, 2n-1\}$. Notice moreover that $f(1) = 1 = f(2n-1)$, using the mountain range conditions $f(0) = 0 = f(2n)$ and $f(j+1) - f(j) \in \{1, -1\}$. This means the function $g = f-1$ defines a mountain range over the subinterval $\{1, \ldots, 2n-1\}$; by induction this has an assigned reduced tree $T = \rho^{-1}(g)$, and then we define $\rho^{-1}(f) = x^T$. This completes the description of the inverse mapping.

\hypertarget{mountain_ranges_and_stayahead_races}{}\subsubsection*{{Mountain ranges and stay-ahead races}}\label{mountain_ranges_and_stayahead_races}

The terminology ``stay-ahead'' race is suggested by the following scenario: a poll race is held between a proponent P and an opponent O. A vote for P is indicated by the value $1$, a vote for O by $-1$. Votes are counted one after another (tracked by a function $f: [2n] \to \{1, -1\}$) and partial tallies are recorded. The stay-ahead conditions are that each partial tally has P ahead of O (i.e., $\sum_{i=0}^j f(i) \gt 0$ for each $j \in [2n]$), and that P wins in the end by just one vote: $\sum_{i=0}^{2n} f(i) = 1$.

To each stay-ahead race $f: [2n] \to \{1, -1\}$ we associate a mountain range $g = \Sigma(f): [2n] \to \mathbb{N}$ by defining $g(j) = -1 + \sum_{i=0}^j f(i)$.

\begin{prop}
\label{}\hypertarget{}{}
The mapping $f \mapsto \Sigma(f)$ defines a bijection $Race_n \to Range_n$ from stay-ahead races $[2n] \to \{1, -1\}$ to mountain ranges $[2n] \to \mathbb{N}$.

\end{prop}
The inverse mapping takes a mountain range $g: [2n] \to \mathbb{N}$ to the stay-ahead race defined by the function $j \mapsto g(j) - g(j-1)$ for $0 \leq j \leq 2n$, making use of a nonce convention $g(-1) \coloneqq -1$.

\hypertarget{mountain_ranges_and_monotonic_lattice_paths}{}\subsubsection*{{Mountain ranges and monotonic lattice paths}}\label{mountain_ranges_and_monotonic_lattice_paths}

A mountain range $f: [2n] \to \mathbb{N}$ (or more precisely, the graph of a mountain range) can easily be converted, by a linear transformation, to an injective poset mapping $g = (g_1, g_2): [2n] \to [n] \times [n]$ satisfying the diagonal conditions $g(0) = (0, 0)$, $g(2n) = (n, n)$, and $g_1 \leq g_2$.

To wit: we remark that for a mountain range $f$, each value $f(j)$ has the same parity as $j$, and $f(j) \leq j$ for all $j \in [2n]$. (Both are simple consequences of the mountain range conditions.) Define

\begin{itemize}%
\item $g_1(j) = \frac1{2}(j - f(j))$,


\item $g_2(j) = \frac1{2}(j + f(j))$.



\end{itemize}
Denote the poset map $g = (g_1, g_2)$ thus defined by $\lambda(f)$. Let $Path_n$ denote the set of monotonic lattice paths satisfying the diagonal conditions.

\begin{prop}
\label{}\hypertarget{}{}
The mapping $f \mapsto \lambda(f)$ defines a bijection $Range_n \to Path_n$.

\end{prop}
The inverse mapping takes an element $(g_1, g_2) \in Path_n$ to the mountain range defined by $j \mapsto g_2(j) - g_1(j)$. The injectivity of $g = (g_1, g_2)$ forces each step of the path to go just one step (or block) north or just one block east, corresponding to the fact that the difference between $g_2(j+1) - g_1(j+1)$ and $g_2(j) - g_1(j)$ always lies in $\{1, -1\}$.

\hypertarget{monotonic_lattice_paths_and_pointed_inflationary_maps}{}\subsubsection*{{Monotonic lattice paths and pointed inflationary maps}}\label{monotonic_lattice_paths_and_pointed_inflationary_maps}

Each injective map $g = (g_1, g_2): [2n] \to [n] \times [n]$ determines and is determined by a map $f = \phi(g): [n] \to [n]$ defined as follows: if $0 \leq j \leq n$, then $f(j) = \min \{g_2(k): g_1(k) = j\}$. (The injectivity of $g$ implies that the lattice path crosses each line $x = j$.)

\begin{prop}
\label{}\hypertarget{}{}
The mapping $g \mapsto \phi(g)$ defines a bijection from $Path_n$ to the set $PtInf_n$ consisting of maps $f: [n] \to [n]$ such that $f(0) = 0$ and $j \leq f(j)$ for all $j \in [n]$.

\end{prop}
Indeed, the pointed inflationary conditions on $f$ are direct consequences of the diagonal conditions on $g$. The inverse mapping takes such a function $f$ to the lattice path that proceeds north and east, interpolating through the points

\begin{displaymath}
(0, 0)\;\; (0, f(1))\;\; (1, f(1))\;\; (1, f(2))\;\; \ldots\;\; (n, n).
\end{displaymath}
\hypertarget{structural_enumeration}{}\subsection*{{Structural enumeration}}\label{structural_enumeration}

The bijections of the last section indicate that all of the structures named above are counted by the same quantity $C_n$. There are several ways of establishing the binomial expressions for $C_n$ mentioned above.

\hypertarget{method_1}{}\subsubsection*{{Method 1}}\label{method_1}

A tried-and-true approach (explained in \hyperlink{bd}{Baez-Dolan}) is by means of generating functions. To enumerate rooted planar binary trees with $n$ internal indices, use the fact that there is just one such tree where $n=0$ (i.e., $C_0 = 1$), and that in the case $n \gt 0$, each tree $T$ is determined by a pair $(T_l, T_r)$ consisting of a left tree and right tree adjacent to the root; if $T_l$ has $n_l$ internal vertices and $T_r$ has $n_r$ internal vertices, then $n = n_l + n_r + 1$. Hence for $n \geq 0$ we have the recursive equation

\begin{displaymath}
C_{n+1} = \sum_{j + k = n} C_j C_k.
\end{displaymath}
Letting $C(x) = \sum_{n \geq 0} C_n x^n$ be the generating function (really a [[formal power series]]), the recursion leads to

\begin{displaymath}
C(x) = 1 + x C(x)^2
\end{displaymath}
which we solve as $C(x) = \frac{1 - \sqrt{1 - 4x}}{2x}$ in the formal power series sense. Starting with the [[binomial theorem]] to expand $(1 - 4x)^{1/2}$ as a power series, a series of (somewhat tedious and unilluminating) manipulations eventually leads to the calculation

\begin{displaymath}
C_n = \frac1{n+1}\binom{2n}{n}.
\end{displaymath}
\hypertarget{method_2}{}\subsubsection*{{Method 2}}\label{method_2}

A more structural derivation can be obtained by counting stay-ahead races, in the following manner. Let $S_n$ be the set of functions $f: [2n] \to \{1, -1\}$ for which $\sum_{i=0}^{2n} f(i) = 1$. Each such $f$ takes the value $1$ a total of $n+1$ times, and the value $-1$ a total of $n$ times, so the cardinality of $S_n$ is $\binom{2n+1}{n}$.

We let the [[cyclic group]] $\mathbb{Z}/(2n+1)$ [[group action|act]] on $S_n$, by precomposing functions $f: [2n] \to \{1, -1\}$ with powers of the cyclic [[permutation]]

\begin{displaymath}
\tau = (0\; 1\; \ldots\; 2n): [2n] \to [2n].
\end{displaymath}
The number of stay-ahead races in $Race_n$ is seen to be $C_n = \frac1{2n+1}\binom{2n+1}{n}$, as soon as we establish the following result.

\begin{prop}
\label{}\hypertarget{}{}
Each [[orbit]] of the cyclic group action on $S_n$ contains exactly one stay-ahead race, and has exactly $2n+1$ elements.

\end{prop}
\begin{proof}
Given $f \in S_n$, form the unique extension $\tilde{f}: \mathbb{Z} \to \{1, -1\}$ that is periodic with period $2n+1$. Let $g = \sigma(f)$ be the unique function such that $g(0) = 0$ and

\begin{displaymath}
g(j+1) - g(j) = \tilde{f}(j)
\end{displaymath}
for all $j \in \mathbb{Z}$. For example, $g(j) = \sum_{0 \leq i \lt j} \tilde{f}(i)$ for all $j \geq 0$.

Observe that $g(j+2n+1) = g(j)+1$ for all $j$, so that the line $L_{g, j}$ with slope $\frac1{2n+1}$ that passes through $(j, g(j))$ also passes through $(j+2n+1, g(j+2n+1))$, but passes through no other $(k, g(k))$ for $j \lt k \lt j+2n+1$ since $g(k)$ is integral but $L_{g, j}(k)$ is not, being strictly between $g(j)$ and $g(j)+1$. This implies that the lines $L_{g, j}$ for $j$ ranging over a period block $\{j, j+1, \ldots, j+2n\}$ are all distinct, i.e., the cyclic group action on these $L_{g, j}$ according to the formula $\tau L_{g, j} = L_{g, j+1}$ is faithful.

Pick $j$ so that the line $L_j$ is ``lowest''; all the lines have the same slope $\frac1{2n+1}$, so lowest just means $L_j(0)$ is minimal. Minimality implies that that for every other $k \neq j$ within a periodic block, the point $(k, g(k))$ lies above the line $y = L_j(x)$. Translating this picture horizontally by $j$ by considering $g \circ \tau^j$, and then vertically by subtracting $g(j) = (g \circ \tau^j)(0)$, i.e., putting $h = \sigma(f \circ \tau^j)$, this means that all points $(k, h(k))$ for $k = 1, \ldots, 2n+1$ stay above the line $y = L_{h, 0}(x) = \frac1{2n+1}(x)$. In other words, these values $h(k)$ are all positive and $h(2n+1) = 1$: precisely the stay-ahead conditions for $f \circ \tau^j$. Thus the orbit of any $f \in S_n$ contains a stay-ahead race. Moreover, this is the only stay-ahead race in the orbit since the stay-ahead positivity condition is equivalent to the minimality condition on $L_j$, and all the $L_j$ are distinct.

Finally, the stabilizer of $f$ must be trivial, else we would have $L_{g, j} = L_{g, j+k}$ for $k$ a non-multiple of $2n+1$: as we saw before, this can't happen.

\end{proof}
\hypertarget{method_3}{}\subsubsection*{{Method 3}}\label{method_3}

Yet another proof of the formula is based on Jean-Luc Rémy's algorithm for generating binary trees uniformly at random \hyperlink{KnuthTACP4a}{(see Knuth TACP 4A, Section 7.2.1.6)}, which can be described as $n$ iterations of the following simple rule:

\begin{itemize}%
\item Pick any edge of the tree.


\item Create a new internal node by splitting the edge in two and budding off a freshly-labelled leaf, either to the left or to the right of the new internal node.



\end{itemize}
Starting from the trivial binary tree (containing no internal nodes and a single leaf labelled ``0''), this algorithm will generate a binary tree with $n$ internal nodes, together with a labelling of its leaves by distinct labels in $0 \dots n$. Moreover, it does so exhaustively and without repetition, that is, every binary tree equipped with a permutation of its leaves will be generated exactly once. (An easy way to see this is by thinking of applying the algorithm ``in reverse'' to an arbitrary leaf-labelled binary tree, repeatedly pruning off the leaf with the largest label while recording whether it is a left leaf or a right leaf, until only the root edge remains.)

Since at the $k$th iteration of the algorithm there are exactly $(2k-1)\cdot 2$ possible choices of an edge and a direction, after $n$ iterations we obtain the identity:

\begin{displaymath}
C_n\cdot (n+1)! = (2n-1)!! \cdot 2^n
\end{displaymath}
(where $(2n-1)!! = (2n-1)(2n-3)\cdots 1 = \frac1{2^n} \frac{(2n)!}{n!}$ is the [[double factorial]]), which implies that

\begin{displaymath}
C_n = (2n-1)!! \cdot 2^n/(n+1)! = \frac{(2n)!}{n!(n+1)!} \,.
\end{displaymath}
\hypertarget{relation_to_cyclic_objects}{}\subsection*{{Relation to cyclic objects}}\label{relation_to_cyclic_objects}

As pointed out for example in \hyperlink{KV}{Kapranov-Voevodsky}, another description of a Catalan species is by way of subdivisions of a regular polygon with $n+2$ points (labeled by elements in $[n+1]$ in clockwise order) into $n$ triangles. Thus there are $2$ distinct subdivisions of a square, $5$ possible subdivisions of a pentagon, and in general $C_n$ possible subdivisions of an $(n+2)$-gon.

(To be continued.)

\hypertarget{related_concepts}{}\subsection*{{Related concepts}}\label{related_concepts}

\begin{itemize}%
\item [[associahedron]]

\end{itemize}
\hypertarget{references}{}\subsection*{{References}}\label{references}

General references:

\begin{itemize}%
\item Wikipedia, \emph{\href{https://en.wikipedia.org/wiki/Catalan_number}{Catalan number}}
\item [[Richard P. Stanley]], \emph{Catalan addendum}, (to problems in Chapter 6 of \emph{Enumerative Combinatorics}, vol. 2) 96 pp. \href{http://www-math.mit.edu/~rstan/ec/catadd.pdf}{pdf}
\item [[Richard P. Stanley]], \emph{Catalan numbers}, 215 pp., Cambridge University Press 2015

\end{itemize}
Other references:

\begin{itemize}%
\item [[Donald E. Knuth]], \emph{The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1}, Addison-Wesley, 2011. See Section 7.2.1.6 on ``Generating all trees'' (also available as a \href{http://www.cs.utsa.edu/~wagner/knuth/fasc4a.pdf}{pre-fascicle}).


\item Sequence \href{https://oeis.org/A000108}{A000108} in the \href{https://oeis.org/}{OEIS}



\end{itemize}
For an interpretation in terms of [[species]] (or \emph{structure types}) see

\begin{itemize}%
\item [[John Baez]], [[James Dolan]], \emph{From Finite Sets to Feynman Diagrams}, (\href{https://arxiv.org/abs/math/0004133}{arXiv:math/0004133}, p. 19).

\end{itemize}
[[!redirects Catalan numbers]]



\end{document}