×

Pattern avoidance in binary trees. (English) Zbl 1221.05058

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.

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
PDFBibTeX XMLCite
Full Text: DOI arXiv

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.