Journal of Integer Sequences, Vol. 23 (2020), Article 20.7.7

Nonleaf Patterns in Trees: Protected Nodes and Fine Numbers

Nachum Dershowitz
School of Computer Science
Tel Aviv University
Ramat Aviv


We derive a closed-form formula for the number of occurrences of matches of a multiset of patterns among all ordered (plane-planted) trees with a given number of edges. A pattern looks like a tree, with internal nodes and leaves, but also contain components that match subtrees or sequences of subtrees. This result extends previous versatile tree-pattern enumeration formulae to incorporate components that are only allowed to match nonleaf subtrees and provides enumerations of trees by the number of protected (shortest outgoing path has two or more edges) or unprotected nodes.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000108 A000957 A001263 A001700 A002057 A003517 A003518 A003519 A014106 A014300 A039598 A114627 A143362 A143363 A172025.)

Received September 27 2018; revised version received March 6 2020. Published in Journal of Integer Sequences, June 27 2020.

Return to Journal of Integer Sequences home page