Lattice Path Enumeration of Permutations with k Occurrences of the Pattern 2–13

Robert Parviainen ARC Centre of Excellence for Mathematics and Statistics of Complex Systems The University of Melbourne 139 Barry Street 3010 Victoria Australia

                   robertp@ms.unimelb.edu.au

Abstract We count the number of permutations with k occurrences of the pattern 2–13 in permutations by lattice path enumeration. We give closed forms for k ≤ 8, extending results of Claesson and Mansour.

1 Introduction

Let S_{n} denote the set of permutations of {1, 2, …, n}. A pattern in a permutation π ∈ S_{n} is a permutation σ ∈ S_{k} and an occurrence of σ as a subword of π; there should exist i_{1} < ⋯ < i_{k} such that π(i_{1}) ⋯ π(i_{k}) is order equivalent to σ. (So π(i_{1}) is the σ(1):th smallest of the subword, and so on.)

For example, an occurrence of the pattern 3–2–1 in π ∈ S_{n} means that there exists 1 ≤ i < j < k ≤ n such that π(i) > π(j) > π(k).

We further consider restricted patterns, introduced by Babson and Steingrímsson [1]. The restriction is that two specified adjacent elements in the pattern must be adjacent in the permutation as well. The position of the restriction in the pattern is indicated by an absence of a dash (–). Thus, an occurrence of the pattern 3–21 in π ∈ S_{n} means that there exists 1 ≤ i < j < n such that π(i) > π(j) > π(j + 1).

Here we are interested in patterns of the type 2–13. We remark that it is shown by Claesson [3] that the occurrences of 2–13 are equidistributed with the occurrences of the pattern 2–31, as well as with 13–2 and with 31–2.

Definition 1. Let ϕ_{k}(n) denote the number of permutations of length n with exactly k occurrences of the pattern 2–13.

Claesson [3] showed that ϕ_{0}(n) is given by the the (n + 1)th Catalan number, \frac{1}{n+1} \binom{2n}{n} (\underline{A000108}^{1}). It was further shown that

ϕ_{1}(n) = \binom{2n}{n − 3} (\underline{A002696}),  (1)
ϕ_{2}(n) = \frac{n}{2}\binom{2n}{n − 4} (\underline{A094218}),  (2)
ϕ_{3}(n) = \frac{(n + 1)(n + 2)}{6}\binom{2n}{n − 5} (\underline{A094219}).  (3)

The authors commented that “… [the above result] obviously is in need of a combinatorial proof,” referring in particular to Equation 1.

In this paper we give such a combinatorial proof of all the above results, as well as formulae for ϕ_{4}(n), …, ϕ_{8}(n). We show how to count occurrences of 2–13 in permutations via lattice paths; bi-coloured Motzkin paths to be precise.

Definition 2. A Motzkin path of length n is a sequence of vertices p = (v_{0}, v_{1}, …, v_{n}), with v_{i} ∈ ℕ^{2} (where ℕ = {0, 1, … }), with steps v_{i+1} − v_{i} ∈ {(1, 1), (1, −1), (1, 0)} and v_{0} = (0, 0) and v_{n} = (n, 0).

A bicoloured Motzkin path is a Motzkin path in which each east, (1, 0), step is labelled by one of two colours. We say that the path is q-weighted if the weight of steps ending at height h is given by [h]_{q} := ∑_{k=0}^{h−1} q^{k}.

We will use N (S) to denote a north, (1, 1), step (resp., south, (1, −1), step), and E and F to denote the two different coloured east steps.

1.1 Main Theorem

Theorem 3. The number of permutations of length m + 1 with exactly n occurrences of the pattern 2–13 is given by the coefficient of q^{n}t^{m} in the generating function for q-weighted bi-coloured Motzkin paths.

Remark 4. It follows from a result of Brak, et al., [2], that the number of permutations of length m + 1 with exactly n occurrences of the pattern 2–13 is given by the coefficient of q^{n} in the normalisation Z_{m} for the stationary distribution of the α = β = η = 1, γ = δ = 0 partially asymmetric exclusion process — a Markov process widely studied in both mathematics and physics.

We first give an almost trivial proof, based on generating functions, which are known in continued fraction form for both problems. In the next section we give a more interesting, bijective proof.

1Six-digit numbers prefixed by ‘A’ indicate the corresponding entry in The On-Line Encyclopedia of Integer Sequences [7].

Proof. Claesson and Mansour [4] give the generating function P (q; t) for the distribution of occurrences of the pattern 2–13 in permutations as a Stieltjes continued fraction:

P (q; t) = \frac{1}{1 − \frac{[1]_{q}t}{1 − \frac{[1]_{q}t}{1 − \frac{[2]_{q}t}{1 − \frac{[2]_{q}t}{...}}}}}.

The generating function M(q; t) for q-weighted bi-coloured Motzkin paths is well known ([5], Theorem 1) to be given by the Jacobi continued fraction

M(q; t) = \frac{1}{1 − 2[1]_{q}t − \frac{[1]_{q}[2]_{q}t^{2}}{1 − 2[2]_{q}t − \frac{[2]_{q}[3]_{q}t^{2}}{1 − 2[3]_{q}t − \frac{[3]_{q}[4]_{q}t^{2}}{...}}}}.

Applying the contraction formula from Stieltjes to Jacobi continued fractions, we find that indeed P (q; t) = 1 + tM(q; t).

2 Bijective proof

We will define three mappings: two bijections B and T , and a projection P. They will have the property that the composition T ∘ P ∘ B is a surjection from the set of permutations weighted by occurrences of the pattern 2–13, to the set of q-weighted bi-coloured Motzkin paths. Theorem 3 will follow.

Definition 5. A bi-coloured vertex-weighted Motzkin path is a bi-coloured Motzkin path in which vertex k, at height h, is given a weight from the set {1, q, …, q^{h}} if step k is E or N, and from the set {1, q, …, q^{h−1}} otherwise. Let M_{n}^{∗} denote the set of bi-coloured vertex-weighted Motzkin paths of length n.

We now define a bijection (of Foata and Zeilberger [6]) B from S_{n} to M_{n}^{∗}. Let step i in p = B(π) be

E if π(i) ≥ i ≥ π^{−1}(i),
F if π(i) < i < π^{−1}(i),
N if π(i) > i < π^{−1}(i),
S if π(i) < i > π^{−1}(i).

Let vertex n + 1 have weight 1, and vertex k, 1 ≤ k ≤ n, weight q^{m(k)}, where m(k) is the number of occurrences of the pattern 2–13 in π in which k takes the role of 2.

Theorem 6 ([6]). The mapping B is a weight preserving bijection between permutations and bi-coloured vertex-weighted Motzkin paths, such that the weight of p = B(π) equals the number of occurrences of 2–13 in π.

Next we define a projection P from bi-coloured vertex-weighted Motzkin paths to a slightly different set of vertex-weighted Motzkin paths, M′.

Definition 7. For p ∈ M, let p′ = P(p) have the same steps. If step k is E or N, let vertex k, at height h, have weight 1 + ⋯ + q^{h}, and weight 1 + ⋯ + q^{h−1} otherwise.

The final step is to define a bijection T from M′_{n+1} to M_{n}.

Definition 8. For p in M′_{n+1} and for k ∈ [n], if steps k and k + 1 is x and y, let step k in T (p) be given by

\begin{matrix}x\y & E & F & N & S \\ E & E & S & E & S \\ F & N & F & N & F \\ N & N & F & N & F \\ S & E & S & E & S \end{matrix}

and have the same weight as vertex k + 1 in p.

Theorem 9. The mapping T is a weight preserving bijection from M′_{n+1} to M_{n}.

Proof. We will describe the inverse mapping.

Append an E step at both the start and the end of a walk r ∈ M_{n} to give a walk r′ of length n + 2. If steps k and k + 1 in r′ are x and y, respectively, step k of T^{−1}(r) is given by

\begin{matrix}x\y & E & F & N & S \\ E & E & N & N & E \\ F & S & F & F & S \\ N & E & N & N & E \\ S & S & F & F & S \end{matrix}

Further, vertex k in s = T^{−1}(r) has the same weight as step k in r′.

That T^{−1} indeed is the inverse of T follows easily from the definition of T .

3 Application

Let C(x) be the Catalan function, C(x) = \frac{1−\sqrt{1−4x}}{2x}. As is well known,

g_{1}(x_{1}; t) = \frac{C(x_{1}t) − 1}{x_{1}t} = C^{2}(x_{1}t)

is the generating function for bi-coloured Motzkin paths in which each step has weight x_{1}.

More generally, let g_{k}(t) = g_{k}(x_{1}, x_{2}, …, x_{k}; t) be the generating function for bi-coloured weighted Motzkin walks in which steps ending at height h ≤ k have weight x_{k−h+1}, and steps ending at height h ≥ k have weight x_{1}.

Lemma 1.

g_{k}(t) = \frac{1}{1 − 2x_{k}t − x_{k−1}x_{k}t^{2}g_{k−1}(t)}.

Proof. Considering the first return to height 0 (where a step E or F is considered a return), we find g_{k}(t) = 1 + (x_{k}t + x_{k}t + x_{k−1}tg_{k−1}(t)x_{k}t)g_{k}(t).

The function g_{k}([q]_{k}, [q]_{k−1}, …, [q]_{0}; t) obviously agrees with the full generating function for q−coloured Motzkin paths for powers of q less than k, and consequently we get the following proposition.

Proposition 10. For n < k the number of permutations of length m with exactly n occurrences of the pattern 2–13 is given by

[q^{n}t^{m}]tg_{k}([q]_{k}, [q]_{k−1}, …, [q]_{0}; t).

The following lemma is useful for extracting coefficients from the generating functions.

Lemma 2. Let S(t) = \sqrt{1 − 4t}. For l ≤ m we have

[t^{n}]\frac{C^{m}(t)}{(2 − C(t))^{l}} = [t^{n}]\frac{C^{m−l}(t)}{S^{l}(t)} = \frac{1}{2^{m−l}} ∑_{k=0}^{m−l} \binom{m − l}{k}(−1)^{k}[t^{n+m−l}]S^{k−l}.

Proof. The first equality holds since S(t)C(t) = 2 − C(t); the second since C(t) = (1 − S(t))/2t.

Note that finding [t^{n}]S^{k} is but an application of the binomial theorem.

Let Φ_{k}(t) be the generating function for the sequence ϕ_{k}(m). We have g_{1}(1; t) = C^{2}(t). Thus, the number of permutations of length m with 0 occurrences of 2–13 is given by the m:th Catalan number.

Next, we have

g_{2}(1 + q, 1; t) = \frac{1}{1 − t − tC((1 + q)t)}, and

\frac{∂}{∂q} g_{2}(1 + q, 1; t) = \frac{t^{2}C′((1 + q)t)}{(1 − t − tC^{2}((1 + q)t)},

where C′(x) = \frac{∂}{∂x}C(x). Setting q = 0, and applying the transformation rules tC^{2}(t) = C(t) − 1 and C′(t) = C^{3}(t)/(2 − C(t)), we find that

Proposition 11 ([4]).

Φ_{1}(t) = t^{3}C^{7}(t)\frac{1}{2 − C(t)}.

Applying Lemma 2 we get

ϕ_{1}(m) = \binom{2m}{m − 3} (\underline{A002696}).

Similarly we derive expressions for Φ_{k} and ϕ_{k} for k ≤ 8. The calculations can be summarised as follows.

1. Find g_{k+1}.

2. Differentiate to get \frac{∂}{∂q^{k}} g_{k+1}|_{q=0}.

3. Apply the transformation rules t = (C − 1)C^{−2}, C′ = C^{3}(2 − C)^{−1}, C′′ = 2C^{5}(3 − C)(2 − C)^{−3}, …, C^{(k)} = ⋯ to get a an expression of the form t^{a}C^{b}P (C)(2 − C)^{−c} where a, b and c are positive integers and P is a polynomial.

4. Apply Lemma 2 and the binomial theorem to extract coefficients.

5. Use standard binomial coefficient identities to simplify.

We note that all steps may, with some programming, be fully automated in a package such as Mathematica (used here). The bottleneck in this procedure is the differentiation (step 2), which in the straightforward implementation is quite memory consuming. This is also the main reason for us to restrict to k ≤ 8 in this work — step 2 required almost 1GB of RAM.

Proposition 12 ([4]).

Φ_{2}(t) = \frac{∂^{2}}{∂^{2}q} g_{3}([q]_{3}, [q]_{2}, [q]_{1}; t)|_{q=0} = t^{4}C^{9}(t)\frac{−1 + 5C(t) − 2C^{2}(t)}{(2 − C(t))^{3}},

ϕ_{2}(m) = \frac{m}{2}\binom{2m}{m − 4} (\underline{A094218}).

Proposition 13 ([4]).

Φ_{3}(t) = \frac{∂^{3}}{∂^{3}q} g_{4}(t)|_{q=0} = t^{5}C^{11}(t)\frac{2 + 6C(t) + 5C(t)^{2} − 8C(t)^{3} + 2C(t)^{4}}{(2 − C(t))^{5}}

ϕ_{3}(m) = \frac{(m + 1)(m + 2)}{6}\binom{2m}{m − 5} (\underline{A094219}).

Proposition 14.

Φ_{4}(t) = \frac{∂^{4}}{∂^{4}q} g_{5}(t)|_{q=0} = t^{5}C^{11} \frac{5 − 118C + 259C^{2} − 240C^{3} + 142C^{4} − 62C^{5} + 17C^{6} − 2C^{7}}{(2 − C)^{7}} ,

ϕ_{4}(m) = \frac{−36 − 100m − 13m^{2} + 4m^{3} + m^{4}}{24(m + 6)} \binom{2m}{m − 5} (\underline{A120812}).

Proposition 15.

Φ_{5}(t) = \frac{∂^{5}}{∂^{5}q} g_{6}(t)|_{q=0}

= t^{6}C^{13} \frac{−14 − 540C + 1519C^{2} − 1517C^{3} + 616C^{4} + 70C^{5} − 199C^{6} + 97C^{7} − 22C^{8} + 2C^{9}}{(2 − C)^{9}} ,

ϕ_{5}(m) = \frac{(m + 4)(−108 − 192m + 3m^{2} + 8m^{3} + m^{4})}{120(m + 7)}\binom{2m}{m − 6} (\underline{A120813}).

Proposition 16.

Φ_{6}(t) = \frac{∂^{6}}{∂^{6}q} g_{7}(t)|_{q=0}

= \frac{t^{6}C^{13}}{(2 − C)^{11}} ( − 42 + 4054C − 18354C^{2} + 36038C^{3} − 40660C^{4} + 30080C^{5} − 16090C^{6} + 6914C^{7}

− 2604C^{8} + 840C^{9} − 202C^{10} + 30C^{11} − 2C^{12}),

ϕ_{6}(m) = \frac{\binom{2m}{m−6}}{720(m + 7)(m + 8)}(20160+44448m+548m^{2}−4196m^{3}−565m^{4}+67m^{5}+17m^{6}+m^{7})

(\underline{A120814}).

Proposition 17.

Φ_{7}(t) = \frac{∂^{7}}{∂^{7}q} g_{8}(t)|_{q=0}

= \frac{t^{7}C^{15}}{(2 − C)^{13}} (132+16516C−92666C^{2}+215944C^{3}−281094C^{4}+225628C^{5}−110922C^{6}+25360C^{7}

+ 7066C^{8} − 9364C^{9} + 4622C^{10} − 1440C^{11} + 294C^{12} − 36C^{13} + 2C^{14}),

ϕ_{7}(m) = \frac{\binom{2m}{m−7}}{5040(m + 8)(m + 9)}((m+5)(40320+67824m−20180m^{2}−7556m^{3}−5m^{4}+211m^{5}

+ 25m^{6} + m^{7}) (\underline{A120815}).

Proposition 18.

Φ_{8}(t) = \frac{∂^{8}}{∂^{8}q} g_{9}(t)|_{q=0}

= \frac{t^{7}C^{15}}{(2 − C)^{15}} (429−65536C +499576C^{2} −1679496C^{3} +3298054C^{4} −4270444C^{5} +3911698C^{6}

− 2671744C^{7} + 1439239C^{8} − 659504C^{9} + 279446C^{10} − 112922C^{11} + 41165C^{12} − 12362C^{13} + 2816C^{14} − 448C^{15} + 44C^{16} − 2C^{17}),

ϕ_{8}(m) = \frac{\binom{2m}{m−7}}{40320(m + 8)(m + 9)(m + 10)}(−7983360−12956832m+10475400m^{2}+3647724m^{3}

− 416326m^{4} − 249417m^{5} − 19971m^{6} + 2646m^{7} + 576m^{8} + 39m^{9} + m^{10}) (\underline{A120816})

References

[1] E. Babson and E. Steingrímsson, Generalized permutation patterns and a classification of the Mahonian statistics, Sém. Lothar. Combin., Art. B44b (2000), electronic.

[2] R. Brak, S. Corteel, J. Essam, R. Parviainen, and A. Rechnitzer, A combinatorial derivation of the PASEP stationary state. Submitted for publication.

[3] A. Claesson, Generalized pattern avoidance, European J. Combin., 22 (2001), 961–971.

[4] A. Claesson and T. Mansour, Counting patterns of type (1,2) and (2,1) in permutations, Adv. in Appl. Math., 29 (2002), 293–310.

[5] P. Flajolet. Combinatorial aspects of continued fractions. Discrete Math., 2 (1980), 125–161.

[6] D. Foata and D. Zeilberger, Denert’s permutation statistic is indeed Euler-Mahonian, Stud. Appl. Math., 83 (1990), 31–59.

[7] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electronically

   at http://www.research.att.com/∼njas/sequences/.

2000 Mathematics Subject Classification: 05A05, 05A15.

Keywords: Permutations, restricted pattern, Motzkin paths, generating functions.

(Concerned with sequences \underline{A000108}, \underline{A002696}, \underline{A094218}, \underline{A094219}, \underline{A120812}, \underline{A120813}, \underline{A120814}, \underline{A120815}, and \underline{A120816}.)

Received July 6 2006; revised version received July 11 2006. Published in Journal of Integer Sequences, July 19 2006.

Return to Journal of Integer Sequences home page.