Action Graphs and Catalan Numbers

Gerardo Alvarez, Julia E. Bergner, and Ruben Lopez Department of Mathematics University of California, Riverside Riverside, CA 92521 USA

                       galva012@ucr.edu
                    bergnerj@member.ams.org
                       rlope015@ucr.edu

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 kth 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.

1 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 [1]. 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 kth step, the number of vertices and edges added is given by the kth Catalan number.

The Catalan numbers give a well-known sequence of natural numbers, arising in many contexts in combinatorics \underline{A000108} [3]. A long list of ways to obtain the Catalan numbers is found in Stanley’s book [4] and subsequent online addendum [5]. Here we use that the 0th Catalan number is C_{0} = 1, and , for any k ≥ 1, the (k + 1)st Catalan number C_{k+1} is given by the formula

C_{k+1} = ∑_{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.

2 Action graphs

We begin by recalling a few basic definitions.

Definition 1. A directed graph is a pair G = (V, E) where V is a set whose elements are called vertices and E is a set of ordered pairs of vertices, called edges. Given an edge e = (v, w), we call v the source of e, denoted by v = s(e), and call w the target of e, denoted by w = t(e).

For the directed graphs that we consider here, we assume that, for every v ∈ V, we have (v, v) ∈ 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.

Definition 2. A (directed) path in a directed graph is a sequence of edges e_{1}, …, e_{n} such that for each 1 ≤ i < k, t(e_{i}) = s(e_{i+1}). For paths consisting of more than one edge, we require all these edges to be nontrivial. We call s(e_{1}) the initial vertex of the path and t(e_{k}) the terminal vertex of the path.

The directed graphs we consider here are labelled by the natural numbers; in other words, they are equipped with a given function V → ℕ.

Definition 3. For each natural number k, the action graph A_{k} is the labeled directed graph defined inductively as follows. The action graph A_{0} is defined to be the graph with one vertex labeled by 0 and no nontrivial edges. Inductively, given the kth action graph A_{k}, define the (k + 1)st action graph A_{k+1} by freely adjoining new edges by the following rule. For any vertex v labeled by k, consider all paths in A_{k} with terminal vertex v. For each such path, adjoin a new edge whose source is the initial vertex u of the path, and whose target is a new vertex which is labeled by k + 1.

Thus, the first few action graphs can be depicted as follows:

\xymatrix{A_{0} : & •_{0} &  & A_{1} : & •_{0} \ar[r] & •_{1} \\ A_{2} : &  &  & A_{3} : & •_{3} & •_{3} \\  & •_{2} & •_{2} &  & •_{2} \ar[u] & •_{2} \ar[u] \\  & •_{0} \ar[u] \ar[r] & •_{1} \ar[u] & •_{3} & •_{0} \ar[u] \ar[d] \ar[l] \ar[r] & •_{1} \ar[u] \ar[d] \\  &  &  &  & •_{3} & •_{3}}

The main result which we wish to prove is the following, which indicates how many new vertices (and edges) are added to A_{k} to obtain A_{k+1}.

Theorem 4. When building A_{k+1} from A_{k}, the number of vertices added and labeled k + 1 (and likewise the number of edges added) is given by the (k + 1)st Catalan number, C_{k+1}.

We begin with a lemma about paths in action graphs.

Lemma 5. The number of paths from 1 to k in A_{k} is equal to the number of paths from 0 to k − 1 in A_{k−1}.

Proof. In any A_{k} with k ≥ 1, there is only one edge connecting the single vertex labeled by 0 and the single vertex labeled by 1. Since the vertex labeled by 0 is the source and the vertex labeled by 1 is the target, no paths whose source is the vertex labeled by 1 pass through the vertex labeled by 0. Therefore, edges with source at the vertex labeled by 1 are adjoined exactly in the same way as edges with source 0, but one step later.

Proof of Theorem 4. We use induction and Lemma 5. For the base case we know that A_{0} has one vertex labeled by 0 and C_{0} = 1.

For the inductive step, suppose we know A_{k} has C_{k} vertices labeled by k. There is always a unique path from 0 to any vertex, so there are C_{k} paths from the vertex labeled by 0 to a vertex labeled by k. Hence, by considering paths with source the 0 vertex, we create C_{k} = C_{0}C_{k} new vertices in A_{k+1}. Lemma 5 tells us that there are C_{k−1} paths from the single vertex labeled by 1 to vertices labeled by k. Thus, we must add C_{k−1} = C_{1}C_{k−1} new vertices in A_{k+1}. Applying Lemma 5 twice, we similarly see that there are C_{k−2} paths from any vertex labeled by 2 (of which there are C_{2}) to any vertex labeled C_{k}, for a total of C_{2}C_{k−1} new vertices added. We continue this process, concluding by using the inductive hypothesis that there are C_{k} vertices labeled by k, from each of which there is only one (trivial) path, from which we produce C_{k} = C_{k}C_{0} new vertices. Taking the sum, we obtain that the total number of paths in A_{k} ending at vertices labeled by k is

C_{0}C_{k} + C_{1}C_{k−1} + ⋯ + C_{k}C_{0} = C_{k+1}.

Since a new vertex is added for each such path, and a new edge for each such vertex, we have completed the proof.

The main theorem has the following immediate consequence.

Corollary 6. The number of vertices in the kth action graph A_{k} is given by the kth term in the sequence of partial sums of Catalan numbers \underline{A014137} [3].

3 A comparison with planar rooted trees

In this section, we give an explicit one-to-one correspondence between the set of leaves of A_{k+1} and the set of planar rooted trees with k + 1 edges. The latter set has C_{k+1} elements [2, 8.4].

We begin with the necessary definitions. Here, we work with graphs which are no longer assumed to be directed. A graph is connected if there exists a path between any two vertices.

Definition 7. A tree is a connected graph with no loops or multiple edges. A rooted tree is a tree with a specified vertex called the root.

Definition 8. A leaf of a rooted tree is a vertex of valence 1 which is not the root. (In the case of a single vertex with no edges, we take this root vertex also to be a leaf.) A branch of a rooted tree is a path from either the root or from a vertex of valence greater than 2 to a leaf.

Note in particular that the action graphs are (directed) trees, and that the vertices of A_{k+1} which are not in A_{k} are precisely the leaves of A_{k+1}.

Here we want to consider planar rooted trees. Thus, if we view the bottom vertex as the root, we regard the following two trees as different:

[figure: •; •; •; •; •; •; •; •]

To aid in our comparison with action graphs, we define a means of labeling the vertices of a planar rooted tree. The root vertex is always given the label 0. Given a representative of the tree with the root at the bottom, label the vertices by successive natural numbers, moving upward from the root and from left to right. For example, we have the labelings

[figure: •_{2}; •_{3}; •_{1}; •_{3}; •_{1}; •_{2}; •_{0}; •_{0}.]

Our goal is to prove that we can use these labels to assemble planar rooted trees together to form the action graph in such a way that each planar rooted tree corresponds to exactly one vertex of highest labeling in the action graph.

Observe that the set of all directed trees with k edges can be partially ordered by the length of the unique path from the vertex labeled by 0 to the vertex labeled by k. Beginning with the tree with longest such path length, namely, the tree with a branch of length k, for each directed tree, identify the edge from 0 to 1, and any branches that do not end in the vertex k, with vertices and edges already present in the graph. Adjoin new vertices and edges to the graph corresponding to the branch containing the vertex k. Using the partial ordering on the set of trees guarantees that, as we assemble the trees together, each tree that is added contributes only (part of) a branch. Hence, any possible ambiguity about placement is eliminated. Repeating for all planar rooted trees with k edges, we claim that the resulting directed graph is precisely the action graph A_{k}.

This assembly can be depicted for the case when k = 2 as follows. We two planar rooted trees with two edges are given by

\xymatrix{•_{2} \\ •_{1} \ar@{-->}[u] & •_{1} &  & •_{2} \\ •_{0} \ar@{-->}[u] &  & •_{0} \ar@{.>}[ul] \ar@{.>}[ur]}

and can thus be assembled to form the action graph A_{2}, as given by

\xymatrix{•_{2} & •_{2} \\ •_{0} \ar@{.>}[u] \ar@{-->}[r] \ar@{.>}[r] & •_{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.

Theorem 9. 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.

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 ≥ 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 ≤ i ≤ k + 1 correspond exactly to the planar rooted trees with k + 1 edges. Again, assume this fact is true for k ≥ 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.

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

4 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.

References

[1] Julia E. Bergner and Philip Hackney, Reedy categories which encode the notion of category actions, Fund. Math., 228 (2015), 193–222.

[2] Thomas Koshy, Catalan Numbers with Applications, Oxford University Press, 2009.

[3] N. J. A. Sloane, Online Encyclopedia of Integer Sequences, http://oeis.org/.

[4] Richard P. Stanley, Enumerative Combinatorics, Vol. 2. Cambridge Studies in Advanced Mathematics, 62. Cambridge University Press, Cambridge, 1999.

[5] Richard P. Stanley, Catalan Addendum, http://www-math.mit.edu/~rstan/ec/catadd.pdf.

2010 Mathematics Subject Classification: Primary 05A19, Secondary 05C05. Keywords: Catalan number, directed graph.

(Concerned with sequences \underline{A000108} and \underline{A014137}.)

Received March 2 2015; revised version received June 12 2015; June 25 2015. Published in Journal of Integer Sequences, June 30 2015.

Return to Journal of Integer Sequences home page