\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\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,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\input xy
\xyoption{all}
\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}
\epsfxsize=4in
\end{center}
\begin{center}
\vskip 1cm{\LARGE\bf Action Graphs and Catalan Numbers}
\vskip 1cm
\large
Gerardo Alvarez, Julia E. Bergner, and Ruben Lopez \\
Department of Mathematics \\
University of California, Riverside \\
Riverside, CA 92521 \\
USA \\
\href{mailto:galva012@ucr.edu}{\tt galva012@ucr.edu} \\
\href{mailto:bergnerj@member.ams.org}{\tt bergnerj@member.ams.org} \\
\href{mailto:rlope015@ucr.edu}{\tt rlope015@ucr.edu}
\end{center}
\vskip .2 in
\begin{abstract}
We introduce an inductively defined sequence of directed graphs and prove that the number of edges added at step $k$ is equal to the $k$th Catalan number. Furthermore, we establish a bijection between the set of edges adjoined at step $k$ and the set of planar rooted trees with $k$ edges.
\end{abstract}
\section{Introduction}
In a recent paper, the second author and Hackney introduced certain inductively defined directed graphs with the goal of understanding the structure of a rooted category action on another category \cite{reedy}. While these graphs were developed in such a way that they encoded the desired structure, the question remained what kinds of patterns could be found in these inductively defined sequences of graphs. In this paper, we look at the most basic of these graph sequences. We begin with the trivial graph with one vertex and no edges, and we inductively add new vertices and edges depending on the number of paths in the previous graph. We prove that at the $k$th step, the number of vertices and edges added is given by the $k$th Catalan number.
The Catalan numbers give a well-known sequence of natural numbers, arising in many contexts in combinatorics \seqnum{A000108} \cite{oeis}. A long list of ways to obtain the Catalan numbers is found in Stanley's book \cite{stanley} and subsequent online addendum \cite{catadd}. Here we use that the 0th Catalan number is $C_0=1$, and , for any $k \geq 1$, the $(k+1)$st Catalan number $C_{k+1}$ is given by the formula
\[ C_{k+1} = \sum_{i=0}^k C_i C_{k-i}. \]
However, it is often of interest to determine a direct comparison with one of the other ways of obtaining the Catalan numbers. To this end, we establish a direct bijection between the set of edges added at step $k$ in the action graph construction and the set of planar rooted trees with $k$ edges, also known to have $C_k$ elements.
\section{Action graphs}
We begin by recalling a few basic definitions.
\begin{definition}
A \emph{directed graph} is a pair $G=(V,E)$ where $V$ is a set whose elements are called \emph{vertices} and $E$ is a set of ordered pairs of vertices, called \emph{edges}. Given an edge $e= (v, w)$, we call $v$ the \emph{source} of $e$, denoted by $v=s(e)$, and call $w$ the \emph{target} of $e$, denoted by $w=t(e)$.
\end{definition}
For the directed graphs that we consider here, we assume that, for every $v \in V$, we have $(v,v) \in E$. While we could think of these edges as loops at each vertex, we prefer to regard them as ``trivial" edges given by the vertices. Otherwise, we have no loops or multiple edges in the graphs we consider, so there is no ambiguity in the definition as we have given it.
\begin{definition}
A \emph{(directed) path} in a directed graph is a sequence of edges $e_1, \ldots, e_n$ such that for each $1\leq i}[u] & \bullet_1 && \bullet_2 \\
\bullet_0 \ar@{-->}[u] && \bullet_0 \ar@{..>}[ul] \ar@{..>}[ur] & } \]
and can thus be assembled to form the action graph $A_2$, as given by
\[ \xymatrix{\bullet_2 & \bullet_2 \\
\bullet_0 \ar@{..>}[u] \ar@{-->}[r]<.5ex> \ar@{..>}[r]<-.5ex> & \bullet_1. \ar@{-->}[u]} \]
Observe in this example that the overlap of the two trees in $A_2$ corresponds to the action graph $A_1$, and that the two new edges in $A_2$ correspond exactly to the two ways to attach an edge to the unique planar rooted tree with one edge to obtain a planar rooted tree with two edges.
Generalizing this example, we obtain the following explicit correspondence.
\begin{theorem}
The function assigning any planar rooted tree with $k$ edges to the leaf that it contributes to the action graph $A_k$ defines a bijection.
\end{theorem}
\begin{proof}
We prove this theorem inductively. When $k=0$, both $A_0$ and the only planar rooted tree with no edges consist of a single vertex and no edges.
Thus, suppose that we have proved the result for $k \geq 0$. Consider the set of planar rooted trees with $k+1$ edges. By our inductive hypothesis, the trees with $k$ edges assemble to produce the action graph $A_k$. But these trees can be obtained from those with $k+1$ vertices by removing the leaf labeled by $k+1$. Indeed, the (possibly multiple) ways of obtaining a rooted tree with $k+1$ edges from one with $k$ edges correspond to the ways we adjoin new leaves to produce $A_{k+1}$ from $A_k$. In particular, there is precisely one edge ending in a vertex labeled by $k+1$ coming from each planar rooted tree.
Conversely, regard $A_{k+1}$ as a labeled rooted tree. We claim that the subtrees of $A_{k+1}$ containing exactly one vertex labeled by $i$ for each $0 \leq i \leq k+1$ correspond exactly to the planar rooted trees with $k+1$ edges. Again, assume this fact is true for $k \geq 0$. Given every such subtree with $k$ edges, and vertices labeled from 0 to $k$, the choices for adjoining an extra edge containing a vertex labeled by $k+1$ correspond exactly to the vertices on the path from the vertex labeled by 0 to the vertex labeled by $k$. But, these choices coincide with the ways to obtain a planar rooted tree with $k+1$ edges from a given planar rooted tree with $k$ edges.
\end{proof}
Observe that the action graph $A_k$ can thus be regarded as a universal tree for all planar rooted trees with $k$ edges, in that it is built from these subtrees and that, using the labeling scheme for planar rooted trees, these subtrees can be recovered from $A_k$.
\section{Acknowledgments}
The first and third authors were participants in the RISE program at UC
Riverside in Summer 2013, with support from the HSI-STEM and CAMP
programs, respectively. The second author was partially
supported by NSF grant DMS-1105766 and CAREER award DMS-1352298. The
authors thank the referee for suggestions which improved the exposition
of the paper.
\begin{thebibliography}{9}
\bibitem{reedy}
Julia E.\ Bergner and Philip Hackney, Reedy categories which encode the notion of category actions, \emph{Fund.\ Math.}, {\bf 228} (2015), 193--222.
\bibitem{koshy}
Thomas Koshy, \emph{Catalan Numbers with Applications}, Oxford University Press, 2009.
\bibitem{oeis}
N.\ J.\ A.\ Sloane, Online Encyclopedia of Integer Sequences, \url{http://oeis.org/}.
\bibitem{stanley}
Richard P.\ Stanley, \emph{Enumerative Combinatorics, Vol.~2.} Cambridge Studies in Advanced Mathematics, {\bf 62}. Cambridge University Press, Cambridge, 1999.
\bibitem{catadd}
Richard P.\ Stanley, Catalan Addendum, \url{http://www-math.mit.edu/~rstan/ec/catadd.pdf}.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent
2010 {\it Mathematics Subject Classification}: Primary 05A19, Secondary
05C05.
\noindent
\emph{Keywords:} Catalan number, directed graph.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences \seqnum{A000108} and \seqnum{A014137}.)
\bigskip
\hrule
\bigskip
\noindent
Received March 2 2015; revised version received June 12 2015; June
25 2015. Published in {\it Journal of Integer Sequences}, June 30 2015.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.waterloo.ca/journals/JIS/}
\bigskip
\hrule
\bigskip
\end{document}