Rowland, Eric S. Pattern avoidance in binary trees. (English) Zbl 1221.05058 J. Comb. Theory, Ser. A 117, No. 6, 741-758 (2010). Summary: This paper considers the enumeration of trees avoiding a contiguous pattern. We provide an algorithm for computing the generating function that counts \(n\)-leaf binary trees avoiding a given binary tree pattern \(t\). Equipped with this counting mechanism, we study the analogue of Wilf equivalence in which two tree patterns are equivalent if the respective \(n\)-leaf trees that avoid them are equinumerous. We investigate the equivalence classes combinatorially. Toward establishing bijective proofs of tree pattern equivalence, we develop a general method of restructuring trees that conjecturally succeeds to produce an explicit bijection for each pair of equivalent tree patterns. Cited in 20 Documents MSC: 05C05 Trees 05A05 Permutations, words, matrices 05C30 Enumeration in graph theory 05A15 Exact enumeration problems, generating functions 05C85 Graph algorithms (graph-theoretic aspects) 68R10 Graph theory (including graph drawing) in computer science Keywords:pattern avoidance; binary trees; Wilf equivalence; algebraic generating functions; Dyck words Software:OEIS; Singular; BinaryTrees; TreePatterns PDFBibTeX XMLCite \textit{E. S. Rowland}, J. Comb. Theory, Ser. A 117, No. 6, 741--758 (2010; Zbl 1221.05058) Full Text: DOI arXiv Online Encyclopedia of Integer Sequences: Catalan numbers (A000108) interpolated with 0’s. Number of n-leaf binary trees that do not contain (()(()(()((()())())))) as a subtree. Number of n-leaf binary trees that do not contain (((()())())(()(()()))) as a subtree. Number of n-leaf binary trees that do not contain (()(()(((()())())()))) as a subtree. Number of n-leaf binary trees that do not contain (()((()())((()())()))) as a subtree. Number of n-leaf binary trees that do not contain (()((((()())())())())) as a subtree. Number of n-leaf binary trees that do not contain ((()())(()((()())()))) as a subtree. The number of equivalence classes of n-leaf binary trees with respect to pattern avoidance. References: [1] Deutsch, Emeric, Dyck path enumeration, Discrete Math., 204, 167-202 (1999) · Zbl 0932.05006 [2] Donaghey, Robert; Shapiro, Louis, Motzkin numbers, J. Combin. Theory Ser. A, 23, 291-301 (1977) · Zbl 0417.05007 [3] Flajolet, Philippe; Sedgewick, Robert, Analytic Combinatorics (2009), Cambridge University Press · Zbl 1165.05001 [4] Flajolet, Philippe; Sipala, Paolo; Steyaert, Jean-Marc, Analytic variations on the common subexpression problem, (Automata, Languages, and Programming. Automata, Languages, and Programming, Lecture Notes in Comput. Sci., vol. 443 (1990)), 220-234 · Zbl 0765.68048 [5] Goulden, Ian; Jackson, David, An inversion theorem for cluster decompositions of sequences with distinguished subsequences, J. Lond. Math. Soc. (2), 20, 567-576 (1979) · Zbl 0467.05008 [6] Kauers, Manuel; Levandovskyy, Viktor, Singular [a Mathematica package], available from [7] Noonan, John; Zeilberger, Doron, The Goulden-Jackson cluster method: extensions, applications, and implementations, J. Difference Equ. Appl., 5, 355-377 (1999) · Zbl 0935.05003 [8] Rowland, Eric, TreePatterns [a Mathematica package], available from · Zbl 1398.11161 [9] Sapounakis, Aris; Tasoulas, Ioannis; Tsikouras, Panos, Counting strings in Dyck paths, Discrete Math., 307, 2909-2924 (2007) · Zbl 1127.05005 [10] Sloane, Neil, The encyclopedia of integer sequences · Zbl 1159.11327 [11] Stanley, Richard, Enumerative Combinatorics, vol. 2 (1999), Cambridge University Press: Cambridge University Press New York · Zbl 0928.05001 [12] Steyaert, Jean-Marc; Flajolet, Philippe, Patterns and pattern-matching in trees: an analysis, Inform. Control, 58, 19-58 (1983) · Zbl 0567.68053 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.