# Counting words with Laguerre polynomials

Jair Taylor

Department of Mathematics, University of Washington, Seattle, WA, USA

**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.

**Résumé.** Nous développons une méthode pour compter des mots satisfaisants certaines restrictions en établissant une interprétation combinatoire utile d'un produit de sommes formelles de polynômes de Laguerre. Nous utilisons cette méthode pour trouver la série génératrice pour les mots k-aires évitant les motifs vinculars consistant uniquement de uns. Nous présentons en suite les séries génératrices pour les mots k-aires évitant de façon cyclique les motifs vinculars consistant uniquement de uns et dont chaque série de uns entre deux tirets est de la même longueur. Nous présentons aussi les résultats analogues pour les compositions.

**Keywords:** Laguerre polynomial, orthogonal polynomial, combinatorics on words, vincular pattern

## 1 Introduction

Define a factorization of a word W to be an ordered list of words that, when concatenated, give W. Given a set of factoriations A and a weight w, we will define a power series $f_{A,w}(t)$, the associated Laguerre series for A, in terms of the generalized Laguerre polynomials with parameter $\alpha = -1$. The key fact we will use is the rule (Theorem 2.4)

$$f_{A_1*A_2,w}(t) = f_{A_1,w}(t) \cdot f_{A_2,w}(t).$$

Here $A_1$ and $A_2$ are factorizations with disjoint alphabets and * is a combinatorial operation that, roughly speaking, interlaces the factorizations in $A_1$ and $A_2$. For example, if $\phi_1 = (aaa)(a)(a) \in A_1$ and $\phi_2 = (bb)(b)(b)(b) \in A_2$ then $\phi = (aaabb)(babab) \in A_1 * A_2$.

Let $\Phi$ denote the linear operator on $\mathbb{R}[t]$ mapping $t^k$ to $k!$. It has the integral representation $\Phi(f(t)) = \int_0^\infty e^{-t} f(t) dt$. We will show in Proposition 2.3 that $\Phi(f_A(t))$ gives the weight of all words in A, which we define to be factorizations with one or no parts. By applying $\Phi$ to a product of Laguerre series we may count a variety of sets of restricted words, especially when the restrictions are on the length of runs of particular letters. For example, the number of arrangements of the word “WALLAWALLA” with no LLL, AAA or WW as consecutive subwords is

$$\int_0^\infty e^{-t} \left( \frac{1}{24} t^4 - t^2 + t \right)^2 \left( \frac{1}{2} t^2 - t \right) dt = 1584$$
as we will see.

In Section 3, we describe the transformation $T$ that turns certain ordinary generating functions into Laguerre series. The transformation can be described in terms of the Laplace transform, and so can be easily implemented in mathematical software packages. We can use $T$ to determine the Laguerre series for a variety of sets of factorizations $A$, and use them to derive formulas and generating functions to count words that obey various restrictions.

In particular, we use this technique to analyze certain pattern avoidance problems. A vincular, or generalized, pattern is a pattern with dashes such as 13-2. This is a generalization of classical permutation patterns where the dashes are used to indicate that the numbers on either side are not required to be adjacent, but all others are. We will only study patterns that have only ones, such as $111-1-11$, so we define pattern avoidance only in this context. A word $W = s_1 \cdots s_l$, with each $s_i$ in some alphabet $S$, contains a vincular pattern $\tau = 1^{k_1} \cdots 1^{k_n}$ if there is a subsequence of $W$ consisting of $m = k_1 + \cdots + k_n$ identical letters of which the first $k_1$ are consecutive, the next $k_2$ are consecutive, and so on. Formally, we require that there are indices $1 \le i_1 < i_2 < \cdots < i_m \le l$ with $s_{i_1} = \cdots = s_{i_m}$ and $i_{j+1} - i_j = 1$ for $j \ne k_1, k_1 + k_2, \cdots, k_1 + \cdots + k_{n-1}$. Otherwise, we say that $W$ avoids $\tau$. These patterns were first studied by Babson and Steingrímsson (Babson and Steingrímsson, 2000), who showed that many statistics of interest can be classified in terms of vincular patterns. The term vincular itself was coined by Claesson in (Bousquet-Mélou et al., 2010), from the Latin vinculare, to bind. Words avoiding vincular patterns are studied in (Bernini, Ferrari, and Pinzani, 2009; Burstein, 1998; Burstein and Mansour, 2003a; Heubach and Mansour, 2009; Burstein and Mansour, 2003b; Mansour, 2006). In this paper we will study vincular patterns with all ones, such as $\tau = 111-11$. A word avoids this pattern if it does not have five appearances of the same letter in the word, of which the first three and the last two are consecutive. Although such patterns are useless in the context of permutations, where only the pattern 1 can be contained, they are meaningful in the context of general words on the alphabet $\mathbb{N}$ where letters may be repeated.

In Section 4, we give a formula to calculate the generating function for the number of words avoiding any such vincular pattern with only ones. This formula involves the use of the maps $T$ and $\Phi$, but these can be easily calculated. For example, we can use Sage to compute the generating function $\sum_W x^{\text{len}(W)}$ where the sum is taken over all ternary words $W$ avoiding the pattern 11-11, where $\text{len}(W)$ is the length of $W$, the number of letters counting multiplicity:

$$ \frac{6x^7 - 6x^6 + 6x^5 - 2x^4 - 5x^3 + 9x^2 - 5x + 1}{16x^4 - 32x^3 + 24x^2 - 8x + 1} = 1 + 3x + 9x^2 + 27x^3 + 78x^4 + 222x^5 + \dots $$

Finally, we give a cyclic version of this result for the case of patterns $1^m-1^m-\cdots-1^m$, where all runs of ones are the same length. This gives the generating functions for words so that any cyclic permutation of their letters avoids such a pattern. This generalizes a result of Burstein and Wilf (Burstein and Wilf, 1997) who give the generating function for the number of words cyclically avoiding $1^m$.

## Acknowledgments

The author would like to thank Sara Billey, Ira Gessel, Silvia Heubach, Yannick van Huele, Toufik Mansour, Brendan Pawloski, Austin Roberts, Byron Schmuland, William Stein and the reviewers for their extraordinarily helpful support. Without them this paper would still be “floating in platonic heaven”.
## 2 Laguerre series

Define the polynomials $l_k(t)$ by their generating function

$$ \sum_{k=0}^{\infty} l_k(t)x^k = e^{\frac{tx}{1+x}} $$

These polynomials are a form of Laguerre polynomial. Specifically, $l_k(t) = (-1)^k L_k^{(-1)}(t)$ where

$$ L_k^{(\alpha)}(t) = \sum_{i=0}^{k} (-1)^i \binom{k+\alpha}{k-i} \frac{t^i}{i!} $$

defines the generalized Laguerre polynomials. They have been found to have a number of interesting combinatorial properties, beginning with their use by Even and Gillis to count generalized derangements when $\alpha$ is set to 0 in (Even and Gillis, 1976). This was later extended by Foata and Zeilberger who use $\alpha$ to keep track of the number of cycles (Foata and Zeilberger:i, 1988). For our purpose, we may assume $\alpha = -1$.

Define a word $W$ on an alphabet $S$ to be an ordered list $s_1 \cdots s_n$ of letters $s_i \in S$. A subword of $W$ is a word $s_ks_{k+1} \cdots s_{k+m}$. Note that we require the indices in a subword to be consecutive, while some authors do not. A word using letters from the alphabet $[k] = \{1, 2, \dots, k\}$ is called $k$-ary, and a word in which no two adjacent letters are the same is called a Carlitz word, after Leonard Carlitz.

Our work is based on the following remarkable result of Ira Gessel (Gessel, 1989, Section 6), which he found in the context of a generalization of rook theory. We present an unlabeled version.

**Theorem 2.1.** Let $\Phi$ be the linear functional on polynomials in $t$ given by $\Phi(t^n) = n!$. Given nonnegative integers $k_1, \dots, k_m$, the number of Carlitz words on an alphabet of $m$ symbols with the $i$th symbol used $k_i$ times is

$$ \Phi\left(\prod_{i} l_{k_i}(t)\right). $$

For example, in (Blom et al., 1998) the authors consider the “Mississippi Problem”. How many arrangements of the letters in the word “MISSISSIPPI” have no adjacent letters the same? We can use the preceding theorem to calculate this directly. There is one $M$, four $I$'s, four $S$'s, and two $P$'s. So the solution is

$$ \Phi(l_1(t)l_4(t)l_4(t)l_2(t)) = \int_0^\infty e^{-t} \binom{1}{24} \binom{1}{2} \binom{3}{2} e^{-t} dt = 2016. $$

Using Theorem 2.1, it is easy to see combinatorially that

$$ \Phi(l_i(t)l_j(t)) = \begin{cases} 2 & \text{if } i = j \\ 1 & \text{if } |i - j| = 1 \\ 0 & \text{if } |i - j| > 1 \end{cases} \quad (1) $$

and so the polynomials $l_k(t)$ are “almost” orthogonal with respect to $\Phi$.
Note that $l_k(t)$ is a polynomial of degree $k$; so the matrix of $l_k$'s expanded into powers of $t$ is triangular with no zeroes on the diagonal, and so $\{l_k\}_k$ forms a basis of $\mathbb{R}[t]$. It is natural to ask, then, what is the expansion of $l_i(t)l_j(t)$ in this basis? These are known as *linearization coefficients*. The linearization coefficients of general Laguerre polynomials, with $\alpha$ indeterminate, is known (Foata and Zeilberger i, 1988; Zeng, 1992), but we will need a combinatorial interpretation of the case $\alpha = -1$. To give it, we need a few more definitions.

**Definition.** A factorization $\phi$ is a finite, ordered list of nonempty words $(\phi_1) \cdots (\phi_n)$, and $\phi_1, \dots, \phi_n$ are the parts or factors of $\phi$. If the concatenation of these words is a word $W$, we say that $\phi$ is a factorization of $W$. We take the convention that the empty word has exactly one factorization, namely the empty factorization which has no factors. Abusing notation, we identify a word $W$ with the factorization $(W)$ in one part, and the empty word with the empty factorization, writing $\emptyset$ for both. We write $\mathrm{par}(\phi) = n$, the number of factors, and $\mathrm{len}(\phi)$ for the length of $\phi$, that is, the length of the word $W$ when $\phi$ is a factorization of $W$.

For example, $\phi = (\mathrm{MISS})(\mathrm{IS})(\mathrm{IPPI})$ is a factorization of “MISSISSIPPI”, with $\mathrm{par}(\phi) = 3$ and $\mathrm{len}(\phi) = 11$. Frequently, we will be interested in the factorization itself without thinking of it as a factorization of a particular word. Rather, the spaces between the factors should be thought of as slots to be filled with nonempty words.

Denote by $n_{i,j,k}$ the number of factorizations over the alphabet $\{a, b\}$ with $k$ parts and exactly $i$ a's and $j$ b's so that each part is Carlitz. For example, $n_{2,5,3} = 6$: the possibilities are $(bab)(bab)(b)$, $(babab)(b)(b)$ and the different permutations of these sets of factors.

**Lemma 2.2.** We have, for all $i, j \in \mathbb{N}$,

$$l_i(t)l_j(t) = \sum_k n_{i,j,k}l_k(t).$$

*Proof.* Note that if $p(t) = a_0 + a_1t + \dots + a_n t^n$ is a polynomial and $\Phi(t^m p(t)) = 0$ for all $m$, then

$$a_0m! + a_1(m+1)! + \dots + a_n(n+m)! = 0.$$

This is a homogenous linear recurrence relation with constant coefficients for the factorial sequence, which is impossible unless $a_0 = a_1 = \dots = a_n = 0$ since it grows superexponentially. Since $\{l_k(t)\}_k$ forms a basis for $\mathbb{R}[t]$, if $\Phi(p(t))l_k(t) = 0$ for all $k$ then we can still conclude $p(t) = 0$. So it is enough to show that

$$\Phi(l_i(t)l_j(t)l_m(t)) = \phi\left(\sum_k n_{i,j,k}l_k(t)l_m(t)\right).$$

We know that the left hand side counts the number of Carlitz arrangements of $i$ a's, $j$ b's, and $m$ c's, while the right hand side gives the total number of pairs $(\phi, W)$ where $\phi$ is a factorization in $k$ parts with $i$ a's and $j$ b's with each part Carlitz, and $W$ is a Carlitz word with $k$ x's and $m$ c's. There is a simple bijection between these sets. Given such a pair $(\phi, W)$, we can get a Carlitz arrangement of $i$ a's, $j$ b's and $m$ c's by replacing the $i$th $x$ of $W$ with the $i$th part of $\phi$. For example, if $\phi = (ab)(bab)$ and $W = cxcx$, we get the Carlitz word $cabcbab$. This process is reversible: given a Carlitz word on $a, b, c$ we replace the $c$'s by parentheses to make a factorization $\phi$ with only the letters $a$ and $b$, and to get $W$ we replace each
maximal subword that does not contain $c$ by a single $x$, getting a word with only $c$'s and $x$'s. For example, given the word $abcabcab$, we get the pair $W = xcxcx$, and $\phi = (ab)(b)(ab)$. The maximality condition guarantees that $W$ will be Carlitz. $\square$

Let $S$ be an alphabet, not necessarily finite, and let $A$ be any set of factorizations of words on $S$. We say that a word $W$ is an allowed word of $A$ if the factorization of $W$ in one part (or zero for the empty word) is in $A$. We think of $A$ as some set of factorizations on $S$ we are interested in investigating. For example, in the above proof we might have defined $A$ to be those factorizations of words on $S = \{a, b\}$ so that each part is Carlitz.

**Definition.** Let $\phi$ be a factorization of a word $W$ on an alphabet $S$. For $T \subseteq S$ and a word $W$ on $S$, let $\phi|_T$ be the factorization created from $\phi$ whose parts are the maximal subwords in each part of $\phi$ that have only letters in $T$ listed in the same order they appeared in $\phi$. The resulting factorization will have only letters from $T$, with parts of $\phi$ possibly split up into multiple parts of $\phi|_T$. We call $\phi|_T$ the restriction of the factorization to $T$. For example, if $S = \{a, b\}$ and $T = \{a\}$, then the restriction of the factorization $(aabba)(aab)(b)(aaab)$ to $T$ is $\phi|_T = (aa)(a)(aa)(aaa)$. If $\phi$ contains no letters from $T$, we define $\phi|_T$ to be the empty factorization.

**Definition.** Let $A_1$ and $A_2$ be two sets of factorizations so that the alphabets of symbols $S_1, S_2$ used in $A_1$ and $A_2$, respectively, are disjoint. Let $S = S_1 \cup S_2$, and denote by $A_1 * A_2$ the set of factorizations $\phi$ of words on $S$ so that $\phi|_{S_1} \in A_1$ and $\phi|_{S_2} \in A_2$.

Thus the factorizations in $A_1 * A_2$ are obtained by interlacing the parts of factorizations in $A_1$ and $A_2$. The factors of $\phi_1$ and $\phi_2$ must appear in the correct order in $\phi$, but a factor of $\phi$ may be a word that is concatenated from factors that alternate between $\phi_1$ and $\phi_2$. For example, if $(a)(aa)(a) \in A_1$ and $(b)(bb) \in A_2$ then $\phi = (abaa)(abb) \in A_1*A_2$ since its restrictions to $\{a\}$ and $\{b\}$ are $\phi|_{\{a\}} = (a)(aa)(a)$ and $\phi|_{\{b\}} = (b)(bb)$.

It is easy to see that $*$ is associative and commutative. Note also that $A_1, A_2 \subseteq A_1 * A_2$ if $A_1$ and $A_2$ contain the empty factorization. If $\phi \in A_1$, for example, then $\phi|_{S_1} = \phi \in A_1$ and $\phi|_{S_2} = \emptyset \in A_2$ when $S_1, S_2$ are the disjoint alphabets of $A_1, A_2$. The allowed words in $A_1 * A_2$ are often of interest; for example, if we have singleton alphabets $S_i = \{i\}$ for $i = 1, \dots, n$, and $A_i$ consists of those factorizations with all parts having length one, then the factorizations in $A_1 * \dots * A_n$ are those so that each factor is Carlitz, and the words of $A_1 * \dots * A_n$ are exactly the Carlitz words.

**Definition.** Given a set of factorizations $A$ on an alphabet $S$, a weight is a function $w$ from $A$ and all of the restrictions of factorizations in $A$ into a polynomial ring $\mathbb{R}[x_1, x_2, \dots]$ that commutes with restriction in the sense that if $\phi \in A$ and $T \subseteq S$, then $w(\phi) = w(\phi|_T) w(\phi|_{S\setminus T})$.

Note that in particular, if $A = A_1 * A_2$ for some sets of factorizations $A_1, A_2$ then $w$ is also a weight on $A_1$ and $A_2$. Also note that taking $T$ to be empty forces $w(\emptyset) = 1$. Typically we will take the weight $w(\phi)$ to be a monomial $x_1^{n_1(\phi)} x_2^{n_2(\phi)} \cdots x_m^{n_m(\phi)}$ where each $n_i(\phi)$ is a statistic so that $x_i^{n_i(\phi)}$ is multiplicative in the above sense. Examples include the length of $\phi$, $\text{len}(\phi)$; the number of distinct symbols in $\phi$; the number of appearances of a particular symbol; the sum of $\phi$, $\text{sum}(\phi)$, if the symbols in $\phi$ are nonnegative integers; or simply $w = 1$ if we wish to enumerate a finite set. We will write $\text{par}(\phi)$ for the number of parts of $\phi$; but $\text{xpar}(\phi)$ is not a weight.
**Definition.** Let $A$ be a set of factorizations on an alphabet $S$ and $w$ be a weight on $A$. Define the *Laguerre series* of $A$ with respect to $w$ to be the formal power series

$$f_{A,w}(t) = \sum_{\phi \in A} w(\phi) l_{\mathrm{par}(\phi)}(t)$$

when this sum is well-defined as a formal power series. For convenience we will omit the $w$ in the subscript when $w = 1$, writing $f_{A,1}(t)$ as $f_A(t)$.

Note that our definition of Laguerre series uses a different normalization of Laguerre polynomials than the sum

$$\sum_n \lambda_n^{(\alpha)} L_n^{(\alpha)}(t)$$

as defined in, e.g., Pollard (1948); Szász and Yeardley (1948); Weniger (2008).

**Proposition 2.3.** Assume $A$ is a set of factorizations and $w$ is a weight on $A$. Let $\Phi$ be the linear operator so that $\Phi(t^n) = n!$ and $\Phi$ fixes any other variables. Then

$$\Phi(f_{A,w}(t)) = \sum_W w(W)$$

when both sides are defined, where the sum is over allowed words $W \in A$ (factorizations with one or no parts.)

*Proof.* We have

$$\Phi(f_{A,w}(t)) = \sum_{\phi \in A} w(\phi) \Phi(l_{\mathrm{par}(\phi)}(t))$$

and $\Phi(l_{\mathrm{par}(\phi)}(t))$ is 1 when $\phi$ has 0 or 1 part and is 0 otherwise by (1) since $l_0(t) = 1$ and $l_1(t) = t$. $\square$

Now we are ready to state our main theorem on the combinatorial properties of Laguerre series.

**Theorem 2.4.**

1. Let $A_1$ and $A_2$ be disjoint sets of allowed factorizations on a common alphabet $S$, and let $w$ be a weight on $A_1 \cup A_2$. Then

$$f_{A_1 \cup A_2, w}(t) = f_{A_1, w}(t) + f_{A_2, w}(t).$$

2. Let $S_1$ and $S_2$ be disjoint alphabets with sets of allowed factorizations $A_1, A_2$ respectively, and let $w$ be a weight on $A_1 * A_2$ (and hence on $A_1$ and $A_2$.) Then

$$f_{A_1 * A_2, w}(t) = f_{A_1, w}(t) \cdot f_{A_2, w}(t).$$
*Proof.* The proof of the first part is evident from the definition. We will prove the second. By Lemma 2.3,

$$ 
\begin{aligned}
f_{A_1,w}(t) \cdot f_{A_2,w}(t) &= \sum_{\phi_1 \in A_1} \sum_{\phi_2 \in A_2} w(\phi_1)w(\phi_2)l_{\text{par}(\phi_1)}(t)l_{\text{par}(\phi_1)}(t) \\
&= \sum_{\phi_1 \in A_1, \phi_2 \in A_2, k \ge 0} n_{\text{par}(\phi_1), \text{par}(\phi_2), k} w(\phi_1)w(\phi_2)l_k(t).
\end{aligned}
$$

Fix $\phi_1 \in A_1$, $\phi_2 \in A_2$. It is enough to show that $n_{\text{par}(\phi_1),\text{par}(\phi_2),k}$ is the number of factorizations with $k$ parts on $S_1 \cup S_2$ whose restrictions to $S_1$ and $S_2$ are $\phi_1$ and $\phi_2$, respectively. Then each allowed word of $A_1 * A_2$ will then be represented exactly once in the series $f_{A_1,w}(t) \cdot f_{A_2,w}(t)$, giving

$$ f_{A_1*A_2,w}(t) = \sum_{\phi \in A_1*A_2} w(\phi)l_{\text{par}(\phi)} = f_{A_1,w}(t) \cdot f_{A_2,w}(t). $$

For fixed $k$, we will construct a simple bijection from the set of triples $(\phi, \phi_1, \phi_2)$ where $\phi_1, \phi_2$ are factorizations in $A_1, A_2$ respectively and $\phi$ is a factorization on the alphabet $\{a, b\}$ with $\text{par}(\phi_1)$ a's and $\text{par}(\phi_1)$ b's so that each part is Carlitz, and the set of factorizations $\phi_3$ of $A_1 * A_2$ with $k$ parts. Let $\phi_3$ be the factorization created by replacing the $n$th $a$ in $\phi$ with the $n$th part of $\phi_1$, and the $n$th $b$ with the $n$th part of $\phi_2$. Then by construction $\phi_3 \in A_1 * A_2$: its restrictions are $\phi_1$ and $\phi_2$. Furthermore, given an allowed factorization $\phi_3 \in A_1 * A_2$ with $k$ parts so that $\phi_{S_1} = \phi_1, \phi_{S_2} = \phi_2$, we can reconstruct the factorization $\phi$ of a word on $\{a, b\}$ by replacing each subword of a factor of $\phi_3$ that uses only the letters of $S_1$, and is maximal with respect to this condition, by an $a$ and each maximal subword using only letters of $S_2$ by a $b$. For example, if $S_1 = \{1, 2\}$ and $S_2 = \{3, 4\}$, with $\phi_3 = (123, 2213, 34413)$, we get the word $\phi = (ab, ab, bab)$. No part of $\phi$ can have $aa$ or $bb$ by the maximality condition. These two algorithms are inverse to each other, establishing the theorem. $\square$

Inductively, we see that if $A_1, \dots, A_n$ are sets of factorizations on disjoint alphabets and $w$ is a weight on $A_1 * \dots * A_n$, then $f_{A_1 * \dots * A_n, w}(t) = f_{A_1, w}(t) \cdots f_{A_n, w}(t)$.

### 3 Computing Laguerre series

The Laguerre series for a set of factorizations would not be especially useful if it was difficult to compute. Fortunately, there is an efficient method to calculate them in some situations. It may be difficult to find a convenient formula for the coefficients of $l_k(t)$ in a given Laguerre series $f_{A,w}(t)$, but this is not needed to find an expression for $f_{A,w}(t)$. It is enough to find the ordinary generating function. Specifically, we define

$$ g_{A,w}(u) = \sum_{\phi \in A} w(\phi)u^k. $$

If a nice form of $g_{A,w}(u)$ is known, we may obtain the Laguerre series $f_{A,w}(t)$ by applying the linear transformation $T$ that sends $u^k$ to $l_k(t)$. As it happens, $T$ can be easily computed in many situations using the inverse Laplace transform. We have

$$ \mathcal{L}\{l_k(t)\} = \frac{1}{s(1-s)} \left( \frac{1-s}{s} \right)^k $$
for $k \ge 1$, where $\mathcal{L}$ is the Laplace transform; this is easily proved from the formula for $l_k(t)$ in terms of the generalized Laguerre polynomials, the fact that $\mathcal{L}\{t^i\} = \frac{i!}{s^{i+1}}$, and the binomial theorem.

Therefore, if $g_{A,w}(0) = 0$, we have by linearity

$$T\{g_{A,w}(u)\} = f_{A,w}(t) = \mathcal{L}^{-1}\left\{\frac{g_{A,w}\left(\frac{1-s}{s}\right)}{s(1-s)}\right\}$$

when the right-hand side is well-defined. If $g_{A,w}(0) \ne 0$, we can calculate

$$f_{A,w}(t) = T\{g_{A,w}(u) - g_{A,w}(0)\} + g_{A,w}(0) = \mathcal{L}^{-1}\left\{\frac{g_{A,w}\left(\frac{1-s}{s}\right) - g_{A,w}(0)}{s(1-s)}\right\} + g_{A,w}(0)$$

since $l_0(t) = 1$. The use of the inverse Laplace transform here is not central to the theory, but it is convenient since many software packages provide symbolic calculation of the inverse Laplace transform, making it easy to implement the transformation $T$. However, the function $T$ itself should not be thought of as an integral transform as we do not consider questions of convergence.

For example, consider the problem of counting words that have no subword consisting of $m$ identical letters. These are words that avoid the subword pattern $1^m$, and are sometimes called $m$-Carlitz words; when $m = 2$ we have the ordinary Carlitz words. To find the generating function, let $A$ be the set of factorizations on a one-letter alphabet with each part having length smaller than $m$, and again let $w(\phi) = x^{\text{len}(\phi)}$. We see that

$$g_{A,w}(u) = \sum_{n=0}^{\infty} u^n (x + \dots + x^{m-1})^n = \frac{1-x}{1-x-u(x-x^m)}$$

and so we compute

$$f_{A,w}(t) = T\{g_{A,w}(u)\} = \exp\left(t \cdot \frac{x-x^m}{1-x^m}\right). \qquad (2)$$

Taking the coefficient of $x^n$ in (2) gives the Laguerre series for the set of factorizations with length $n$ so that each part is smaller than $m$. This gives a generalization of Theorem 2.1. If $m_1, \dots, m_k, n_1, \dots, n_k$ are nonnegative integers, and $p_{m,n}(t)$ are polynomials defined by $\sum_{n=0}^{\infty} p_{m,n}(t) x^n = \exp\left(\frac{t(x-x^m)}{1-x^m}\right)$, we see that

$$\Phi\left(\prod_{i=1}^{k} p_{m_i, n_i}(t)\right)$$

is the total number of $k$-ary words that use the letter $i$ exactly $n_i$ times and do not contain the subwords $i^{m_i}$. Thus the number of arrangements of the word "WALLAWALLA" with no LLL, AAA or WW as consecutive subwords is

$$\begin{align*}
\int_0^\infty e^{-t} p_{3,4}(t) \cdot p_{3,4}(t) \cdot p_{2,2}(t) dt &= \int_0^\infty e^{-t} \left(\frac{1}{24}t^4 - t^2 + t\right)^2 \cdot \left(\frac{1}{2}t^2 - t\right) dt \\
&= 1584.
\end{align*}$$
Recalling again the formula

$$ \Phi(e^{tf}) = \frac{1}{1-f}, $$

we see that the generating function for the number of k-ary m-Carlitz words of length n is given by

$$ \Phi \left( \exp \left( kt \cdot \frac{x - x^m}{1 - x^m} \right) \right) = \frac{1 - x^m}{1 - kx - (k-1)x^m}. $$

Another derivation of this formula is given by Burstein and Mansour (Burstein and Mansour, 2003a, Example 2.2).

More generally, we might count the number of times the pattern $1^m$ occurs. We define the weight $w(W)$ of a word $W$ to be $x^ny^l$, where $n$ is the length of $W$ and $l$ is the number of times $W$ contains the pattern $1^m$. Letting $A$ be the set of all factorizations on a one-letter alphabet, it is not difficult to compute the generating function $g_{A,w}$. A formula for the generating function for k-ary words by the number of times they avoid a pattern $1^m$ can also be found in Burstein and Mansour (2003a).

# 4 Vincular patterns

We are now ready to state a general formula for k-ary words avoiding vincular patterns with ones. We say that a k-ary factorization $\phi$ contains a vincular pattern $\tau$ with only ones if the word made from $\phi$ by inserting a single 0 between each pair of adjacent factors contains $\tau$, and this copy of $\tau$ does not use 0. Using the transformations $T$ and $\Phi$, we can reduce the problem to finding ordinary generating functions for factorizations that only use one symbol and avoid the given vincular pattern.

**Theorem 4.1.** Let $k_1, \dots, k_n$ be positive integers. Let $w$ be the weight on k-ary words with $w(a_1 \cdots a_l) = x_{a_1}x_{a_2} \cdots x_{a_l}$, so that the power of $x_i$ represents the number of times $i$ appears in $W$, and let $A$ be the set of k-ary words avoiding the pattern $\tau = 1^{k_1-1^{k_2}-\cdots-1^{k_n}}$. Then

$$ \sum_{W \in A} w(W) = \Phi \left( \prod_{i=1}^{k} [e^{tx_i} - T \{G_{\tau}(x_i, u)\}] \right) $$

where $T$ is the operator defined in Section 3, and

$$ G_{\tau}(x, u) = \frac{ux^{k_1}(1-x)}{(1-x-u(x-x^{k_i}))(1-x-ux)} \prod_{i=2}^{n} \left[ x^{k_i} + \frac{ux^{k_i}(1-x^{k_i})}{1-x-u(x-x^{k_i})} \right]. \quad (3) $$

We say that a word $W$ cyclically avoids a vincular pattern $\tau$ if $W$ avoids $\tau$ no matter how its letters are cycled. More formally, let $r$ be the function that cycles $W$, moving the last letter into the first position: $r(a_1 \cdots a_n) = a_na_1 \cdots a_{n-1}$. Then $W$ cyclically avoids $\tau$ if $r^k(W)$ avoids $\tau$ for each $k$.

In order to find the generating function for the number of words cyclically avoiding the pattern $\tau = 1^m-1^m-\cdots-1^m$, we will need a little more information than provided by the generating function $G_{\tau}(x, u)$ defined by (3). Let $H(x, u, v) = g_{A,w}(u)$ where $A$ is the set of factorizations on the alphabet $\{1\}$ avoiding the pattern $\tau$, where $w$ is the weight $w(\phi) = x^{\text{len}(\phi)}u^{\text{par}(\phi)}v^{\text{fst}(\phi)}$ where $\text{fst}(\phi)$ is the size of the first factor of $\phi$. Note that in this case $w$ is trivially a weight by our definition since we are using a singleton alphabet, but generally is not. We will find a closed-form expression for $H(x, u, v)$, although it is rather unwieldy.
**Lemma 4.2.** The generating function $H(x, u, v)$ is given by

$$H(x, u, v) = 1 + \left[ \frac{1-x}{(1-vx)(1-x-ux)} \right] \left[ u(vx - (vx)^{mn}) + \frac{u^2 x^m ((1-vx)(z-(vx)^m)z^{n-1} - (1-(vx)^m)(z^n-(vx)^{mn}))}{(z-(vx)^m)(1-x-u(x-x^m))} \right]$$

where

$$z = x^m + \frac{ux^m(1-x^m)}{1-x-u(x-x^m)}.$$

**Theorem 4.3.** Let A be the set of words cyclically avoiding the pattern $1^m-1^m-\cdots-1^m$, with $n-1$ dashes, and let w be the weight on k-ary words with $w(s_1 \dots s_l) = x_{s_1}x_{s_2}\cdots x_{s_l}$. Then the generating function $\sum_{W \in A} w(W)$ is given by

$$1 + \sum_{i=1}^{k} \Phi \left( t^{-1} \cdot T \left\{ u \frac{d^2}{dv du} \bigg|_{v=1} H(x_i, u, v) \right\} \left( -1 + \prod_{\substack{j=1 \\ j \neq i}}^{k} T\{H(x_j, u, 1)\} \right) \right) + \sum_{i=1}^{k} \frac{x_i - x_i^{mn}}{1-x}.$$

In particular, letting $x_i = x$ for each $i$ gives:

$$\sum_{W \in A} x^{\text{len}(W)} = 1 + k \cdot \Phi \left( t^{-1} \cdot T \left\{ u \frac{d^2}{dv du} \bigg|_{v=1} H(x, u, v) \right\} \left( (T\{H(x, u, 1)\})^{k-1} - 1 \right) \right) + \frac{k(x - x^{mn})}{1-x}.$$

If we set $n=1$, considering k-ary words that cyclically avoid $1^m$, the formula simplifies considerably. After some computation, which we omit here, we arrive at the following.

**Corollary 4.4.** Let A be the set of nonempty k-ary words avoiding $1^m$. As above, let w be the weight $w(a_1 \cdots a_l) = x_{a_1}x_{a_2} \cdots x_{a_l}$. Then

$$\sum_{W \in A} w(W) = \sum_{i=1}^{k} \frac{x_i^{2m} - mx_i^{m+1} + (m-1)x_i^m}{(x_i^m - 1)(x_i - 1)} + \frac{\sum_{i=1}^{k} \frac{(m-1)x_i^{m+1} - mx_i^m + x_i}{(x_i^m - 1)^2}}{1 - \sum_{i=1}^{k} \frac{x_i^m - x_i}{x_i^m - 1}}.$$

In the book by Heubach and Mansour (Heubach and Mansour, 2009), the authors define a cyclic Carlitz composition as a Carlitz composition so that the first and last parts are not equal; they ask (Research Direction 3.3) for the generating function for the number of cyclic Carlitz compositions. If we let $k$ approach infinity, $m=2$, and $x_i = x^i$, we get the following.

**Corollary 4.5.** Let A be the set of cyclic Carlitz compositions. Then

$$\sum_{W \in A} x^{\text{sum}(W)} = \frac{\sum_{i=1}^{\infty} \frac{x^i}{(1+x^i)^2}}{1 - \sum_{i=1}^{\infty} \frac{x^i}{1+x^i}} + \sum_{i=1}^{\infty} \frac{x^{2i}}{1+x^i}.$$

Setting $x_i = x$ in Corollary 4.4 and simplifying gives the following formula.
**Corollary 4.6.** Let A be the set of nonempty k-ary words that cyclically avoid 1^m. Then

$$ \sum_{W \in A} x^{\text{len}(W)} = \frac{1 - x^{m-1}}{1-x} \left( kx + (k-1)x \left( \frac{m - (m-1)kx}{1 - kx + (k-1)x^m} - \frac{m}{1-x^m} \right) \right). $$

This was found by Burstein and Wilf (Burstein and Wilf, 1997). They go on to show that the number of k-ary words of length n cyclically avoiding 1^m is asymptotically β^n, where β is the positive root of x^{m+1} = (k-1)(1 + x + x^2 + ... + x^m); in fact, they extract an explicit formula when n is sufficiently large.

We can also give a cyclic version of Theorem 2.1, which can be derived by extracting the coefficient of a monomial x_1^{n_1} ... x_k^{n_k} in the generating function from Theorem 4.2 for words cyclically avoiding 1^m.

**Corollary 4.7.** Let n_1, ..., n_k be positive integers, and let p_{m,n}(t) be defined as before by Σ_{n=0}^∞ p_{m,n}(t) x^n = exp (t(x-x^m) / (1-x^m)). Then

$$ N \cdot \Phi \left( t^{-1} \cdot \prod_{i=1}^{k} p_{m, n_i}(t) \right) $$

is the total number of k-ary words that use the letter i exactly n_i times and cyclically avoid 1^m, where N = Σ_{i=1}^k n_i is the total number of letters counted with multiplicity.

There are other variations. For example, if we would like to keep track of the length (number of parts) of a composition instead of just the sum, we can replace each x^i in Corollary 5.4 by yx^i, so that the power of y represents the number of parts. Furthermore, if we are interested in only words or compositions whose symbols lie in a given set other than {1, ..., k} or $\mathbb{N}$, then we may sum over that set instead in the above formulas.

# 5 Questions and future directions

There are a number of combinatorial applications of Laguerre series that might be pursued in the future. One direction is to extend the work of Section 4, finding generating functions for words avoiding other cyclic patterns. Another possibility would be to count the number of occurrences of a given pattern of ones, which would amount to finding the appropriate generating function for factorizations on a single-letter alphabet by the number of occurrences of this pattern. One might also look for a combinatorial interpretation of some form of composition of Laguerre series; empirically, it seems that $l_i(l_j(t))$ has nonnegative integer coefficients in the $l_k$-basis for $j > 0$. Finally, it would be useful to develop bijections from sets of words with restrictions to other combinatorial objects that are not obviously described in terms of words, using the methods outlined here to count sets that may be otherwise difficult to enumerate.

# References

E. Babson and E. Steingrímsson. Generalized permutation patterns and a classification of the Mahonian statistics. *Sem. Lothar. Combin.*, 44: Art. B44b:18 pp. (electronic), 2000.

A. Bernini, L. Ferrari, and R. Pinzani. Enumeration of some classes of words avoiding two generalized patterns of length three. *J. Autom. Lang. Comb.*, 14(2):129–147, 2009.
G. Blom, J.-E. Englund, and D. Sandell. The Mississippi problem. *American Statistician*, 52(1):49–50, 1998.

M. Bousquet-Mélou, A. Claesson, M. Dukes, and S. Kitaev. (2+2)-free posets, ascent sequences and pattern avoiding permutations. *Journal of Combinatorial Theory, Series A*, 117(7):884–909, 2010.

A. Burstein. *Enumeration of words with forbidden patterns*. PhD thesis, University of Pennsylvania, 1998.

A. Burstein and T. Mansour. Words restricted by 3-letter generalized multipermutation patterns. *Ann. Combin.*, 7(1):1–12, 2003a.

A. Burstein and T. Mansour. Counting occurrences of some subword patterns. In *Discr. Math. Theor. Compu. Sci.* 6:1, pages 1–11, 2003b.

A. Burstein and H. S. Wilf. On cyclic strings without long constant blocks. *Fibonacci Quart.*, 35(3): 240–247, 1997.

S. Even and J. Gillis. Derangements and Laguerre polynomials. *Mathematical Proceedings of the Cambridge Philosophical Society*, 79(01):135–143, 1976.

D. Foata and D. Zeilberger. I. Laguerre polynomials, weighted derangements, and positivity. *SIAM J. Disc. Math*, pages 425–433, 1988.

I. M. Gessel. Generalized rook polynomials and orthogonal polynomials. In D. Stanton, editor, *q-Series and Partitions*, pages 159–176. Springer-Verlag, New York, 1989.

S. Heubach and T. Mansour. *Combinatorics of Words and Compositions*. CRC Press, 2009.

T. Mansour. Restricted 132-avoiding k-ary words, Chebyshev polynomials, and continued fractions. *Advances in Applied Mathematics*, 36(2):175–193, 2006.

H. Pollard. Representation of an analytic function by a Laguerre series. *Ann. Math.*, 48:358–65, 1948.

O. Szász and N. Yeardley. The representation of an analytic function by general Laguerre series. *Pac. J. Math.*, 8:621–33, 1948.

E. J. Weniger. On the analyticity of Laguerre series. *Journal of Physics A: Mathematical and Theoretical*, 41(42):425207, 2008.

J. Zeng. Weighted derangements and the linearization coefficients of orthogonal Sheffer polynomials. *Proc. London Math. Soc*, 3:65, 1992.