Counting words with Laguerre polynomials

Abstract

We develop a method for counting words subject to various restrictions by finding a combinatorial interpretation for a product of formal sums of Laguerre polynomials. We use this method to find the generating function for $k$-ary words avoiding any vincular pattern that has only ones. We also give generating functions for $k$-ary words cyclically avoiding vincular patterns with only ones whose runs of ones between dashes are all of equal length, as well as the analogous results for compositions.

Keywords

• laguerre polynomial
• orthogonal polynomial
• combinatorics on words
• vincular pattern
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]