Nonleaf Patterns in Trees: Protected Nodes and Fine Numbers
Nachum Dershowitz
School of Computer Science
Tel Aviv University
Ramat Aviv
Israel
Abstract:
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