Given an alphabet X and a relation A on X, an extremely well-studied (but perhaps not thoroughly understood) problem consists of counting words in X whose adjacent letters avoid A. We focus on a class of examples in which the rational generating function has a form with interesting combinatorial ramifications. The talk will explore some of these, including: Nim-type games, Mobius functions, cycle-free posets, alternating forests, and derangements of a multiset.
This is joint work with John Dollhopf and Ian Goulden.