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.
Dairyko, Michael; Tyner, Samantha; and Wynn, Casey, "Non-Contiguous Pattern Avoidance in Binary Trees" (2011). Symposium on Undergraduate Research and Creative Expression (SOURCE). 82.