Non-Contiguous Pattern Avoidance in Binary Trees

Authors

Michael Dairyko
Samantha Tyner
Casey Wynn

Presentation Type

Poster Presentation

Symposium Date

2011

Abstract

We consider the enumeration of binary trees avoiding non-contiguous binary tree patterns. We begin by modifying a known algorithm that counts binary trees avoiding a single contiguous tree pattern. Next, we use this algorithm to prove several theorems about the generating function whose nth coefficient gives the number of n-leaf trees avoiding a pattern. In addition, we investigate and structurally explain the recurrences that arise from these generating functions. Finally, we examine the enumeration of binary trees avoiding multiple tree patterns.

Biographical Information about Author(s)

Link is to abstract only.

Recommended Citation

Dairyko, Michael; Tyner, Samantha; and Wynn, Casey, "Non-Contiguous Pattern Avoidance in Binary Trees" (2011). Symposium on Undergraduate Research and Creative Expression (SOURCE). 82.
https://scholar.valpo.edu/cus/82