Consecutive Pattern-Avoidance 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. Our approach also lends itself to the enumeration of permutations, replicating, and giving a new approach to, results in this research area pioneered, in 2003, by Sergi Elizalde and Marc Noy, but it also enables the efficient enumeration, for example, of words in 1^{s} … n^{s}, avoiding the consecutive pattern 1 … r, for any s, and any 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 function 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}) and hence yield many more terms, and, of course, new sequences. 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. 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]), 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 introduces the study of the enumeration of permutations avoiding consecutive patterns. A permutation π = π_{1} … π_{n} avoids a 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 , but in a sense, is more straightforward, and closer in spirit to the original Goulden-Jackson method ([GJ],that is beautifully exposited in [NZ]).

Guessing General Generating Functions in x_{1}, …, x_{n} (for arbitrary n) for Words avoiding a pattern (or set of patterns)

Recall that the original Goulden-Jackson method ([GJ][NZ]) 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 discerte n-variable function

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

the counts the words in 1^{m_{1}} … n^{m_{n}} (there are totally (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}} G(m_{1}, …, m_{n}) x_{1}^{m_{1}} ⋯ x_{n}^{m_{n}} .

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

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

for example if n = 4, so the alphabet if {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 arbitrarily large set of forbidden words, 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}. This is accomplished by the Maple package GJpats.txt available from the webpage of this article. It used the original DavidIan.txt to produce the corresponding generating functions for increasing values for n. For example for words avoiding the consecutive pattern 123 for n = 3

lprint(GFpats([1,2,3],x,3,0)); yields
1/(x[1]*x[2]*x[3]-x[1]-x[2]-x[3]+1) .

This is simple enough. Moving right along

lprint(GFpats([1,2,3],x,4,0)); yields ,
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]-1)
while lprint(GFpats([1,2,3],x,4,0)); yields ,
-1/(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] -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[5]-1) .

It looks like these are 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[] Now you don’t have to be a Ramanujan to conjecture the following Theorem 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_{i}, 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 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, applying the cluster method to a general alphabet. At this time of writing this still has to be done by humans and will be given later.

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})). 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(m − v) − ∑_{v∈V_{r}} f(m − v)

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

+ ∑_{v∈V_{2r+1}} f(m − v) − ∑_{v∈V_{3r}} f(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 for any 0−1 vector v f_{r}(v) only depends on the number of 1’s. 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 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 ≤ 3 ≤ 9, with many terms (using the above recurrences, probably). These are (in order): A049774, A117158, A177523, A177533,

A177553, A230051, A230231.

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.

[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, Rutgers University, May 2008,

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

[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: my239 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 .