Using Noonan-Zeilberger Functional Equations to enumerate (in Polynomial Time!) Generalized Wilf classes

Brian NAKAMURA^{1} and Doron ZEILBERGER^{1}

Very Important This article is accompanied by the Maple packages

• http://www.math.rutgers.edu/~zeilberg/tokhniot/P123 ,
• http://www.math.rutgers.edu/~zeilberg/tokhniot/F123 ,
• http://www.math.rutgers.edu/~zeilberg/tokhniot/P1234 ,
• http://www.math.rutgers.edu/~zeilberg/tokhniot/F1234 ,
• http://www.math.rutgers.edu/~zeilberg/tokhniot/P12345 ,
• http://www.math.rutgers.edu/~zeilberg/tokhniot/F12345 ,
• http://www.math.rutgers.edu/~zeilberg/tokhniot/P123456 ,

to be described below. Lots of sample input and output files can be seen at:

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/Gwilf.html  .

Introduction Recall that the reduction of a finite list of k, say, distinct (real) numbers [a_{1}, a_{2}, …, a_{k}] is the unique permutation σ = [σ_{1}, …, σ_{k}], of {1, …, k} such that a_{1} is the σ_{1}-th largest element in the list, a_{2} is the σ_{2}-th largest element in the list, etc. In other words [a_{1}, a_{2}, …, a_{k}] and σ are “orderisomorphic”. For example, the reduction of [6, 3, 8, 2] is [3, 2, 4, 1] and the reduction of [π, γ, e, ϕ] is [4, 1, 3, 2] (ϕ is the Golden Ratio). Given a permutation π = π_{1} … π_{n} and another permutation σ = [σ_{1}, …, σ_{k}] (called a pattern), we denote by N_{σ}(π) the number of instances 1 ≤ i_{1} < … < i_{k} ≤ n such that the reduction of π_{i_{1}} … π_{i_{k}} is σ. For example, if π = 51324 then N_{[1,2,3]}(π) = 2 (because π_{2}π_{3}π_{5} = 134 and π_{2}π_{4}π_{5} = 124 reduce to [1, 2, 3]).

1 Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen

Rd., Piscataway, NJ 08854-8019, USA. [bnaka, zeilberg] at math dot rutgers dot edu , http://www.math.rutgers.edu/~bnaka/ , http://www.math.rutgers.edu/~zeilberg/ .

First Written: Sept. 7, 2012. This version: Oct. 9, 2012. Supported in part by the USA National Science Foundation.

N_{[1,3,2]}(π) = 1 (because π_{2}π_{3}π_{4} = 132 reduces to [1, 3, 2]).

N_{[2,1,3]}(π) = 1 (because π_{3}π_{4}π_{5} = 324 reduces to [2, 1, 3]).

N_{[2,3,1]}(π) = 0 (because none of the 10 length-three subsequences of π reduces to 231).

N_{[3,1,2]}(π) = 5 (because π_{1}π_{2}π_{3} = 513 and π_{1}π_{2}π_{4} = 512 and π_{1}π_{2}π_{5} = 514 and π_{1}π_{3}π_{5} = 534 and π_{1}π_{4}π_{5} = 524 all reduce to [3, 1, 2]) .

N_{[3,2,1]}(π) = 1 (because π_{1}π_{3}π_{4} = 532 reduces to [3, 2, 1]).

Of course the sum of N_{σ}(π) over all k-permutations σ is \binom{n}{k}.

Fixing a pattern σ, the set of permutations π for which N_{σ}(π) = 0 (we say that π avoids σ) is called the Wilf class of σ, and more generally, given a set of patterns S, the set of permutations for which N_{σ}(π) = 0 for all σ ∈ S, is the Wilf class of that set. The first systematic study of enumerating Wilf classes was undertaken in the pioneering paper by Rodica Simion and Frank Schmidt [SiSc].

The general question is extremely difficult (see [Wiki] and [Bo3]) and “explicit” answers are only known for few short patterns (and sets of patterns), the increasing patterns [1, 2, …, k], and a few other West-equivalent to them, giving the same enumeration. For example, even for the pattern [1, 3, 2, 4] (http://oeis.org/A061552) the best known algorithm takes exponential time in n, and it is very possible that that’s the best that one can do.

But for those patterns σ for which we know how to enumerate their Wilf classes, most importantly the increasing patterns [1, …, k], it makes sense to ask the more general question:

Given a pattern σ, and a positive integer r, find a “formula”, or at least a polynomial-time algorithm (thus answering the question in the sense of Herb Wilf[Wil]) that inputs a positive integer n and outputs the number of permutations π of {1, …, n} for which N_{σ}(π) = r. We call such a class a generalized Wilf class.

Ideally, we would like to have, given a pattern σ, an explicit formula, in n and q, for the generating function (S_{n} denotes the set of permutations of {1, …, n})

A_{σ}(q, n) := ∑_{π∈S_{n}} q^{N_{σ}(π)} ,

then, for any fixed r, the sequence of coefficients of q^{r} in A_{σ}(q, n) would give the sequence enumerating permutations with exactly r occurrences of the pattern σ.

In fact, for patterns of length ≤ 2 there are nice answers. Trivially

A_{[1]}(q, n) := n! q^{n} ,

and almost-trivially (or at least classically)

A_{[2,1]}(q, n) := (1) (1 + q) ⋯ (1 + q + … + q^{n−1}) = [n]! ,

the famous “q-analog” of n!. But things start to get complicated for patterns of length 3.

Past Work

For a very lucid and extremely engaging introduction to the subject, as well as the state-of-the-art, we strongly recommend Miklós Bóna’s masterpiece [Bo3].

In [NZ], John Noonan and the second-named author initiated a functional equations-based approach for enumerating generalized Wilf classes. In order to illustrate it, they reproved John Noonan’s[N] combinatorially-proved result that the number of permutations of length n with exactly one occurrence of the pattern [1, 2, 3] equals \frac{3}{n} \binom{2n}{n−3}. Recently a proof from the book of this result was given by Alexander Burstein[Bu] (see also [Z1]).

In [NZ] it was conjectured that the number of permutations of length n with two occurrences of the pattern [1, 2, 3] equals \frac{59n^{2}+117n+100}{2n(2n−1)(n+5)} \binom{2n}{n−4}. This conjecture was proved by Markus Fulmek[F], using Dyck paths. A very interesting, purely human, approach was developed by David Callan[C] who derived expressions for enumerating permutations of length n with three occurrences and four occurrences.

In [NZ] it was also conjectured that the number of permutations of length n with one occurrence of the pattern [1, 3, 2] equals \frac{n−2}{2n} \binom{2n−2}{n−1}. This conjecture was proved by Miklós Bóna[Bo1], who later proceeded to prove[Bo2] the interesting fact that the sequences enumerating permutations with exactly r occurrences of [1, 3, 2] is P -recursive (i.e. satisfies a homogeneous linear recurrence with polynomial coefficients) for every r. In fact he proved the stronger result that the generating functions are always algebraic. This was vindicated by Toufik Mansour and Alek Vainshtein[MV] who gave an efficient algorithm to actually compute these generating functions, and they used it to find explicit expressions for 1 ≤ r ≤ 5.

Another interesting but different “functional equation” approach, for patterns of length three, was developed by Firro and Mansour[FM].

This Project

But so far, practically nothing is known for patterns of length larger than three and r > 0. In this paper we will modify the approach of [NZ] in order to generate, in polynomial time, such sequences for increasing patterns of any length [1, …, k]. That method can be extended to the patterns [1, …, k − 2, k, k − 1] and possibly other families, but here we will only discuss increasing patterns.

Let us emphasize that the “brute force” approach requires exponential time, since we actually have to construct the set of permutations of length n with the given specifications, and then take the cardinality.

Using the new algorithm to compute sufficiently many terms, we were able to conjecture explicit formulas, in n, for the number of permutations of length n with exactly r occurrences of the pattern [1, 2, 3], for 5 ≤ r ≤ 7, extending Fulmek’s[F] conjectures for r = 3 and r = 4. We believe that the enumeration schemes, that our algorithms generate, should enable our computers to conjecture holonomic representations for the more general quantities (see below), that once guessed, should be amenable to automatic rigorous proving in the holonomic paradigm[Z2], using Christoph Koutschan’s[K] far-reaching extensions and powerful implementations. But since these conjectures are certainly true, and their formal proof would (probably) not yield any new insight, we don’t think that it is worth the trouble to actually carry out the gory details, wasting both humans’ time (it would require quite a bit of daunting programming) and the computers’ time (it would take a very long time, due to the complexity of the schemes).

Now let’s recall the Noonan-Zeilberger Functional Equation Approach.

The Noonan-Zeilberger Functional Equation Approach

The starting point of the Noonan-Zeilberger[NZ] approach for enumerating generalized Wilf classes is to derive a functional equation. Let’s review it with the simplest non-trivial case, that of the length-3 increasing pattern [1, 2, 3].

In addition to the variable q, introduce n extra catalytic variables x_{1}, …, x_{n}, and define the weight of a permutation π = π_{1} … π_{n} of length n by

weight(π) := q^{N_{[1,2,3]}(π)} ∏_{i=1}^{n} x_{i}^{|{1≤a<b≤n;π_{a}=i<π_{b}}|} ,

(as usual, for any set A, |A| denotes the number of elements of A). For example,

weight(12345) = q^{10}x_{1}^{4}x_{2}^{3}x_{3}^{2}x_{4} ,
weight(54321) = 1 ,
weight(21354) = q^{4}x_{2}^{3}x_{1}^{3}x_{3}^{2} = q^{4}x_{1}^{3}x_{2}^{3}x_{3}^{2} .

Let’s define the polynomial in the n + 1 variables

P_{n}(q; x_{1}, …, x_{n}) := ∑_{π∈S_{n}} weight(π) .

Let π = π_{1} … π_{n} be a typical permutation of length n. Suppose π_{1} = i. Note that the number of occurrences of the pattern [1, 2, 3] in π equals the number of occurrences of that pattern in the beheaded permutation π_{2} … π_{n} plus the number of the patterns [1, 2] in the beheaded permutation π_{2} … π_{n} where the “1” is i + 1, or i + 2, or … or n. Let π′ be the reduction to {1, …, n − 1} of that beheaded permutation. We see that

weight(π) = x_{i}^{n−i}weight(π′) |_{x_{i}→qx_{i+1} , x_{i+1}→qx_{i+2}, ... , x_{n−1}→qx_{n}} .

The factor of x_{i}^{n−i} is because converting π′ from a permutation of {1, …, n − 1} to a permutation of {1, …, i−1, i+1, …, n}, and sticking an i at the front introduces n−i new [1, 2] patterns where the “1” is i. This gives the Noonan-Zeilberger Functional Equation

P_{n}(q; x_{1}, …, x_{n}) = ∑_{i=1}^{n} x_{i}^{n−i}P_{n−1}(q; x_{1}, …, x_{i−1}, qx_{i+1}, …, qx_{n}) .  (NZF E1)

Having found P_{n}(q; x_{1}, …, x_{n}), we set the “catalytic” variables x_{1}, …, x_{n} all to 1 and get

f_{n}(q) := A_{[1,2,3]}(q, n) = P_{n}(q; 1, 1, …, 1) .

Even though this is an “exponential-time” (and memory!) algorithm, it is much faster than the direct weighted counting of all the n! permutations, and we were able to explicitly compute them through n = 20.

This is implemented in procedure fn(n,q) in P123. Procedure L20(q); gives the pre-computed sequence of fn(n,q) for n between 1 and 20 .

Here are the first few terms:

f_{1}(q) = 1 , f_{2}(q) = 2 , f_{3}(q) = q + 5 , f_{4}(q) = q^{4} + 3 q^{2} + 6 q + 14 ,

f_{5}(q) = q^{10} + 4 q^{7} + 6 q^{5} + 9 q^{4} + 7 q^{3} + 24 q^{2} + 27 q + 42 ,

f_{6}(q) = q^{20}+5 q^{16}+8 q^{13}+6 q^{12}+6 q^{11}+16 q^{10}+12 q^{9}+24 q^{8}+32 q^{7}+37 q^{6}+54 q^{5}+74 q^{4}+70 q^{3}+133 q^{2}+110 q+132 ,

f_{7}(q) = q^{35}+6 q^{30}+10 q^{26}+10 q^{25}+8 q^{23}+13 q^{22}+30 q^{21}+10 q^{20}+32 q^{19}+18 q^{18}+62 q^{17}+74 q^{16}+24 q^{15}+100 q^{14}

+130 q^{13}+104 q^{12}+162 q^{11}+191 q^{10}+232 q^{9}+260 q^{8}+320 q^{7}+387 q^{6}+395 q^{5}+507 q^{4}+461 q^{3}+635 q^{2}+429 q+429 ,

f_{8}(q) = q^{56} +7 q^{50} +12 q^{45} +15 q^{44} +10 q^{41} +16 q^{40} +40 q^{39} +18 q^{38} +47 q^{36} +38 q^{35} +68 q^{34} +60 q^{33}

+58 q^{32} +66 q^{31} +154 q^{30} +138 q^{29} +115 q^{28} +156 q^{27} +252 q^{26} +324 q^{25} +228 q^{24} +288 q^{23} +537 q^{22}

+466 q^{21} + 546 q^{20} + 656 q^{19} + 682 q^{18} + 1004 q^{17} + 1047 q^{16} + 886 q^{15} + 1494 q^{14} + 1456 q^{13} + 1580 q^{12}

+1818 q^{11}+2077 q^{10}+2182 q^{9}+2389 q^{8}+2544 q^{7}+2864 q^{6}+2570 q^{5}+3008 q^{4}+2528 q^{3}+2807 q^{2}+1638 q+1430 .

For f_{n}(q) for 9 ≤ n ≤ 20 see:

http://www.math.rutgers.edu/~zeilberg/tokhniot/oP123d .

Using this data, the computer easily finds rigorously-proved explicit expressions for the first six moments (about the mean) of the random variable “number of occurrences of the pattern [1, 2, 3]”, and from them verifies that, at least up to the sixth moment, this random variable is asymptotically normal, as humanly proved (for all patterns) by Miklós Bóna[Bo4]. See:

http://www.math.rutgers.edu/~zeilberg/tokhniot/oP123a .

The “Perturbation” Approach

The equations of quantum field theory are (usually) impossible to solve exactly, but physicists got around it by devising clever “approximate” methods using perturbation expansions, that only use the first few terms in a potentially “infinite” (and intractable) series, but that suffice for all practical purposes, using Feynman diagrams.

Of course, we are enumerators, and we want exact results, but suppose we only want to know the sequences enumerating permutations with exactly s occurrences of the pattern [1, 2, 3] for s ≤ r for some relatively small r, rather than for r = \binom{n}{3}, provided by the full

f_{n}(q) = P_{n}(q; 1 [n times]) .

In the original article [NZ], for r = 0, Noonan and Zeilberger simply plugged-in q = 0 and x_{1} = … = x_{n} = 1, getting a simple enumeration scheme, that proved, for the n-th time, the classical result that the number of permutations of length n that avoid the pattern 123 equals the Catalan number (2n)!/(n!(n + 1)!). For r = 1, they differentiated Eq. (NZF E1) with respect to q, using the multivariable calculus chain rule, and then plugged-in q = 0 and x_{1} = … = x_{n} = 1. For r = 2 they did it again, but this turned out to be, for larger r, a Rube Goldberg nightmare, even for a computer.

Here is a much easier way!

Recall that you are really only interested in f_{n}(q) = P_{n}(q; 1 [n times] ). Plugging it into (NZFE1) gives

P_{n}(q; 1 [n times]) = ∑_{i=1}^{n} P_{n−1}(q; 1 [ i − 1 times] , q [ n − i times]) .

This forces us to put-up with expressions of the form

P_{a_{0}+a_{1}}(q; 1 [ a_{0} times] , q [ a_{1} times]) .

Plugging this into (NZF E1) yields

P_{a_{0}+a_{1}}(q; 1 [ a_{0} times] , q [ a_{1} times]) = ∑_{i=1}^{a_{0}} P_{a_{0}+a_{1}−1}(q; 1 [ i−1 times] , q [ a_{0}−i times] , q^{2}[a_{1} times])

+ ∑_{i=1}^{a_{1}} q^{a_{1}−i}P_{a_{0}+a_{1}−1}(q; 1 [ a_{0} times] , q [ i − 1 times] , q^{2} [ a_{1} − i times]) .

This forces us, in turn, to consider expressions of the form

P_{a_{0}+a_{1}+a_{2}}(q; 1 [ a_{0} times] , q [ a_{1} times] , q^{2} [ a_{2} times]),

that would force us to further consider expressions of the form

P_{a_{0}+a_{1}+a_{2}+a_{3}}(q; 1 [ a_{0} times] , q [ a_{1} times] , q^{2} [ a_{2} times] , q^{3} [ a_{3} times]) ,

etc. etc., leading to an exponential explosion in both time and memory. But, if we are only interested in the first r coefficients of f_{n}(q), then we can take advantage of the crucial lemma, that follows immediately from the definition of the weight. Crucial Lemma: For s > r + 1, the coefficients of q^{0}, q^{1}, …, q^{r} of

P_{a_{0}+a_{1}+...+a_{s}}(q; 1 [ a_{0} times] , … q^{s−1} , [ a_{s−1} times] , q^{s} [ a_{s} times])

− P_{a_{0}+a_{1}+...+a_{s}}(q; 1 [ a_{0} times] , …, q^{r} [a_{r} times] , q^{r+1} [ a_{r+1} + a_{r+2} + … + a_{s} times])

all vanish. Let n := a_{1} + … + a_{r} + a_{r+1}. For any expression R and positive integer k, let R$k, denote R … R[k times] for example q^{2}$3 means q^{2}, q^{2}, q^{2}. Also, for any polynomial p(q) in q, let p^{(r)}(q) denote the polynomial of degree r obtained by ignoring all powers of q larger than r, and let CHOP_{r}[ p(q) ] := p^{(r)}(q). Eq. (NZF E1) becomes

P_{n}^{(r)}(q; 1$a_{0} , q$a_{1} , …, q^{r}$a_{r}, q^{r+1}$a_{r+1})

= CHOP_{r} [ ∑_{i=1}^{a_{0}} P_{n−1}^{(r)}(q; 1$(i − 1) , q$(a_{0} − i) , q^{2}$a_{1} , …, q^{r}$a_{r−1} , q^{r+1}$(a_{r} + a_{r+1}))

+ ∑_{i=1}^{a_{1}} q^{a_{1}−i+a_{2}+...+a_{r+1}}P_{n−1}^{(r)}(q; 1$a_{0} , q$(i − 1) , q^{2}$(a_{1} − i) , …, q^{r}$a_{r−1} , q^{r+1}$(a_{r} + a_{r+1}))

+ ∑_{i=1}^{a_{2}} q^{2(a_{2}−i+a_{3}+...+a_{r+1})}P_{n−1}^{(r)}(q; 1$a_{0} , q$a_{1} , q^{2}$(i−1), q^{3}$(a_{2}−i) , …, q^{r}$a_{r−1} , q^{r+1}$(a_{r}+a_{r+1}))

+ . . . . . . . . .

+ ∑_{i=1}^{a_{r+1}} q^{(r+1)(a_{r+1}−i)}P_{n−1}^{(r)}(q; 1$a_{0} , q$a_{1} , q^{2}$a_{2} …, q^{r}$a_{r} , q^{r+1}$(a_{r+1} − 1)) ] .

Now note that, because of the CHOP_{r} operator in front, many terms automatically disappear, because of the powers of q in front. The bottom line is that the computer can automatically generate a scheme for computing the degree-r polynomials in q,

F_{r}(a_{0}, …, a_{r+1})(q) := P_{a_{0}+...+a_{r+1}}^{(r)}(q; 1 [ a_{0} times] , q [ a_{1} times] , …, q^{r+1} [ a_{r+1} times]) ,

with a_{0} +…+a_{r+1} = n and a_{0}, …, a_{r+1} ≥ 0. The number of such quantities is the coefficient of z^{n} in 1/(1 − z)^{r+2} that equals (−1)^{r+2}\binom{−(r+2)}{n} = \binom{r+n+1}{r+1} terms. So each iteration involves O(n^{r+1}) evaluations and hence O(n^{r+2}) additions and doing it n times yields an O(n^{r+3}) algorithm for finding our object of desire, the degree r polynomial in q:

f_{n}^{(r)}(q) = F_{r}(n , 0 [ r + 1 times])(q) .

Having found the scheme, the very same computer (or a different one), may use it to generate as many terms as desired.

The Maple package P123

The Maple package P123 downloadable from

http://www.math.rutgers.edu/~zeilberg/tokhniot/P123 ,

implements the functional equation (NZF E1) and easily generated the first 25 terms of the enumerating sequences for 0 ≤ r ≤ 7. With this data, it empirically verified the already-known results for the number of permutations with exactly r occurrences of the pattern [1, 2, 3] for 0 ≤ r ≤ 4 (due to Noonan[N] (r = 1), Fulmek[F] (r = 2), and Callan[C] (r = 3, 4), and made conjectures for 5 ≤ r ≤ 7 as follows. Let a_{r}(n) be the number of permutations of length n with exactly r occurrences of the pattern [1, 2, 3].

a_{0}(n) = 2 \frac{(2 n − 1)!}{(n − 1)! (n + 1)!} .

a_{1}(n) = 6 \frac{(2 n − 1)!}{(n − 3)! (n + 3)!} .

a_{2}(n) = \frac{(2 n − 2)!}{(n − 4)! (n + 5)!} · (59 n^{2} + 117 n + 100) .

a_{3}(n) = \frac{(2 n − 3)!}{(n − 5)! (n + 7)!} · 4 n (113 n^{3} + 506 n^{2} + 937 n + 1804) .

a_{4}(n) = \frac{(2n − 4)!}{(n − 4)!(n + 9)!} ·

(3561 n^{8} + 3126 n^{7} − 46806 n^{6} + 12384 n^{5} − 659091 n^{4} + 2630634 n^{3} + 5520576 n^{2} + 26283456 n − 39191040) .

a_{5}(n) = \frac{(2n − 5)!}{(n − 5)!(n + 11)!} ·

( 26246 n^{10} + 136646 n^{9} − 115872 n^{8} + 22524 n^{7} − 9648450 n^{6} + 71304534 n^{5}

+381205612 n^{4} + 1607633896 n^{3} + 2800103664 n^{2} + 3611692800 n − 32891443200) .

a_{6}(n) = \frac{(2n − 6)!}{(n − 6)!(n + 13)!}·

( 193311 n^{12} + 2349954 n^{11} + 13035003 n^{10} + 95151030 n^{9} + 406430793 n^{8} + 2889552582 n^{7}

+14335663329 n^{6} + 60005854890 n^{5} + 313010684796 n^{4} + 1025692693464 n^{3}

+1283595375168 n^{2} − 6909513045120 n − 28177269120000 ) .

a_{7}(n) = \frac{(2n − 7)!}{(n − 5)!(n + 15)!}·

( 1386032 n^{16} + 13111080 n^{15} + 22526480 n^{14} + 355187760 n^{13} − 1654450096 n^{12} + 10534951680 n^{11}

+15797223760 n^{10} − 305671694640 n^{9} + 3750695521216 n^{8} − 26631101348520 n^{7}
−86395090065440 n^{6} − 636425872408320 n^{5} + 3647384624274048 n^{4}

+11386434230674560 n^{3}+103032675524966400 n^{2}−157858417817856000 n−763734137886720000 ) .

Enumerating Permutations with r occurrences of the pattern [1,2,3,4] for small r via a Noonan-Zeilberger Functional Equation

In addition to the variable q, we now introduce 2n extra catalytic variables x_{1}, …, x_{n}, and y_{1}, …, y_{n}, and define the weight of a permutation π = π_{1} … π_{n} of length n by

weight(π) := q^{N_{[1,2,3,4]}(π)} ∏_{i=1}^{n} x_{i}^{|{1≤a<b<c≤n; π_{a}=i<π_{b}<π_{c}}|} · y_{i}^{|{1≤a<b≤n; π_{a}=i<π_{b}}|} .

For example,

weight([1, 2, 3, 4, 5, 6]) = q^{15}x_{1}^{10}x_{2}^{6}x_{3}^{3}x_{4}y_{1}^{5}y_{2}^{4}y_{3}^{3}y_{4}^{2}y_{5} ,
weight([6, 5, 4, 3, 2, 1]) = 1 ,
weight([3, 4, 5, 6, 1]) = qx_{3}^{3}x_{4}y_{3}^{3}y_{4}^{2}y_{5} .

Let us define the polynomial in the 2n + 1 variables

P_{n}(q; x_{1}, …, x_{n}; y_{1}, …, y_{n}) := ∑_{π∈S_{n}} weight(π) .

Let π = π_{1} …, π_{n} be a typical permutation of length n. Suppose π_{1} = i. Note that the number of occurrences of the pattern [1, 2, 3, 4] in π equals the number of occurrences of that pattern in the beheaded permutation π_{2} … π_{n} plus the number of the patterns [1, 2, 3] in the beheaded permutation π_{2} … π_{n} where the “1” is i + 1, or i + 2, or … or n. Let π′ be the reduction to {1, …, n − 1} of that beheaded permutation. Also note that the number of occurrences of the pattern [1, 2, 3] where the “1” is an i gets increased by the number of occurrences of the pattern [1, 2] in the beheaded permutation, where the “1” is a j with j > i. We see that

weight(π) = y_{i}^{n−i}weight(π′) |_{x_{i}→qx_{i+1} , x_{i+1}→qx_{i+2}, ... , x_{n−1}→qx_{n} ; y_{i}→x_{i}y_{i+1} , y_{i+1}→x_{i}y_{i+2}, ... , y_{n−1}→x_{i}y_{n}} .

The factor of y_{i}^{n−i} is because converting π′ from a permutation of {1, …, n − 1} to a permutation of {1, …, i−1, i+1, …, n}, and sticking an i at the front introduces n−i new [1, 2] patterns where the “1” is i. This gives the Noonan-Zeilberger Functional Equation for the pattern [1, 2, 3, 4]:

P_{n}(q; x_{1}, …, x_{n}; y_{1}, …, y_{n}) = ∑_{i=1}^{n} y_{i}^{n−i}P_{n−1}(q; x_{1}, …, x_{i−1}, qx_{i+1}, …, qx_{n}; y_{1}, …, y_{i−1}, x_{i}y_{i+1}, …, x_{i}y_{n}) .

(NZF E2)

Having found P_{n}(q; x_{1}, …, x_{n}; y_{1}, …, y_{n}), we set the “catalytic” variables x_{1}, …, x_{n} and y_{1}, …, y_{n} all to 1 and get

g_{n}(q) := A_{[1,2,3,4]}(q, n) = P_{n}(q; 1, 1, …, 1 ; 1, 1, …, 1) .

Even though this is an “exponential-time” (and memory!) algorithm, it is still faster than the direct weighted counting of all the n! permutations, and we were able to explicitly compute them through n = 10.

The first few polynomials are

g_{1}(q) = 1 , g_{2}(q) = 2 , g_{3}(q) = 6 , g_{4}(q) = q + 23 ,
g_{5}(q) = q^{5} + 4 q^{2} + 12 q + 103 ,

g_{6}(q) = q^{15} + 5 q^{9} + 8 q^{6} + 12 q^{5} + 6 q^{4} + 10 q^{3} + 63 q^{2} + 102 q + 513 ,

g_{7}(q) = q^{35} + 6 q^{25} + 10 q^{19} + 18 q^{16} + 12 q^{15} + 13 q^{13} + 24 q^{11} + 32 q^{10} + 72 q^{9} + 10 q^{8} + 46 q^{7}

+142 q^{6} + 116 q^{5} + 146 q^{4} + 196 q^{3} + 665 q^{2} + 770 q + 2761 ,

g_{8}(q) = q^{70}+7 q^{55}+12 q^{45}+15 q^{41}+10 q^{39}+8 q^{36}+28 q^{35}+40 q^{32}+41 q^{29}+10 q^{28}+24 q^{27}+44 q^{26}+84 q^{25}

+24 q^{24} + 89 q^{23} + 12 q^{21} + 142 q^{20} + 136 q^{19} + 96 q^{18} + 115 q^{17} + 333 q^{16} + 156 q^{15} + 112 q^{14} + 312 q^{13}

+199 q^{12}+600 q^{11}+573 q^{10}+804 q^{9}+503 q^{8}+885 q^{7}+1782 q^{6}+1204 q^{5}+2148 q^{4}+2477 q^{3}+5982 q^{2}+5545 q+15767 .

For g_{9}(q), g_{10}(q) see: http://www.math.rutgers.edu/~zeilberg/tokhniot/oP1234d.

The obvious analog of the Crucial Lemma still holds, and one can get polynomial time (in n) algorithms, to compute the number of permutations of length n with exactly r occurrences of the pattern [1, 2, 3, 4]. Alas, because we have twice as many catalytic variables, the O(n^{r+3}) becomes O(n^{2r+5}). Nevertheless, we were able to compute the first 70 terms for the case r = 1. Here are the first 23 terms:

0, 0, 0, 1, 12, 102, 770, 5545, 39220, 276144, 1948212, 13817680, 98679990,
710108396, 5150076076, 37641647410, 277202062666, 2056218941678, 15358296210724,
115469557503753, 873561194459596, 6647760790457218, 50871527629923754 .

The rest can be viewed in: http://www.math.rutgers.edu/~zeilberg/tokhniot/oF1234a.

Manuel Kauers has programmed our algorithm in the numeric language C, and used clever programming techniques to extend the table to 200 terms! We thank him dearly for allowing us to post them. These can be viewed here

http://www.math.rutgers.edu/~zeilberg/tokhniot/oF1234bManuelKauers.

The Maple package P1234

Everything is implemented in the Maple package P1234. See the webpage of this article for sample input and output files. The package F1234 is a more efficient implementation for a small number of occurrences r. Typing Seq1(); in the Maple package F1234 would give the first 200 terms, of the enumerating sequence for permutations with exactly one occurrence of the pattern [1, 2, 3, 4]. As mentioned above, these were computed by Manuel Kauers.

Beyond

Of course, the same reasoning applies to any increasing pattern [1, …, k] but we have, in addition to q, (k − 2)n additional catalytic variables. For each specific r this implies a scheme that enables one to compute in “polynomial” time (in n, but of course not in k or r) the desired numbers. For the patterns [1, 2, 3, 4, 5] and [1, 2, 3, 4, 5, 6] (i.e. k = 5 and k = 6) this is implemented in Maple packages P12345 (and its more efficient [for small r] version F12345) and P123456 respectively.

Other Patterns

Even the case of pattern-avoidance, i.e. r = 0, is already extremely difficult in general. As we mentioned above for the pattern [1, 3, 2, 4], there is no known polynomial time algorithm for enumerating permutations that avoid it. In other words the best known algorithm that inputs a positive integer n and outputs the number of permutations of length n that avoid the pattern [1, 3, 2, 4] takes exponentially many steps in n.

The status of the Noonan-Zeilberger Conjecture

The Noonan-Zeilberger conjecture, made in [NZ], asserts that for any pattern, and for any positive integer r, the enumerating sequence of n-permutations with exactly r occurrences of that pattern is always P -recursive, i.e. satisfies a linear recurrence equation with polynomial coefficients in n. While still open, it seems much less likely to be true today than when it was first made almost twenty years ago. Manuel Kauers informed us, using computations modulo the prime 45007, that even 400 terms of the enumerating sequence for permutations with exactly one occurrence of [1, 2, 3, 4] would not suffice to guess a recurrence. In other words, if a recurrence does exist, it would be extremely complicated. On the other hand, for [1, 2, 3, 4]-avoiding permutations, i.e. the case r = 0, there is a simple second-order recurrence.

Going back to the problem of plain enumeration, for some few infinite families (see [Bo3] and [Wiki]) exact formulas (for the avoiding, r = 0, case) are known, and the present approach would hopefully be able to find polynomial-time schemes for r > 0, at least for some of them. We hope to investigate this in a future paper.

acknowledegement: Many thanks are due to Manuel Kauers for his extensive computations, mentioned above, and to the referee for very helpful remarks that considerably improved the readability of this article.

References

[Bo1] Miklós Bóna, Permutations with one or two 132-subsequences, Discrete Mathematics 175(1997), 55-67.

[Bo2] Miklós Bóna, The Number of Permutations with Exactly r 132-Subsequences Is P-Recursive in the Size!, Adv. Appl. Math. 18 (1997), 510-522.

[Bo3] Miklós Bóna, “Combinatorics of Permutations”, Chapman and Hall. First Edition: 2004. Second Edition, 2012.

[Bo4] Miklós Bóna, The copies of any permutation pattern are asymptotically normal,

http://arxiv.org/abs/0712.2792 (17 Dec. 2007).

[Bu] Alexander Burstein, A short proof for the number of permutations containing pattern 321 exactly once, Electron. J. Combin. 18(2) (2011), #21, (3 pp).

[C] David Callan, A recursive bijective approach to counting permutations containing 3-letter patterns,

http://arxiv.org/abs/math/0211380.

[FM] Ghassan Firro and Toufik Mansour, Three-letter-pattern-avoiding permutations and functional equations, Electron. J. Combin. 13(1) (2006), #51, (14 pp).

[F] Markus Fulmek, Enumeration of permutations containing a prescribed number of occurrences of a pattern of length three, Adv. Appl. Math. 30 (2003), 607-632

[K] Christoph Koutschan. HolonomicFunctions (User’s Guide). Technical report no. 10-01 in RISC Report Series, University of Linz, Austria. January 2010.

http://www.risc.jku.at/publications/download/risc 3934/hf.pdf

[MV] Toufik Mansour and Alek Vainshtein, Counting occurrences of 132 in a permutation, Adv. in Appl. Math. 28(2002), 185-195.

[N] John Noonan, The number of permutations containing exactly one increasing subsequence of length three, Discrete Mathematics 152(1996), 307-313.

[NZ] John Noonan and Doron Zeilberger, The enumeration of permutations with a prescribed number of ‘forbidden’ patterns, Adv. Appl. Math. 17(1996), 381-407. http://www.math.rutgers.edu/˜ zeilberg/mamarim/mamarimhtml/forbid.html

[SiSc] Rodica Simion and Frank W. Schmidt, Restricted permutations, European Journal of Combinatorics 6 (1985), 383-406.

[Wiki] Enumerations of specific permutation classes,

http://en.wikipedia.org/wiki/Enumerations of specific permutation classes

[article initiated by Vince Vatter]

[Wil] Herbert Wilf, What is an answer?, Amer. Math. Monthly 89 (1982), 289-292.

[Z1] Doron Zeilberger, Alexander Burstein’s Lovely Combinatorial Proof of John Noonan’s Beautiful Formula that the number of n-permutations that contain the Pattern 321 Exactly Once Equals (3/n)(2n)!/((n-3)!(n+3)!), Personal Journal of Shalosh B. Ekhad and Doron Zeilberger, Oct. 18, 2011. http://www.math.rutgers.edu/˜ zeilberg/mamarim/mamarimhtml/burstein.html

[Z2] Doron Zeilberger, A Holonomic Systems Approach To Special Functions, J. Computational and Applied Math 32(1990), 321-368. http://www.math.rutgers.edu/˜ zeilberg/mamarim/mamarimhtml/holonomic.html