A generalized Goulden-Jackson cluster method and lattice path enumeration

DOI10.1016/J.DISC.2017.09.004zbMATH Open1376.05009arXiv1508.02793OpenAlexW2963187226MaRDI QIDQ1685986FDOQ1685986

Authors: Yan Zhuang 

Publication date: 20 December 2017

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

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

Uses Software

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

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)