A generalized Goulden-Jackson cluster method and lattice path enumeration

DOI10.1016/J.DISC.2017.09.004MaRDI QIDQ1685986zbMATH OpenOpenAlexFDO

Authors Yan Zhuang

Publication date 20 December 2017

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1508.02793

zbMATH Keywords

statisticsgenerating functionslattice pathsfree monoidsMotzkin pathsGoulden-Jackson cluster method

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Enumeration in graph theory (05C30) Paths and cycles (05C38)

Abstract: The Goulden-Jackson cluster method is a powerful tool for obtaining generating functions for counting words in a free monoid by occurrences of a set of subwords. We introduce a generalization of the cluster method for monoid networks, which generalize the combinatorial framework of free monoids. As a sample application of the generalized cluster method, we compute bivariate and multivariate generating functions counting Motzkin paths---both with height bounded and unbounded---by statistics corresponding to the number of occurrences of various subwords, yielding both closed-form and continued fraction formulae.

Recommendations

• Generalizations of the Goulden–Jackson cluster method
• The symbolic Goulden-Jackson cluster method
• The Goulden-Jackson cluster method for cyclic words
• A lifting of the Goulden-Jackson cluster method to the Malvenuto-Reutenauer algebra
• The umbral transfer-matrix method. V: The Goulden-Jackson cluster method for infinitely many mistakes

Cites work

• scientific article; zbMATH DE number 41838 (Why is no real title available?)
• scientific article; zbMATH DE number 3588051 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• An Inversion Theorem for Cluster Decompositions of Sequences with Distinguished Subsequences
• Analytic combinatorics
• Combinatorial aspects of continued fractions
• Counting occurrences for a finite set of words
• Determination of a class of Poincaré series.
• Dyck paths with peak- and valley-avoiding sets
• Enumeration of pairs of sequences by rises, falls and levels
• Extension of Goulden–Jackson cluster method on pattern occurrences in random sequences and comparison with Régnier–Szpankowski method
• Generalizations of the Goulden–Jackson cluster method
• Lattice path enumeration
• The Goulden-Jackson cluster method for cyclic words
• The Goulden—Jackson cluster method: extensions, applications and implementations
• The symbolic Goulden-Jackson cluster method
• The umbral transfer-matrix method. V: The Goulden-Jackson cluster method for infinitely many mistakes

Cited in

(8)

• Generalizations of the Goulden–Jackson cluster method
• A lifting of the Goulden-Jackson cluster method to the Malvenuto-Reutenauer algebra
• Extension of Goulden–Jackson cluster method on pattern occurrences in random sequences and comparison with Régnier–Szpankowski method
• An application of the Goulden-Jackson cluster theorem
• The symbolic Goulden-Jackson cluster method
• Enumerating symmetric and asymmetric peaks in Dyck paths
• The Goulden-Jackson cluster method for cyclic words
• Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata

Describes a project that uses

Uses Software

• GJsqfree
• GJSAW
• GJseries
• SPGJ
• SYMGJ
• BLANKS
• JODO
• DAVID_IAN
• NAIVE
• CGJ
• SiPerUGJ
• SymUGJ
• UGJ
• OEIS

This page was built for publication: A generalized Goulden-Jackson cluster method and lattice path enumeration

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