An application of the Goulden-Jackson cluster theorem

DOI10.5802/ALCO.210MaRDI QIDQ2109221zbMATH OpenOpenAlexFDO

Authors Ira M. Gessel

Publication date 20 December 2022

Published in Algebraic Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

forbidden subwordsGoulden-Jackson cluster theoremMöbius function

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15)

Abstract: Let A be an alphabet and let F be a set of words with letters in A. We show that the sum of all words with letters in A with no consecutive subwords in F, as a formal power series in noncommuting variables, is the reciprocal of a series with all coefficients 0, 1 or -1. We also explain how this result is related to a result of Curtis Greene on lattices with M"obius function 0, 1, or -1.

Recommendations

• Generalizations of the Goulden–Jackson cluster method
• The Goulden-Jackson cluster method for cyclic words
• The symbolic Goulden-Jackson cluster method
• A generalized Goulden-Jackson cluster method and lattice path enumeration
• The umbral transfer-matrix method. V: The Goulden-Jackson cluster method for infinitely many mistakes

Cites work

• scientific article; zbMATH DE number 3821741 (Why is no real title available?)
• A class of lattices with Möbius function \(\pm 1,0\)
• A generalized Goulden-Jackson cluster method and lattice path enumeration
• A lifting of the Goulden-Jackson cluster method to the Malvenuto-Reutenauer algebra
• An Inversion Theorem for Cluster Decompositions of Sequences with Distinguished Subsequences
• Counting occurrences for a finite set of words
• Determination of a class of Poincaré series.
• Enumeration of pairs of sequences by rises, falls and levels
• Finite generation for Hochschild cohomology of Gorenstein monomial algebras
• On the Homology of Associative Algebras
• On the foundations of combinatorial theory I. Theory of M�bius Functions
• Shuffle algebras, homology, and consecutive pattern avoidance
• The Goulden—Jackson cluster method: extensions, applications and implementations

Cited in

(3)

• Generalizations of the Goulden–Jackson cluster method
• The Goulden-Jackson cluster method for cyclic words
• Characteristic polynomials of weighted lattices

Describes a project that uses

Uses Software

• GJsqfree
• GJSAW
• GJseries
• SPGJ
• SYMGJ
• BLANKS
• JODO
• DAVID_IAN
• NAIVE

This page was built for publication: An application of the Goulden-Jackson cluster theorem

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