Page 1 
Save page Remove page  Previous  1 of 27  Next 


Preview Image (250x250 max)
medium (500x500 max)
Large
Extra Large
large ( > 500x500)
Full Resolution
All (PDF)

This page
All

Pattern Avoidance in Ternary Trees Nathan Gabriel, Katie Peske, Sam Tay July 30, 2010 Abstract This paper considers the enumeration of ternary trees (i.e. rooted trees in which each vertex has 0 or 3 children) avoiding a contiguous ternary tree pattern. We begin by nding the recurrence relations for several simple ternary trees; then, for more complex trees, we extend a known algorithm for nding the generating function that counts nleaf binary trees avoiding a given pattern. After investigating bijections between these trees' avoidance sequences and other common combinatorial objects, we conclude by nding a bijective method to restructure speci c tree patterns that give the same generating function, and generalizing this process to a larger class of ternary trees. 1 Introduction In recent years, pattern avoidance has proven to be a useful language to describe connections be tween various combinatorial objects. The notion of one object avoiding another has been studied in permutations, word, partitions, and graphs. In 2010, Rowland explored pattern avoidance in binary trees (that is, rooted trees in which each vertex has 0 or 2 children) because of the natural bijection between nleaf binary trees and nvertex trees. His study had two main objectives. First, he developed an algorithm to nd the generating function denoting the number of nleaf binary trees avoiding a given tree pattern; he adapted this to count the number of occurences of the given pattern. Second, he determined equivalence classes for binary tree patterns, classifying two trees s and t as equivalent if the same number of nleaf binary trees avoid s as avoid t for n 1. He com pleted the classi cation for all binary trees with at most six leaves, using these classes to develop replacement bijections between equivalent binary trees [1]. In this paper, we extend Rowland's work by exploring pattern avoidance in ternary trees, i.e. ordered rooted trees in which each vertex has 0 or 3 children. We follow a similar outline to work done in binary trees. As a preface to our work, we de ne a new system of notation to represent mary trees (that is, trees where each vertex has 0 or m children), which we use to discuss ternary trees. We then nd and explain the recurrence relations that count trees avoiding relatively simple ternary tree patterns (those with at most seven leaves), where the nth term denotes the number of nleaf trees avoiding the given tree pattern. Next, we adapt Rowland's algorithm to nd the avoid ance generating function for ternary trees; this is followed with a discussion of a Maple package written to produce the terms of the series representation of the generating function for any tree taken as input. Finally, we put forth bijections for several pairs of equivalent tree patterns, and begin generalizing this process to t a wider class of equivalent trees. The rst appendix contains all the equivalence classes of ternary trees with at most nine leaves found using the Maple package; the Maple package itself is given in Appendix Two. 1
Object Description
Title  Pattern Avoidance in Ternary Trees 
Author  Peske, Katherine; Gabrial, Nathan; Tay, Samuel; Pudwell, Dr. Lara 
Date Created  2012 
Keywords  Mathematics; Combinatorics; Graph theory; Trees 
Abstract  This paper considers the enumeration of ternary trees (i.e. rooted trees in which each vertex has 0 or 3 children) avoiding a contiguous ternary tree pattern. We begin by finding the recurrence relations for several simple ternary trees; then, for more complex trees, we extend a known algorithm for finding the generating function that counts nleaf binary trees avoiding a given pattern. After investigating bijections between these trees' avoidance sequences and other common combinatorial objects, we conclude by finding a bijective method to restructure specific tree patterns that give the same generating function, and generalizing this process to a larger class of ternary trees. 
Language  English 
Rights Management  Copyright owned by author. 
Research Honors 
Departmental Honors Paper 
Biography  This paper was written by Katherine Peske, a Mathematics and Computer Science double major from Bemidji, MN. It was a joint effort, with Nathan Gabriel and Samuel Tay, as part of a summer Research Experience for Undergraduates at Valparaiso University in Valparaiso, Indiana (sponsored by the National Science Foundation). The project was advised by Dr. Lara Pudwell. The paper was published in the Journal of Integer Sequences, volume 15, issue 1, in 2012. 
Notes  This paper is apart of the departmental honors paper for Mathematics & Computer Science; no applicable course (summer research); April 25. 2012 (research performed JuneJuly, 2010) 
Submission Date  20120425 
Type  Text 
Description
Title  Page 1 
Transcript  Pattern Avoidance in Ternary Trees Nathan Gabriel, Katie Peske, Sam Tay July 30, 2010 Abstract This paper considers the enumeration of ternary trees (i.e. rooted trees in which each vertex has 0 or 3 children) avoiding a contiguous ternary tree pattern. We begin by nding the recurrence relations for several simple ternary trees; then, for more complex trees, we extend a known algorithm for nding the generating function that counts nleaf binary trees avoiding a given pattern. After investigating bijections between these trees' avoidance sequences and other common combinatorial objects, we conclude by nding a bijective method to restructure speci c tree patterns that give the same generating function, and generalizing this process to a larger class of ternary trees. 1 Introduction In recent years, pattern avoidance has proven to be a useful language to describe connections be tween various combinatorial objects. The notion of one object avoiding another has been studied in permutations, word, partitions, and graphs. In 2010, Rowland explored pattern avoidance in binary trees (that is, rooted trees in which each vertex has 0 or 2 children) because of the natural bijection between nleaf binary trees and nvertex trees. His study had two main objectives. First, he developed an algorithm to nd the generating function denoting the number of nleaf binary trees avoiding a given tree pattern; he adapted this to count the number of occurences of the given pattern. Second, he determined equivalence classes for binary tree patterns, classifying two trees s and t as equivalent if the same number of nleaf binary trees avoid s as avoid t for n 1. He com pleted the classi cation for all binary trees with at most six leaves, using these classes to develop replacement bijections between equivalent binary trees [1]. In this paper, we extend Rowland's work by exploring pattern avoidance in ternary trees, i.e. ordered rooted trees in which each vertex has 0 or 3 children. We follow a similar outline to work done in binary trees. As a preface to our work, we de ne a new system of notation to represent mary trees (that is, trees where each vertex has 0 or m children), which we use to discuss ternary trees. We then nd and explain the recurrence relations that count trees avoiding relatively simple ternary tree patterns (those with at most seven leaves), where the nth term denotes the number of nleaf trees avoiding the given tree pattern. Next, we adapt Rowland's algorithm to nd the avoid ance generating function for ternary trees; this is followed with a discussion of a Maple package written to produce the terms of the series representation of the generating function for any tree taken as input. Finally, we put forth bijections for several pairs of equivalent tree patterns, and begin generalizing this process to t a wider class of equivalent trees. The rst appendix contains all the equivalence classes of ternary trees with at most nine leaves found using the Maple package; the Maple package itself is given in Appendix Two. 1 