Increasing Consecutive Patterns in Words

Mingjia Yang Department of Mathematics

Rutgers University (New Brunswick)

Piscataway, NJ 08854

USA

 my237@math.rutgers.edu

Doron Zeilberger Department of Mathematics

Rutgers University (New Brunswick)

Piscataway, NJ 08854

USA

  DoronZeil@gmail.com

Abstract

We show how to enumerate words in 1^{m_{1}} ⋯ n^{m_{n}} that avoid the increasing consecutive pattern 12 ⋯ r for any r ≥ 2. Our approach yields 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. We also treat the more general case of counting words with a specified number of the pattern of interest (the avoiding case corresponding to zero appearances). This article is accompanied by three Maple packages implementing our algorithms.

1 Introduction

Simion and Wilf initiated the study of enumerating classical pattern-avoidance. This is a very dynamic area with its own annual conference.

Recall that a permutation π = π_{1} ⋯ π_{n} avoids a pattern σ = σ_{1} ⋯ σ_{k} if none of the \binom{n}{k} length-k subsequences of π, reduces to σ.

Burstein [2], in a 1998 PhD thesis, under the direction of Wilf, pioneered the enumeration of words avoiding a set of patterns. This field is also fairly active today, with notable contributions by, inter alia, Mansour [3] and Pudwell [12].

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 Elizalde and Noy, in a seminal paper [5], 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 consecutive subwords, π_{i}π_{i+1} ⋯ π_{i+k−1} of π, reduces to σ.

Algorithmic approaches to the enumeration of permutations avoiding sets of consecutive patterns were given by Nakamura, Baxter, and Zeilberger [10, 1]. 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 cluster method, but in a sense, is more straightforward, and closer in spirit to the original Goulden-Jackson cluster method ([8], that is beautifully exposited (and extended!) in [11]).

In this article we will consider consecutive patterns of the form 1 ⋯ r, i.e. increasing consecutive patterns, and show how to count words in 1^{m_{1}} ⋯ n^{m_{n}} avoiding the pattern 1 ⋯ r (Theorem 1, that is due to Ira Gessel [6]). Throughout this article we will only consider consecutive patterns, so the word “consecutive” may be omitted. In particular, we will look at how to efficiently 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. 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.

In the last part of the paper, we will provide a new proof of Theorem 1 by tweaking the Goulden-Jackson cluster method. Using this proof, along with a little more effort, we will generalize Theorem 1 to counting words with a specified number of the pattern 12 ⋯ r (Theorem 3), instead of just avoiding, that is, having zero occurrence of the pattern of interest.

We close this introduction by mentioning the pioneering work of Mendes and Remmel [9], 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/icpw.html .

These are

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

• ICPWt.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.

2 Method, experimentation, and results

2.1 The Goulden-Jackson cluster method

Recall that the original Goulden-Jackson method [8, 11] 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 us call it F (x_{1}, …, x_{n}), that is the multivariable 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 [11], and is freely available from

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

For example, let n = 4, so the alphabet is {1, 2, 3, 4}, and let the set of “bad words” to avoid be {1234, 1432}. 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 Human language reads

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

2.2 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 consecutive patterns, but each pattern, e.g., 123, entails an arbitrarily large set of forbidden consecutive subwords. For example, in this case, the set of forbidden consecutive subwords is

{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. For example for words avoiding the consecutive pattern 123 (alias the word 123), for n = 3,

GFpats({[1, 2, 3]}, x, 3, 0); (the 0 stands for having zero occurrences of (i.e., avoiding) the pattern of interest) yields

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

This is simple enough. Moving right along, 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 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 do not 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 us 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 were safe in formulating the following theorem that we discovered using the present experimental mathematics approach. After the first version of this article was posted, we found out, thanks to Justin Troyka, that this theorem is due to Ira Gessel [6, p. 51].

Theorem 1. (Gessel [6]) For n ≥ 1, r ≥ 2, the generating function for words in {1, 2, …, n} avoiding the consecutive pattern 12 ⋯ r, let us 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, if Gessel did not prove it before us, these would have been “only” guesses, but once known, humans can prove them. We did it by tweaking the cluster method to apply to an arbitrarily large alphabet, i.e. where even the size of the alphabet, n, is symbolic. Our proof of Gessel’s theorem will be given at the end of this article.

2.3 Efficient computations

Theorem 1 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) + · · · .

(Readers can check this derivation by multiplying each side of the equation in Theorem 1 by the denominator of the right hand side and then using the fact that F_{r}(x_{1}, …, x_{n}) = ∑_{(m_{1},...,m_{n})∈N^{n}} f_{r}(m_{1}, …, m_{n}) x_{1}^{m_{1}} ⋯ x_{n}^{m_{n}}.)

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!

It follows from the symmetry of the generating function F_{r}(x_{1}, …, x_{n}), that f_{r}(m_{1}, …, m_{n}) is symmetric, hence the above Fundamental Recurrence immediately implies the following recurrence, that enables a very fast computation of the sequences, let us call them a_{r}(n), for the number of permutations of length n that avoid the consecutive pattern 1 ⋯ r.

2.3.1 Fast recurrence for enumerating permutations avoiding the consecutive pattern 1 ⋯ r

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 recurrence goes back to F. N. David and D. Barton [4, p. 157], whose proof used a probabilistic language and an inclusion-exclusion argument that may be viewed as a precursor of the cluster method, applied to the special case of increasing patterns.

Equivalently, we have the following exponential generating function:

∑_{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. These are (in order): \underline{A001212}, \underline{A117158}, \underline{A177523}, \underline{A177533}, \underline{A177553},
\underline{A230051}, \underline{A230231}.

2.3.2 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): \underline{A177555} (15 terms)

• b_{4}(n): \underline{A177558} (15 terms)

• b_{5}(n): \underline{A177564} (14 terms)

• b_{6}(n): \underline{A177574} (14 terms)

• b_{7}(n): \underline{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 cubic 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/oICPW1.txt .

2.3.3 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): \underline{A177596} (Only 10 terms)

• c_{4}(n): \underline{A177599} (Only 10 terms)

• c_{5}(n): \underline{A177605} (Only 10 terms)

• c_{6}(n): \underline{A177615} (Only 9 terms)

• c_{7}(n): \underline{A177635} (Only 9 terms) c_{r}(n) for r > 7 are not yet in the OEIS. We can compute c_{r}(n) in quartic time as follows. If you plug-in f_{r}(3^{n}) into the Fun-

damental 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/oICPW1.txt .

2.3.4 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): \underline{A177637} (8 terms)

• d_{4}(n): \underline{A177640} (8 terms)

• d_{5}(n): \underline{A177646} (8 terms)

• d_{6}(n): \underline{A177656} (8 terms)

• d_{7}(n): \underline{A177676} (8 terms)

d_{r}(n) for r > 7 are not yet in the OEIS.

We can compute d_{r}(n) in quintic 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/oICPW1.txt .

Comment: Ira Gessel kindly informed us that an alternative approach to extracting coefficients from the generating function in Theorem 1 is to use the elegant method described in section 3 of his paper on symmetric functions and P-recursiveness [7].

2.4 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 j consecutive patterns 1 ⋯ r for any j, not just j = 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 if r = 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 certain families of polynomial sequences.

Definition 2. For any integer k ≥ 1 and 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 3. For k ≥ 1, r ≥ 2, the generating function of g_{r}(m; t), let us 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}} .

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})), using the weight “t raised to the power of the number of occurrences of the consecutive pattern 1 ⋯ r”.

Also, let V_{k} be the set of 0 − 1 vectors of length n with k ones. Then we have

g_{r}(m) = ∑_{v∈V_{1}} g_{r}(m − v) + ∑_{k=r}^{n} ∑_{v∈V_{k}} P_{k}^{(r)}(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 ICPWt.txt .

3 Proofs

3.1 Proof of Theorem 1

We will use the general set-up of the Goulden-Jackson cluster method as described in Noonan and Zeilberger’s paper [11], but will be able to make things simpler by taking advantage of the specific structure of our forbidden patterns, which are the increasing patterns 1 ⋯ r. That will 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 Wen’s paper [14].) 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 mark 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 [11] that weight(M) = 1 + weight(M) · (x_{1} + x_{2} + ⋯ + x_{n})+weight(M) · weight(C) where C is the set of all possible clusters. This implies 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) 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 4. 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 Lemma.

Lemma 5. 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}). (Equivalently, 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}+···}.

3.2 Proof of Theorem 3

This proof can be directly generalized from the proof of Theorem 1 based on the ‘t-generalization’ described in Noonan and Zeilberger’s paper [11]. 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) = 1+weight(M)·(x_{1}+x_{2}+⋯+x_{n})+weight(M)·weight(C) 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 Lemma 5 to the following:

Lemma 6. 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})). (Equivalently, 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 Lemma 6 directly generalizes from the proof of Lemma 5. 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 lose 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, Lemma 6 immediately implies that weight(C) = ∑_{k=r}^{n} P_{k}^{(r)}(t)e_{k} 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 3 follows directly.

4 Acknowledgment

Many thanks are due to Sergi Elizalde for help with the references and to Yonah Biers-Ariel for suggestions on the format of the paper. Also many thanks to Justin Troyka for pointing out that “our” Theorem 1 appeared in Ira Gessel’s PhD thesis.

References

[1] A. Baxter, B. Nakamura, and D. 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, Springer, 2013, pp. 121–138.

[2] A. Burstein, Enumeration of words with forbidden patterns, Ph.D. thesis, University of Pennsylvania, 1998.

[3] A. Burstein and T. Mansour, Words restricted by patterns with at most 2 distinct letters, Electron. J. Combin. 9 (2002), #R3.

[4] F. N. Davis and D. E. Barton, Combinatorial Chance, Hafner, New York, 1962.

[5] S. Elizalde and M. Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (2003), 110–125 .

[6] I. M. Gessel, Generating functions and enumeration of sequences, PhD thesis, Massachusetts Institute of Technology, 1977.

[7] I. M. Gessel, Symmetric functions and P-recursiveness, J. Combin. Theory Ser. A 53 (1990), 257–285.

[8] I. Goulden and D. Jackson, An inversion theorem for cluster decomposition of sequences with distinguished subsequences, J. London Math. Soc.(2) 20 (1979), 567–576.

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

[10] B. Nakamura, Computational approaches to consecutive pattern avoidance in permutations, Pure Math. Appl. (PU.M.A.) 22 (2011), 253–268.

[11] J. Noonan and D. Zeilberger, The Goulden-Jackson cluster method: extensions, applications, and implementations, J. Difference Eq. Appl. 5 (1999), 355–377.

[12] L. 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

[13] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org.

[14] X. Wen, The symbolic Goulden-Jackson cluster method, J. Difference Eq. Appl. 11 (2005), 173–179.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 05A05, 05–04. Keywords: permutation, word, consecutive pattern, generating function, efficient computation, Goulden-Jackson cluster method.

(Concerned with sequences:

\underline{A049774}, \underline{A117158}, \underline{A177523}, \underline{A177533}, \underline{A177553}, \underline{A177555}, \underline{A177558}, \underline{A177564}, \underline{A177574}, \underline{A177594}, \underline{A177596}, \underline{A177599}, \underline{A177605}, \underline{A177615}, \underline{A177635}, \underline{A177637}, \underline{A177640}, \underline{A177646}, \underline{A177656}, \underline{A177676}, \underline{A230051}, and \underline{A230231}.)