Lattice path enumeration by formal schema

DOI10.1016/0196-8858(92)90010-TMaRDI QIDQ1197397zbMATH OpenOpenAlexFDO

Authors Jay R. Goldman, Thomas S. Sundquist

Publication date 16 January 1993

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-8858(92)90010-t

zbMATH Keywords

formal schemalattice path enumerationrooted plane treeword

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Trees (05C05) Special sequences and polynomials (11B83) Formal languages and automata (68Q45)

Review text

This paper gives another formal description of Pólya's idea of picture writing. An unlabelled rooted plane tree is represented as a word of the free monoid generated by the alphabet \(t\), ), \((_ n,\;n=1,2,3,\dots\), by starting with \(D\) and using the substitution rules \(D\to(_ n D^ n)\) if \(n\) is the number of edges emanating from the vertex \(D\) and \(D\to t\) for a terminal point.

Recommendations

• Lattice path enumeration
• Enumerating a class of lattice paths
• Enumerating and constructing essentially equivalent lattice paths
• scientific article; zbMATH DE number 1058045
• Enumerating lattice paths to hyperplanes
• Enumerating minimal length lattice paths
• scientific article; zbMATH DE number 2247202
• A probabilistic method for lattice path enumeration
• Refined lattice path enumeration and combinatorial reciprocity
• Lattices of lattice paths

Cites work

• Chain enumeration and non-crossing partitions
• Combinatorial aspects of continued fractions
• Formal languages and enumeration
• scientific article; zbMATH DE number 3821741 (Why is no real title available?)
• scientific article; zbMATH DE number 3957110 (Why is no real title available?)
• scientific article; zbMATH DE number 3681764 (Why is no real title available?)
• scientific article; zbMATH DE number 3712896 (Why is no real title available?)
• scientific article; zbMATH DE number 3758344 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)

Cited in

(6)

• Underdiagonal lattice paths with unrestricted steps
• The Formal System of Dijkstra and Scholten
• A combinatorial study of the growing altitude elementary paths of the plane lattice Z²
• scientific article; zbMATH DE number 2010461 (Why is no real title available?)
• The area determined by underdiagonal lattice paths
• Context-free grammars, differential operators and formal power series

This page was built for publication: Lattice path enumeration by formal schema

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