An application of the Goulden-Jackson cluster theorem

DOI10.5802/ALCO.210zbMATH Open1504.05012arXiv2011.03171OpenAlexW3105950866MaRDI QIDQ2109221FDOQ2109221

Authors: Ira M. Gessel 

Publication date: 20 December 2022

Published in: Algebraic Combinatorics (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

forbidden subwordsGoulden-Jackson cluster theoremMöbius function

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (3)

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

Uses Software

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

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)