An application of the Goulden-Jackson cluster theorem

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öbius function 0, 1, or -1.

To be published in Algebraic Combinatorics

References in corpus (2)

• A generalized Goulden-Jackson cluster method and lattice path enumeration
• A lifting of the Goulden-Jackson cluster method to the Malvenuto-Reutenauer algebra

Cited by in corpus (1)

• Stationary 1-dependent Counting Processes: from Runs to Bivariate Generating Functions