Nonleaf patterns in trees: protected nodes and fine numbers

MaRDI QIDQ3300679zbMATH OpenFDO

Authors Nachum Dershowitz

Publication date 29 July 2020

Full work available at URL https://arxiv.org/abs/1908.04329, https://cs.uwaterloo.ca/journals/JIS/VOL23/Dershowitz/dersh4.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

treeslattice pathDyck pathinteger sequencestree patterntree enumerationFine numberprotected nodeFine pathhill

Mathematics Subject Classification ID

Trees (05C05) Exact enumeration problems, generating functions (05A15) Enumeration in graph theory (05C30)

Abstract: A closed-form formula is derived 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.

Recommendations

• Patterns in trees
• scientific article; zbMATH DE number 3871389
• Enumeration of protected nodes in Motzkin trees
• Noncontiguous pattern containment in binary trees
• Plane trivalent trees and their patterns

Cites work

• scientific article; zbMATH DE number 3270295 (Why is no real title available?)
• A Catalan triangle
• A problem of arrangements
• A survey of the Fine numbers
• A transformation on ordered trees
• Dyck path enumeration
• Enumeration of plane trees by branches and endpoints
• Enumerations of ordered trees
• More patterns in trees: up and down, young and old, odd and even
• Patterns in trees
• Protected points in ordered trees
• Protection number in plane trees
• Some bijections and identities for the Catalan and Fine numbers
• The cycle lemma and some applications
• The on-line encyclopedia of integer sequences
• \(k\)-protected vertices in unlabeled rooted plane trees

Cited in

(4)

• scientific article; zbMATH DE number 3871389 (Why is no real title available?)
• More patterns in trees: up and down, young and old, odd and even
• Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata
• Protection number in plane trees

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Nonleaf patterns in trees: protected nodes and fine numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3300679)