Browse issues
no. 6
An application of the Goulden–Jackson cluster theorem
Gessel, Ira M.1
1 Department of Mathematics Brandeis University Waltham, MA 02453, USA
Algebraic Combinatorics, Volume 5 (2022) no. 6, pp. 1279-1286.

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 the work of Dotsenko and Khoroshkin on a closely related problem and to a theorem of Curtis Greene on lattices with Möbius function 0, 1, or -1.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.210
Classification: 05A05, 05A15
Keywords: Goulden–Jackson cluster theorem, forbidden subwords, Möbius function

Gessel, Ira M. 1

1 Department of Mathematics Brandeis University Waltham, MA 02453, USA
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{ALCO_2022__5_6_1279_0,
     author = {Gessel, Ira M.},
     title = {An application of the {Goulden{\textendash}Jackson} cluster theorem},
     journal = {Algebraic Combinatorics},
     pages = {1279--1286},
     publisher = {The Combinatorics Consortium},
     volume = {5},
     number = {6},
     year = {2022},
     doi = {10.5802/alco.210},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.210/}
}
TY  - JOUR
AU  - Gessel, Ira M.
TI  - An application of the Goulden–Jackson cluster theorem
JO  - Algebraic Combinatorics
PY  - 2022
SP  - 1279
EP  - 1286
VL  - 5
IS  - 6
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.210/
DO  - 10.5802/alco.210
LA  - en
ID  - ALCO_2022__5_6_1279_0
ER  - 
%0 Journal Article
%A Gessel, Ira M.
%T An application of the Goulden–Jackson cluster theorem
%J Algebraic Combinatorics
%D 2022
%P 1279-1286
%V 5
%N 6
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.210/
%R 10.5802/alco.210
%G en
%F ALCO_2022__5_6_1279_0
Gessel, Ira M. An application of the Goulden–Jackson cluster theorem. Algebraic Combinatorics, Volume 5 (2022) no. 6, pp. 1279-1286. doi : 10.5802/alco.210. https://alco.centre-mersenne.org/articles/10.5802/alco.210/

[1] Anick, David J. On the homology of associative algebras, Trans. Amer. Math. Soc., Volume 296 (1986) no. 2, pp. 641-659 | DOI | MR | Zbl

[2] Bassino, Frédérique; Clément, Julien; Nicodème, Pierre Counting occurrences for a finite set of words: combinatorial methods, ACM Trans. Algorithms, Volume 8 (2012) no. 3, p. Art. 31, 28 pp. | DOI | MR | Zbl

[3] Carlitz, Leonard; Scoville, Richard; Vaughan, Theresa Enumeration of pairs of sequences by rises, falls and levels, Manuscripta Math., Volume 19 (1976) no. 3, pp. 211-243 | DOI | MR | Zbl

[4] Dotsenko, Vladimir; Gélinas, Vincent; Tamaroff, Pedro Finite generation for Hochschild cohomology of Gorenstein monomial algebras (2019) (https://arxiv.org/abs/1909.00487)

[5] Dotsenko, Vladimir; Khoroshkin, Anton Shuffle algebras, homology, and consecutive pattern avoidance, Algebra Number Theory, Volume 7 (2013) no. 3, pp. 673-700 | DOI | MR | Zbl

[6] Fröberg, Ralf Determination of a class of Poincaré series, Math. Scand., Volume 37 (1975) no. 1, pp. 29-39 | DOI | Zbl

[7] Gessel, Ira Martin Generating Functions and Enumeration of Sequences, Ph. D. Thesis, Massachusetts Institute of Technology (1977) | MR

[8] Goulden, Ian P.; Jackson, David M. An inversion theorem for cluster decompositions of sequences with distinguished subsequences, J. London Math. Soc. (2), Volume 20 (1979) no. 3, pp. 567-576 | DOI | MR | Zbl

[9] Goulden, Ian P.; Jackson, David M. Combinatorial Enumeration, John Wiley & Sons, Inc., New York, 1983, xxiv+569 pages | MR | Zbl

[10] Greene, Curtis A class of lattices with Möbius function ±1,0, European J. Combin., Volume 9 (1988) no. 3, pp. 225-240 | DOI | MR | Zbl

[11] Iyudu, Natalie; Vlassopoulos, Ioannis Homologies of monomial operads and algebras (2020) (https://arxiv.org/abs/2008.00985)

[12] Noonan, John; Zeilberger, Doron The Goulden-Jackson cluster method: extensions, applications and implementations, J. Differ. Equations Appl., Volume 5 (1999) no. 4–5, pp. 355-377 | DOI | MR | Zbl

[13] Rota, Gian-Carlo On the foundations of combinatorial theory. I. Theory of Möbius functions, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, Volume 2 (1964), pp. 340-368 | DOI | MR | Zbl

[14] Wang, Chao-Jen Applications of the Goulden-Jackson Cluster Method to Counting Dyck paths by Occurrences of Subwords, Ph. D. Thesis, Brandeis University (2011) | MR

[15] Zhuang, Yan A generalized Goulden-Jackson cluster method and lattice path enumeration, Discrete Math., Volume 341 (2018) no. 2, pp. 358-379 | DOI | MR | Zbl

[16] Zhuang, Yan A lifting of the Goulden–Jackson cluster method to the Malvenuto–Reutenauer algebra, Algebr. Comb., Volume 5 (2022) no. 6, pp. 1391-1425

Cited by Sources: