Consecutive Patterns in Words

Mingjia YANG and Doron ZEILBERGER

Abstract. We use an extension of the celebrated Goulden-Jackson Cluster method, aided by symbolic computation, to enumerate words avoiding a given set of consecutive patterns. The special case of permutations was initiated in 2003, by Sergi Elizalde and Marc Noy, who completely solved the case where the pattern to avoid was increasing. Here we show how to extend their results from permutations to words. More specifically, we give an O(n^{s+1}) algorithm to enumerate words in 1^{s} … n^{s}, avoiding the consecutive pattern 1 … r, for any s, and any r. This enables us to supply many more terms to quite a few OEIS sequences, and create new ones. Surprisingly, our approach also provides a simpler proof of the original Elizalde-Noy formula. We also treat the more general case of counting such words with a specified number of appearances of the pattern of interest (the avoiding case corresponding to zero appearances). This article is accompanied by three Maple packages implementing our algorithms.

Introduction.

Rodica Simion and Herbert Wilf initiated the study of enumerating classical pattern-avoidance. This is a very dynamic area with its own annual conference and Wikipedia page ([Wi]). Recall that a permutation π = π_{1} … π_{n} avoids a pattern σ = σ_{1} … σ_{k} if none of the \binom{n}{k} length-k subsequence of π, reduces to σ.

Alex Burstein([Bu]), in a 1998 PhD thesis, under the direction of Herb Wilf, pioneered the enumeration of words avoiding a set of patterns. This field is also fairly active today, with notable contributions by, inter alia, Toufik Mansour (e.g [BuM]) and Lara Pudwell([P]).

The enumeration of permutations avoiding a given (classical) pattern, or a set of patterns, is notoriously difficult, and it is widely believed to be intractable for most patterns, hence it would be nice to have other notions for which the enumeration is more feasible. Such an analog was given, in 2003, by Sergi Elizalde and Marc Noy, in a seminal paper ([EN]), that introduced the study of the enumeration of permutations avoiding consecutive patterns. A permutation π = π_{1} … π_{n} avoids a consecutive pattern σ = σ_{1} … σ_{k} if none of the n − k + 1 length-k factors, π_{i}π_{i+1} … π_{i+k−1} of π, reduces to σ.

Algorithmic approaches to the enumeration of permutations avoiding sets of consecutive patterns were given by Brian Nakamura, Andrew Baxter, and Doron Zeilberger ([Na], [BaNaZ]). Our present approach may be viewed as an extension, from permutations to words, of Nakamura’s paper, who was also inspired by the Goulden-Jackson method, but in a sense, is more straightforward, and closer in spirit to the original Goulden-Jackson method ([GJ],that is beautifully exposited (and extended!) in [NoZ]).

In this article we will focus on consective patterns of the form 1 … r, i.e. increasing patterns, and show how to count words in 1^{s} … n^{s} avoiding the pattern 1 … r. All the sequences for s = 1, and 3 ≤ r ≤ 9 are in the On-Line Encyclopedia of Integer Sequences, with many terms, using the explicit generating functions of Elizalde and Noy. Also, quite a few of theses sequences for s > 1 are already there, but with very few terms. Our implied algorithms are O(n^{s+1}) and hence yield many more terms, and, of course, new sequences.

We close this introduction by mentioning the pioneering work of Anthony Mendes and Jeff Remmel([MR]), in combining the two keywords ‘consecutive patterns’ and ‘words’. We were greatly inspired by their article, but our focus is algorithmic.

Maple Packages: This article is accompanied by three Maple packages available from the webpage:

http://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/cpaw.html .

These are

• CPAW.txt: For fast enumeration of sequences enumerating words avoiding increasing consecutive patterns.

• CPAWt.txt: For fast computation of sequences of weight-enumerators for words according to the number of increasing consecutive patterns (t = 0 reduces to the former case).

• GJpats.txt: For conjecturing generating functions (that still have to be proved by humans).

This page also has links to numerous input and output files. The input files can be modified to generate more data, if desired.

The Goulden-Jackson Cluster Method

Recall that the original Goulden-Jackson method ([GJ][NoZ]) inputs a finite alphabet, A, that may be taken to be {1, ..., n}, and a finite set of ‘bad words’, B.

It outputs a certain rational function, let’s call it F (x_{1}, …, x_{n}), that is the multi-variable generating function, in x_{1}, …, x_{n}, for the discrete n-variable function

f(m_{1}, …, m_{n}) ,

that counts the words in 1^{m_{1}} … n^{m_{n}} (there are altogether (m_{1} + … + m_{n})!/(m_{1}! ⋯ m_{n}!) of them) that never contain, as consecutive subwords (aka factors in linguistics) any member of B. In other words:

F (x_{1}, …, x_{n}) = ∑_{(m_{1},...,m_{n})∈N^{n}} f(m_{1}, …, m_{n}) x_{1}^{m_{1}} ⋯ x_{n}^{m_{n}} .

This is nicely implemented in the Maple package DavidIan.txt, that accompanies [NoZ], and is freely available from

http://sites.math.rutgers.edu/~zeilberg/tokhniot/DavidIan.txt .

For example, if n = 4, so the alphabet is {1, 2, 3, 4} and the set of ‘bad words’ to avoid is {1234, 1432}, then, starting a Maple session, and typing:

read `DavidIan.txt`:  lprint(subs(t=0,GJgf(1,2,3,4,[1,2,3,4],[1,4,3,2],x,t)));

immediately returns

1/(1-x[1]-x[2]-x[3]-x[4]+ 2*x[1]*x[2]*x[3]*x[4]) ,

that in Humanese reads

\frac{1}{1 − x_{1} − x_{2} − x_{3} − x_{4} + 2 x_{1}x_{2}x_{3}x_{4}} .

Enumerating Words Avoiding Consecutive Patterns: Let the Computer Do the Guessing Now we are interested in words in an arbitrarily large alphabet {1, … n} avoiding a set of patterns, but each pattern, e.g. 123, entails an arbitrarily large set of forbidden words. For example, in this case, the \binom{n}{3} members of the set

{i_{1} i_{2} i_{3} | 1 ≤ i_{1} < i_{2} < i_{3} ≤ n} .

We can ask DavidIan.txt to find the generating function for each specific n, and then hope to conjecture a general formula in terms of x_{1}, …, x_{n}, for general (i.e. symbolic) n. This is accomplished by the Maple package GJpats.txt, available from the webpage of this article. It uses the original DavidIan.txt to produce the corresponding generating functions for increasing values for n, and then attempts to conjecture a meta-pattern (npi). For example for words avoiding the consecutive pattern 123 (alias the word 123), for n = 3,

latex(GFpats([1,2,3],x,3,0)); yields

1/(1 − x_{1} − x_{2} − x_{3} + x_{1}x_{2}x_{3}) .

This is simple enough. Moving right along,

latex(GFpats([1,2,3],x,4,0)); yields ,

1/(1 − x_{1} − x_{2} − x_{3} − x_{4} + x_{1}x_{2}x_{3} + x_{1}x_{2}x_{4} + x_{1}x_{3}x_{4} + x_{2}x_{3}x_{4} − x_{1}x_{2}x_{3}x_{4}) ,

while latex(GFpats([1,2,3],x,5,0)); yields

1/(1 − x_{1} − x_{2} − x_{3} − x_{4} − x_{5} + x_{1}x_{2}x_{3} + x_{1}x_{2}x_{4} + x_{1}x_{2}x_{5} + x_{1}x_{3}x_{4} + x_{1}x_{3}x_{5} + x_{1}x_{4}x_{5}+ x_{2}x_{3}x_{4} + x_{2}x_{3}x_{5} + x_{2}x_{4}x_{5} + x_{3}x_{4}x_{5} − x_{1}x_{2}x_{3}x_{4} − x_{1}x_{2}x_{3}x_{5} − x_{1}x_{2}x_{4}x_{5} − x_{1}x_{3}x_{4}x_{5} − x_{2}x_{3}x_{4}x_{5}) .

These look like symmetric functions. Procedure SPtoM(P,x,n,m) expresses a polynomial, P, in the indexed variables x[1], …, x[n] in terms of the monomial symmetric polynomials m_{λ}. Applying this procedure we have

SPtoM(denom(GFpats([1,2,3],x,5,0)),x,5,m); yields
-m[1, 1, 1, 1] + m[1, 1, 1] - m[1] + m[] .
SPtoM(denom(GFpats([1,2,3],x,6,0)),x,6,m); yields
m[1,1,1,1,1,1]-m[1,1,1,1]+m[1,1,1]-m[1]+m[] .
SPtoM(denom(GFpats([1,2,3],x,7,0)),x,7,m); yields

-m[1,1,1,1,1,1,1]+m[1,1,1,1,1,1]-m[1,1,1,1]+m[1,1,1]-m[1]+m[] . You don’t have to be a Ramanujan to conjecture the following result. Fact: The generating function for words in {1, 2, …, n} avoiding the consecutive pattern 123, let’s call it F_{3}(x_{1}, …, x_{n}) is

F_{3}(x_{1}, …, x_{n}) = \frac{1}{1 − e_{1} + e_{3} − e_{4} + e_{6} − e_{7} + e_{9} − e_{10} + …} ,

where e_{i} stands for the elementary symmetric function of degree i in x_{1}, …, x_{n}, i.e. the coefficient of z^{i} in (1 + x_{1} z) … (1 + x_{n} z). (Note that e_{i} = m_{1^{i}}). Doing the analogous guessing for the consecutive patterns 1234 and 12345, a meta-pattern emerges, and we are safe in formulating the following theorem. Theorem 1: For n ≥ 1, r ≥ 2, the generating function for words in {1, 2, …, n} avoiding the consecutive pattern 12 … r, let’s call it F_{r}(x_{1}, …, x_{n}) is

F_{r}(x_{1}, …, x_{n}) = \frac{1}{1 − e_{1} + e_{r} − e_{r+1} + e_{2r} − e_{2r+1} + e_{3r} − e_{3r+1} + …} .

Of course, so far, these are ‘only’ guesses, but once we know them, the human can prove them, by tweaking the cluster method to apply to an arbitrarily large alphabet, i.e. where even the size of the alphabet , n, is symbolic. At this time of writing, this still has to be done by humans and will be given later in this article. Efficient Computations The Theorem immediately implies the following partial recurrence equation for the actual coefficients.

Fundamental Recurrence: Let f_{r}(m) be the number of words in the alphabet {1, …, n} with m_{1} 1-s, m_{2} 2-s, …, m_{n} n-s (where we abbreviate m = (m_{1}, …, m_{n})) that avoid the consecutive pattern 1 … r. Also let V_{i} be the set of 0 − 1 vectors of length n with i ones, then

f_{r}(m) = ∑_{v∈V_{1}} f_{r}(m − v) − ∑_{v∈V_{r}} f_{r}(m − v)

+ ∑_{v∈V_{r+1}} f_{r}(m − v) − ∑_{v∈V_{2r}} f_{r}(m − v)

+ ∑_{v∈V_{2r+1}} f_{r}(m − v) − ∑_{v∈V_{3r}} f_{r}(m − v)

+ ∑_{v∈V_{3r+1}} f_{r}(m − v) − ∑_{v∈V_{4r}} f_{r}(m − v) + ….

Suppose that we want to compute f_{3}(1^{100}), i.e. the number of permutations of length 100 that avoid the consecutive pattern 123. If we use the above recurrence literally, we would need about 2^{100} computations, but there is a shortcut!

Enter Symmetry

It follows from the generating function that f_{r}(m_{1}, …, m_{n}) is symmetric, hence the above fundamental recurrence implies, the following

Fast Recurrence For Enumerating Permutations avoiding the consecutive pattern 1 … r: Let a_{r}(n) be the number of permutations of length n that avoid the consecutive pattern 1 … r, then

a_{r}(n) = na_{r}(n−1)−\binom{n}{r}a_{r}(n−r)+\binom{n}{r + 1}a_{r}(n−r−1)−\binom{n}{2r}a_{r}(n−2r)+\binom{n}{2r + 1}a_{r}(n−2r−1)

−\binom{n}{3r}a_{r}(n − 3r) + \binom{n}{3r + 1}a_{r}(n − 3r − 1) − ….

This follows from the Fundamental Recurrence and the fact that a_{r}(n) = f_{r}(1^{n}), and more generally, f_{r}(1^{a}0^{b}) = a_{r}(a), and symmetry.

This recurrence immediately implies the Elizalde-Noy exponential generating functions

∑_{n=0}^{∞} a_{r}(n)\frac{x^{n}}{n!} = \frac{1}{1 − x + \frac{x^{r}}{r!} − \frac{x^{r+1}}{(r+1)!} + \frac{x^{2r}}{(2r)!} − \frac{x^{2r+1}}{(2r+1)!} + \frac{x^{3r}}{(3r)!} − \frac{x^{3r+1}}{(3r+1)!} + …} .

While this ‘explicit’ (exponential) generating function is ‘nice’, it is more efficient to use the fast recurrence. And indeed, the OEIS has these sequences for 3 ≤ r ≤ 9, with many terms (using (presumably) the Elizalde-Noy generating function). These are (in order): A049774, A117158,

A177523, A177533, A177553, A230051, A230231.

Efficient Computations of Permutations of words with Two Occurrences of each Letter Let b_{r}(n) be the number of words with 2 occurrences of each of 1, 2, …, n avoiding the pattern 1 … r. Quite a few of them are currently (April 17, 2018) in the OEIS, but with relatively few terms

• b_{3}(n): https://oeis.org/A177555 (15 terms)
• b_{4}(n): https://oeis.org/A177558 (15 terms)
• b_{5}(n): https://oeis.org/A177564 (14 terms)
• b_{6}(n): https://oeis.org/A177574 (14 terms)
• b_{7}(n): https://oeis.org/A177594 (14 terms)

b_{r}(n) for r > 7 are not yet (April 17, 2018) in the OEIS. We can compute b_{r}(n) in quadratic time as follows. If you plug-in f_{r}(2^{n}) into the fundamental recurrence, you are forced to consider the more general quantities of the form f_{r}(2^{α}1^{β}). Defining

B_{r}(α, β) = f_{r}(2^{α}1^{β}) ,

and using symmetry, we get the following recurrence for B_{r}(α, β).

B_{r}(α, β) = αB_{r}(α − 1, β + 1) + βB_{r}(α, β − 1)

− ∑_{i_{1}+i_{2}=r} \binom{α}{i_{1}}\binom{β}{i_{2}}B_{r}(α − i_{1}, β − i_{2} + i_{1}) + ∑_{i_{1}+i_{2}=r+1} \binom{α}{i_{1}}\binom{β}{i_{2}}B_{r}(α − i_{1}, β − i_{2} + i_{1})

− ∑_{i_{1}+i_{2}=2r} \binom{α}{i_{1}}\binom{β}{i_{2}}B_{r}(α − i_{1}, β − i_{2} + i_{1}) + ∑_{i_{1}+i_{2}=2r+1} \binom{α}{i_{1}}\binom{β}{i_{2}}B_{r}(α − i_{1}, β − i_{2} + i_{1}) − ….

In particular b_{r}(n) = B_{r}(n, 0). Using this recurrence we (easily!) obtained 80 terms of each of the sequences b_{r}(n) for 3 ≤ r ≤ 9, and could get many more. See the output file

http://sites.math.rutgers.edu/ zeilberg/tokhniot/oCPAW1.txt .

Efficient Computations of Permutations of words with Three Occurrences of each Letter Let c_{r}(n) be the number of words with 3 occurrences of each of 1, 2, …, n avoiding the pattern 1 … r. Quite a few of them are currently (April 17, 2018) in the OEIS, but with relatively few terms

• c_{3}(n): https://oeis.org/A177596 (Only 10 terms)
• c_{4}(n): https://oeis.org/A177599 (Only 10 terms)
• c_{5}(n): https://oeis.org/A177605 (Only 10 terms)
• c_{6}(n): https://oeis.org/A177615 (Only 9 terms)
• c_{7}(n): https://oeis.org/A177635 (Only 9 terms)

c_{r}(n) for r > 7 are not yet in the OEIS. We can compute c_{r}(n) in cubic time as follows. If you plug-in f_{r}(3^{n}) into the fundamental recurrence, you are forced to consider the more general quantities of the form f_{r}(3^{α}2^{β}1^{γ}). Defining

C_{r}(α, β, γ) = f_{r}(3^{α}2^{β}1^{γ}) ,

and using symmetry, we get the following recurrence for C_{r}(α, β, γ).

C_{r}(α, β, γ) = αC_{r}(α − 1, β + 1, γ) + βC_{r}(α, β − 1, γ + 1) + γC_{r}(α, β, γ − 1)

− ∑_{i_{1}+i_{2}+i_{3}=r} \binom{α}{i_{1}}\binom{β}{i_{2}}\binom{γ}{i_{3}}C_{r}(α − i_{1}, β − i_{2} + i_{1}, γ − i_{3} + i_{2})

+ ∑_{i_{1}+i_{2}+i_{3}=r+1} \binom{α}{i_{1}}\binom{β}{i_{2}}\binom{γ}{i_{3}}C_{r}(α − i_{1}, β − i_{2} + i_{1}, γ − i_{3} + i_{2})

− ∑_{i_{1}+i_{2}+i_{3}=2r} \binom{α}{i_{1}}\binom{β}{i_{2}}\binom{γ}{i_{3}}C_{r}(α − i_{1}, β − i_{2} + i_{1}, γ − i_{3} + i_{2})

+ ∑_{i_{1}+i_{2}+i_{3}=2r+1} \binom{α}{i_{1}}\binom{β}{i_{2}}\binom{γ}{i_{3}}C_{r}(α − i_{1}, β − i_{2} + i_{1}, γ − i_{3} + i_{2}) − …

In particular, c_{r}(n) = C_{r}(n, 0, 0). Using this recurrence we (easily!) obtained 40 terms of each of the sequences c_{r}(n) for 3 ≤ r ≤ 9, and could get many more. See the output file

http://sites.math.rutgers.edu/ zeilberg/tokhniot/oCPAW1.txt .

Efficient Computations of Permutations of words with Four Occurrences of each Letter Let d_{r}(n) be the number of words with 4 occurrences of each of 1, 2, …, n avoiding the pattern 1 … r. Quite a few of them are currently (April 17, 2018) in the OEIS, but with relatively few terms.

• d_{3}(n): https://oeis.org/A177637 (8 terms)
• d_{4}(n): https://oeis.org/A177640 (8 terms)
• d_{5}(n): https://oeis.org/A177646 (8 terms)

• d_{6}(n): https://oeis.org/A177656 (8 terms)
• d_{7}(n): https://oeis.org/A177676 (8 terms)

d_{r}(n) for r > 7 are not yet in the OEIS. We can compute d_{r}(n) in quartic time as follows. If you plug-in f_{r}(4^{n}) into the fundamental recurrence, you are forced to consider the more general quantities of the form f_{r}(4^{α}3^{β}2^{γ}1^{δ}). Defining

D_{r}(α, β, γ, δ) = f_{r}(4^{α}3^{β}2^{γ}1^{δ}) ,

and using symmetry, we get the following recurrence for D_{r}(α, β, γ, δ). D_{r}(α, β, γ, δ) = αD_{r}(α−1, β+1, γ, δ)+βD_{r}(α, β−1, γ+1, δ)+γD_{r}(α, β, γ−1, δ+1)+δD_{r}(α, β, γ, δ−1)

− ∑_{i_{1}+i_{2}+i_{3}+i_{4}=r} \binom{α}{i_{1}}\binom{β}{i_{2}}\binom{γ}{i_{3}}\binom{δ}{i_{4}}D_{r}(α − i_{1}, β − i_{2} + i_{1}, γ − i_{3} + i_{2}, δ − i_{4} + i_{3})

+ ∑_{i_{1}+i_{2}+i_{3}+i_{4}=r+1} \binom{α}{i_{1}}\binom{β}{i_{2}}\binom{γ}{i_{3}}\binom{δ}{i_{4}}D_{r}(α − i_{1}, β − i_{2} + i_{1}, γ − i_{3} + i_{2}, δ − i_{4} + i_{3})

− ∑_{i_{1}+i_{2}+i_{3}+i_{4}=2r} \binom{α}{i_{1}}\binom{β}{i_{2}}\binom{γ}{i_{3}}\binom{δ}{i_{4}}D_{r}(α − i_{1}, β − i_{2} + i_{1}, γ − i_{3} + i_{2}, δ − i_{4} + i_{3})

+ ∑_{i_{1}+i_{2}+i_{3}+i_{4}=2r+1} \binom{α}{i_{1}}\binom{β}{i_{2}}\binom{γ}{i_{3}}\binom{δ}{i_{4}}D_{r}(α − i_{1}, β − i_{2} + i_{1}, γ − i_{3} + i_{2}, δ − i_{4} + i_{3}) − …

In particular d_{r}(n) = D_{r}(n, 0, 0, 0). Using this recurrence we (easily!) obtained 20 terms of each of the sequences c_{d}(n) for 3 ≤ r ≤ 9, and could get many more. See the output file

http://sites.math.rutgers.edu/ zeilberg/tokhniot/oCPAW1.txt .

Keeping Track of the Number of Occurrences Above we showed how to enumerate words avoiding the consecutive pattern 1 … r, in other words, the number of words, with a specified number of each letters, with zero such patterns. With a little more effort we can answer the more general question about the number of such words with exactly k consecutive patterns 1 … r for any k, not just k = 0. Let W(m) = W(m_{1}, …, m_{n}) be the set of words in the alphabet 1, …, n with m_{1} 1’s, …, m_{n} n’s (note that the number of elements of W(m) is (m_{1} + … + m_{n})!/(m_{1}! ⋯ m_{n}!)). We are interested in the polynomials in t

g_{r}(m; t) = ∑_{w∈W(m)} t^{α(w)} ,

where α(w) is the number of occurrences of the consecutive pattern 1 … r in the word w. (For example α(831456178) = 3. Note that α(w) = 0 if w avoids the pattern.)

[Also note that g_{r}(m; 0) = f_{r}(m) and g_{r}(m; 1) = (m_{1} + … + m_{n})!/(m_{1}! ⋯ m_{n}!).] Using GJpats.txt we were able to conjecture the following theorem, whose proof will be presented later. We first need to define a certain families of polynomial sequences. Definition: For any integer r ≥ 2, P_{k}^{(r)}(t) is defined as follows. If k < r, then it is 0. If k = r then it is t − 1, and if k > r then

P_{k}^{(r)}(t) = (t − 1) ∑_{i=1}^{r−1} P_{k−i}^{(r)}(t) .

Theorem 2: For k ≥ 1, r ≥ 2, the generating function of g_{r}(m; t), let’s call it G_{r}(x_{1}, …, x_{n}; t), is

G_{r}(x_{1}, …, x_{n}; t) = \frac{1}{1 − e_{1} − ∑_{k=r}^{n} P_{k}^{(r)}(t)e_{k}(x_{1}, …, x_{n})} .

This implies the Fundamental Recurrence For g_{r}: Let g_{r}(m; t) be the weight-enumerator of words in the alphabet {1, …, n} with m_{1} 1-s, m_{2} 2-s, … m_{n} n-s (where we abbreviate m = (m_{1}, …, m_{n})), according to the weight “t raised to the power of the number of occurrences of the consecutive pattern 1 … r”. Also, let V_{i} be the set of 0 − 1 vectors of length n with i ones, then

g_{r}(m) = ∑_{v∈V_{1}} g_{r}(m − v) + ∑_{i=r}^{n} ∑_{v∈V_{i}} P_{i}(t) g_{r}(m − v) .

Analogously to the avoidance case we can get efficient recurrences for the permutations, and words in 1^{s} ⋯ n^{s}, for each s > 1. For each s it is still polynomial time, but things are slower because of the variable t. This is implemented in the Maple package CPAWt.txt . Proofs. Proof of Theorem 1. We will use the general set-up of the Goulden-Jackson cluster method as described in [NoZ], but will be able to makes things simpler by taking advantage of the specific structure of our forbidden patterns, that happen to be the increasing patterns 1 … r. Tha would enable us to use an elegant combinatorial argument, without solving a system of linear equations.

First let us quickly review some basic definitions. (We will not go into the details of the cluster method but readers who wish to see an excellent and concise summary of the cluster method are welcome to refer to the first section of [W].) A marked word is a word with some of its factors (consecutive subwords) marked. We are assuming that all the marks are in the set of bad words B. For example (13212; [1,3]) is a marked word with 132 marked, with [1,3] denoting the location of the mark. A cluster is a marked word where the adjacent marks overlap with each other and all the letters in the underlying word belong to at least one component of the cluster. For example (145632; [1,3],[2,4],[4,6]) is a cluster whereas (145632; [1,3],[4,6]) is not. We let the weight of a marked word w := w_{1}w_{2} … w_{k} be weight(w) := (−1)^{|S|} · ∏_{i=1}^{k} x[w_{i}] where S is the set of marks in w. For example, the weight of the cluster (135632; [1,3],[2,4],[4,6]) is (−1)^{3}x_{1}x_{2}x_{3}^{2}x_{5}x_{6}.

Let M be the set of all marked words in the alphabet {1, .., n}. Recall from [NoZ] that weight(M) = weight(M) · (x_{1} + x_{2} + … + x_{n})+weight(M) · weight(C) + 1 where C is the set of all possible clusters. This implies, according to [NoZ], that the multivariate generating function for words avoiding the consecutive pattern 1 … r (i.e. our target generating function) is equal to weight(M) = \frac{1}{1−e_{1}−weight(C)}. So we only need to figure out weight(C). However, to use the classical Goulden-Jackson cluster method, we would have to solve a system of \binom{n}{r} (the number of bad words) equations (recall that we write C as a summation of C[v]’s where v is a word in B, and for each C[v] there is an equation) and no obvious symmetry argument seems to help. So we will use a slick combinatorial approach.

Notice that since the pattern to be avoided is 12 … r, the clusters can only be of the form

(a_{1} … a_{j}; [1, r], …)

where

1 ≤ a_{1} < a_{2} < … < a_{j} ≤ n .

Therefore weight(C) is a summations of multivariate monomials on x_{1}, x_{2}, .., x_{n} where the exponent of each variable x_{i} is zero or one.

Any fixed monomial in weight(C), it can come from many different clusters. The number of clusters it comes from and the coefficient of the monomial are uniquely determined by the number of variables in the monomial. For example, for r = 3, the monomial x_{1}x_{3}x_{5}x_{6}x_{7} can come from the cluster (13567; [1, 3], [2, 4], [3, 5]) or (13567; [1, 3], [3, 5]). The first cluster contributes weight (−1)^{3}x_{1}x_{3}x_{5}x_{6}x_{7} whereas the second cluster contributes weight (−1)^{2}x_{1}x_{3}x_{5}x_{6}x_{7}. So when summing up, they cancel each other out and there is no monomial x_{1}x_{3}x_{5}x_{6}x_{7} in weight(C). So is the case with any other monomial of degree 5. Therefore, let us focus on the monomial x_{1}x_{2}x_{3} … x_{k} and figure out its coefficient.

Definition: Let coeff(x_{1}x_{2} … x_{k}) (k ≥ 1) be the coefficient of x_{1}x_{2} … x_{k} in weight(C).

It is clear that for k < r, coeff(x_{1}x_{2}x_{3} … x_{k}) = 0 because 12 … k cannot be a cluster (it does not have enough letters to be marked). And when k = r, we have coeff(x_{1}x_{2} … x_{k}) = −1, since there can be only one mark. So let us move on to the case when k > r. We have the following claim.

Claim 1:

For k > r, coeff(x_{1}x_{2} … x_{k}) = − coeff(x_{2}x_{3} … x_{k})− coeff(x_{3}x_{4} … x_{k}) − … − coeff(x_{r}x_{r+1} … x_{k}). (i.e. coeff(x_{1}x_{2} … x_{k}) = − coeff(x_{1}x_{2} … x_{k−1})− coeff(x_{1}x_{2} … x_{k−2})−… − coeff(x_{1}x_{2} … x_{k−r+1}).)

This is because there are (r − 1) ways in which the left-most marked word can ‘interface’ with the one to its immediate right. For example, if the clusters are of the form (1 … k; [1, r], [3, r + 2], …) (that is, the second mark starts at 3), then the contribution will be (−1)· coeff(x_{3}x_{4} … x_{k}). This is simply because of the bijection between the set of clusters in the form of (1 … k; [1, r], [3, r + 2], …) with set of the clusters in the form (3 … k; [3, r + 2], …). By peeling off the first mark [1, r], we just lose a factor of (−1) in the coefficient of our monomial.

Similarly, if the clusters are of the form (1 … k; [1, r], [u, u + r − 1], …) (1 < u ≤ r), then the contribution from this case will be (−1)· coeff(x_{u}x_{u+1} … x_{k}). Note that if k < 2r − 1, there cannot be as many as (r−1) cases. However, in this case, we can make the convention that there are (r−1) places for the second mark because for k < r the coefficient of x_{1}x_{2}x_{3} … x_{k} is 0. So the above formula still holds. For example, for the clusters associated with the word 123456, and r = 4, the first mark has to be 1234, the second mark can only be 2345 or 3456. But, according to the natural convention, the second mark can also start with 4 and be 456, and so, coeff(x_{1}x_{2}x_{3}x_{4}x_{5}x_{6}) = −coeff(x_{2}x_{3}x_{4}x_{5}x_{6})−coeff(x_{3}x_{4}x_{5}x_{6})−coeff(x_{4}x_{5}x_{6})= −coeff(x_{2}x_{3}x_{4}x_{5}x_{6})−coeff(x_{3}x_{4}x_{5}x_{6}).

So we have: coeff(x_{1}x_{2} … x_{r}) = −1; coeff(x_{1}x_{2} … x_{r+1}) = (−1) · (−1) = 1; coeff(x_{1}x_{2} … x_{r+2}) = −coeff(x_{2}x_{3} … x_{r+2}) − coeff(x_{3}x_{4} … x_{r+2}) = −coeff(x_{1}x_{2} … x_{r+1}) − coeff(x_{1}x_{2} … x_{r}) = 0. Continuing this process, it is easy to see that x_{1}x_{2} … x_{mr} (m ≥ 1) has coefficient −1 (so is any other monomial of degree mr ) and x_{1}x_{2} … x_{mr+1} has coefficient 1 (so is any other monomial of degree mr + 1). The monomials with other number of variables all have coefficient 0. From this argument and summing over all clusters, we conclude weight(C) = −e_{r} +e_{r+1} −e_{2r} +e_{2r+1} +… and therefore weight(M) = \frac{1}{1−e_{1}+e_{r}−e_{r+1}+e_{2r}−e_{2r+1}+...}.

Proof of Theorem 2.

This proof can be directly generalized from the proof of Theorem 1 based on the ‘t-generalization’ described in [NoZ]. Again, let the set of marked words on {1, 2, …, n} be M. However, this time we let the weight of a marked word w of length k be weight(w) := (t−1)^{|S|}·∏_{i=1}^{k} x[w_{i}] where S is the set of marks in w. We still have weight(M) = weight(M)·(x_{1}+x_{2}+…+x_{n})+weight(M)·weight(C)+1 and G_{r}(x_{1}, …, x_{n}; t) is equal to weight(M), which is \frac{1}{1−e_{1}−weight(C)}.

The procedure to calculate weight(C) directly follows from the proof of Theorem 1. We simply replace (−1) with (t−1) in various places, because the only difference is that now we assign a different weight to a marked word. For example, we have coeff(x_{1}x_{2} … x_{r}) = t − 1; coeff(x_{1}x_{2} … x_{r+1}) = (t − 1)(t − 1) = (t − 1)^{2}; coeff(x_{1}x_{2} … x_{r+2}) = (t − 1)(coeff(x_{2}x_{3} … x_{r+2}) + coeff(x_{3}x_{4} … x_{r+2})) = (t − 1)((t − 1) + (t − 1)^{2}). Again it is clear that for k < r, coeff(x_{1}x_{2}x_{3} … x_{k}) = 0 and when k = r, coeff(x_{1}x_{2} … x_{k}) = t − 1. For the case when k > r, we generalize Claim 1 to the following:

Claim 2:

For k > r, coeff(x_{1}x_{2} … x_{k}) = (t−1) (coeff(x_{2}x_{3} … x_{k})+ coeff(x_{3}x_{4}...x_{k})+...+ coeff(x_{r}x_{r+1}...x_{k})). (i.e. coeff(x_{1}x_{2}...x_{k}) = (t − 1) (coeff(x_{1}x_{2}...x_{k−1})+ coeff(x_{1}x_{2}...x_{k−2}) + ...+ coeff(x_{1}x_{2}...x_{k−r+1}).)

The proof of Claim 2 directly generalizes from the proof of Claim 1. Now one mark contributes a factor of (t − 1) instead of (−1) to the weight of a marked word. For example, for the clusters associated with the word 123456, and r = 3, the first mark has to be 123, the second mark can be 234 or 345. So coeff(x_{1}x_{2}x_{3}x_{4}x_{5}x_{6}) = (t − 1)(coeff(x_{2}x_{3}x_{4}x_{5}x_{6})+coeff(x_{3}x_{4}x_{5}x_{6})). In general, like in the proof of Theorem 1, if we are interested in keeping track of the number of appearances of the consecutive pattern 12 … r, then there are (r − 1) scenarios of clusters that can give rise to the monomial x_{1}x_{2} … x_{k}, depending on where the second mark is. By peeling off the first mark, now we loose a factor of (t − 1) instead of (−1) in the coefficient of our monomial.

As the coefficients of the monomials of the same length are the same, Claim 2 immediately implies that weight(C) = ∑_{k=r}^{n} P_{k}^{(r)}(t)e_{k}(x_{1}, …, x_{n}) where P_{k}^{(r)}(t) satisfies the recurrence

P_{k}^{(r)}(t) = (t − 1) ∑_{i=1}^{r−1} P_{k−i}^{(r)}(t) .

(In fact P_{k}^{(r)}(t) is just a concise way of writing coeff(x_{1}x_{2} … x_{k}), where the consecutive pattern of interest is 12 … r.) From this Theorem 2 follows directly.

References

[BaNZ] Andrew Baxter, Brian Nakamura, and Doron Zeilberger, Automatic Generation of Theorems and Proofs on Enumerating Consecutive-Wilf classes, in: ”Advances in Combinatorics: Waterloo Workshop in Computer Algebra, W80, May 26-29, 2011” [Volume in honor of Herbert S. Wilf], edited by Ilias Kotsireas and Eugene Zima, 121-138 .

[Bu] Alex Burstein, ”Enumeration of words with forbidden patterns”, Ph.D. thesis, University of Pennsylvania, 1998.

[BuM] Alex Burstein and Toufik Mansour, Words Restricted by Patterns with at Most 2 Distinct Letters, The electronic journal of combinatorics 9(2) (2002), #R3 .

[EN] Sergi Elizalde and Marc Noy, Consecutive patterns in permutations, Advances in Applied Mathematics 30 (2003), 110-125 .

[GJ] Ian Goulden and David Jackson, An inversion theorem for cluster decomposition of sequences with distinguished subsequences, J. London Math. Soc.(2) 20 (1979), 567-576.

[MR] A. Mendes and J.B. Remmel, Permutations and words counted by consecutive patterns, Adv. Appl. Math, 37(2006), 443-480.

[Na] Brian Nakamura, Computational Approaches to Consecutive Pattern Avoidance in Permutations, Pure Math. Appl. (PU.M.A.) 22(2011), 253268.

Also available fromhttps://arxiv.org/abs/1102.2480 .

[NoZ] John Noonan and Doron Zeilberger, The Goulden-Jackson Cluster Method: Extensions, Applications, and Implementations, J. Difference Eq. Appl. 5(1999), 355-377.

http://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/gj.html .

[P] Lara Pudwell, Enumeration schemes for pattern-avoiding words and permutations, Ph.D. thesis, Rutgers University, May 2008,

http://faculty.valpo.edu/lpudwell/papers/pudwell thesis.pdf .

[W] Xiangdong Wen (2005) The symbolic Goulden-Jackson cluster method, Journal of Difference Equations and Applications, 11:2, 173-179, DOI: 10.1080/10236190512331329432

https://doi.org/10.1080/10236190512331329432 .

[Wi] The Wikipedia Foundation, Permutation Pattern [Initiated and largely written by Vince Vatter]

https://en.wikipedia.org/wiki/Permutation pattern .

Mingjia Yang, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: my237 at math dot rutgers dot edu .

Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: DoronZeil at gmail dot com .