Distributions of Statistics Over Pattern-Avoiding Permutations

Michael Bukata, Ryan Kulwicki, Nicholas Lewandowski, Lara Pudwell,

Jacob Roth, and Teresa Wheeland Department of Mathematics and Statistics Valparaiso University Valparaiso, IN 46383 USA

               Michael.Bukata@valpo.edu
                Ryan.Kulwicki@valpo.edu
            Nicholas.Lewandowski@valpo.edu
                Lara.Pudwell@valpo.edu
                 Jacob.Roth@valpo.edu
               Teresa.Wheeland@valpo.edu

Abstract

We consider the distribution of ascents, descents, peaks, valleys, double ascents, and double descents over permutations avoiding a set of patterns. Many of these statistics have already been studied over sets of permutations avoiding a single pattern of length 3. However, the distribution of peaks over 321-avoiding permutations is new, and we relate it to statistics on Dyck paths. We also obtain new interpretations of a number of well-known combinatorial sequences by studying these statistics over permutations avoiding two patterns of length 3.

1 Introduction

Let S_{n} denote the set of permutations of {1, 2, …, n} and let red(w_{1} ⋯ w_{m}) be the word obtained by replacing the ith smallest digit(s) of w with i. Given π ∈ S_{n} and ρ ∈ S_{m}, we say that π contains ρ as a pattern if there exist indices 1 ≤ i_{1} < i_{2} < ⋯ < i_{m} ≤ n such that π_{i_{a}} < π_{i_{b}} if and only if ρ_{a} < ρ_{b}; that is, red(π_{i_{1}} ⋯ π_{i_{m}}) = ρ. Otherwise π avoids ρ. For example, the permutation 18274635 ∈ S_{8} contains the pattern ρ = 4312 using i_{1} = 2, i_{2} = 4, i_{3} = 5, and i_{4} = 8 since the entries of π_{i_{1}}π_{i_{2}}π_{i_{3}}π_{i_{4}} = 8745 are in the same relative order as 4312; i.e., red(8745) = 4312. Let S_{n}(ρ_{1}, …, ρ_{p}) be the set of permutations avoiding each of ρ_{1}, …, ρ_{p}; S_{n}(ρ_{1}, …, ρ_{p}) is called a pattern class and the pattern(s) ρ_{1}, …, ρ_{p} are called the basis of the pattern class. Further, let s_{n}(ρ_{1}, …, ρ_{p}) = |S_{n}(ρ_{1}, …, ρ_{p})|. It is well-known that

s_{n}(ρ) = \frac{\binom{2n}{n}}{n+1} (\underline{A000108}) when ρ ∈ S_{3}, and there are a variety of techniques for determining s_{n}(ρ_{1}, …, ρ_{p}), depending on that patterns to be avoided.

Another well-known family of objects enumerated by the Catalan numbers (\underline{A000108}) is the set of Dyck paths of semilength n. Here a Dyck path of semilength n is a sequence of n up-steps (U = ⟨1, 1⟩) and n down-steps (D = ⟨1, −1⟩) from (0, 0) to (2n, 0) that never falls below the x-axis. We let D_{n} denoted the set of such paths. Further, we let I_{n} be the set of indecomposable Dyck paths of semilength n, where a path is indecomposable if it only touches the x-axis at (0, 0) and at (2n, 0). Because both S_{n}(ρ) and D_{n} have the same enumeration when ρ ∈ S_{3}, bijections with Dyck paths are a powerful tool to better understand the structure of these pattern classes.

Some common permutations and constructions require addition notation. To this end, let I_{m} = 1 ⋯ m be the increasing permutation of length m and let J_{m} = m(m − 1) ⋯ 1 be the decreasing permutation of length m. Further, given permutations α ∈ S_{a} and β ∈ S_{b}, let α ⊕ β ∈ S_{a+b} denote the direct sum of α and β and let α ⊖ β ∈ S_{a+b} denote the skew-sum of α and β, defined as follows:

α ⊕ β = \begin{cases}α(i), & 1 ≤ i ≤ a; \\ a + β(i − a), & a + 1 ≤ i ≤ a + b. \end{cases}

α ⊖ β = \begin{cases}α(i) + b, & 1 ≤ i ≤ a; \\ β(i − a), & a + 1 ≤ i ≤ a + b. \end{cases}

Another thread of research is to consider the distribution of permutation statistics over S_{n}. Here, a permutation statistic is a function stat : S_{n} → ℤ^{+} ∪{0}. Some common statistics include ascents (asc), descents (des), double ascents (dasc), double descents (ddes), peaks (pk), and valleys (vl), which are defined as follows:

asc(π) = |{i|π_{i} < π_{i+1}}| ,
des(π) = |{i|π_{i} > π_{i+1}}| ,
dasc(π) = |{i|π_{i} < π_{i+1} and π_{i+1} < π_{i+2}}| ,
ddes(π) = |{i|π_{i} > π_{i+1} and π_{i+1} > π_{i+2}}| ,
pk(π) = |{i|π_{i} < π_{i+1} and π_{i+1} > π_{i+2}}| ,
vl(π) = |{i|π_{i} > π_{i+1} and π_{i+1} < π_{i+2}}| .

It is well-known that |{π ∈ S_{n}|asc(π) = k}| = |{π ∈ S_{n}|des(π) = k}| is given by the Eulerian numbers (\underline{A008292}), while the distributions of dasc, ddes, pk, and vl, are newer to the literature or open.

Combining these two areas, we consider the distribution of permutation statistics over S_{n}(ρ_{1}, …, ρ_{p}). Let

a_{n,k}^{stat}(ρ_{1}, …, ρ_{p}) = |{π ∈ S_{n}(ρ_{1}, …, ρ_{p})|stat(π) = k}| .

Further, for π ∈ S_{n}, let π^{r} = π_{n} ⋯ π_{1} and π^{c} = (n + 1 − π_{1}) ⋯ (n + 1 − π_{n}) denote the reverse and complement of π respectively. By symmetry, we observe the following:

a_{n,k}^{asc}(ρ_{1}, …, ρ_{p}) = a_{n,k}^{des}(ρ_{1}^{r}, …, ρ_{p}^{r})
= a_{n,k}^{des}(ρ_{1}^{c}, …, ρ_{p}^{c})
= a_{n,k}^{asc}(ρ_{1}^{rc}, …, ρ_{p}^{rc}),

a_{n,k}^{dasc}(ρ_{1}, …, ρ_{p}) = a_{n,k}^{ddes}(ρ_{1}^{r}, …, ρ_{p}^{r})
= a_{n,k}^{ddes}(ρ_{1}^{c}, …, ρ_{p}^{c})
= a_{n,k}^{dasc}(ρ_{1}^{rc}, …, ρ_{p}^{rc}),

a_{n,k}^{pk}(ρ_{1}, …, ρ_{p}) = a_{n,k}^{pk}(ρ_{1}^{r}, …, ρ_{p}^{r})
= a_{n,k}^{vl}(ρ_{1}^{c}, …, ρ_{p}^{c})
= a_{n,k}^{vl}(ρ_{1}^{rc}, …, ρ_{p}^{rc}).

In this paper, we consider a_{n,k}^{stat}(ρ_{1}, …, ρ_{p}) where p ∈ {1, 2} and where

stat ∈ {asc, des, dasc, ddes, pk, vl} .

A summary our results is given in Table 1. In Section 2, we detail known results for a_{n,k}^{stat}(ρ) where ρ ∈ S_{3}. While there are a number of previous results, a_{n,k}^{pk}(321) is new, and we determine its distribution in Section 3 via a bijection with Dyck paths. In Section 4 we consider a_{n,k}^{stat}(ρ_{1}, ρ_{2}) for ρ_{1}, ρ_{2} ∈ S_{3}; while these enumerations yield a number of well-known combinatorial sequences, the particular interpretations in terms of permutation statistics are new.

2 History

The study of permutation statistics has a rich history, with over 300 possible statistics listed in the database FindStat [12] as of this writing. However, the distribution of statistics

B\ st  asc  des  pk  vl  dasc  ddes
231 (known) (known) Thm. 1 Thms. 2 and 3 (known) (known)
321 (known) (known) Thm. 3  Thm. 3  (known) (known)
213,312 Prop. 6 Prop. 6 Prop. 7  Prop. 7  Prop. 8  Pr. 9
132,213 Prop. 10 Prop. 10 Prop. 11  Prop. 11  Prop. 12 Prop. 12
213,231 Prop. 10 Prop. 10 Prop. 11  Prop. 11  Prop. 12 Prop. 12
123,132 Prop. 13 Prop. 14 Prop. 15  Prop. 16  Prop. 17 Prop. 18
132,321 Prop. 21 Prop. 21 Prop. 22  Prop. 23  Prop. 24 Prop. 25

Table 1: Results for distribution of statistics over S_{n}(B)

over pattern classes, rather than over all permutations, is newer. Robertson, Saracino, and Zeilberger [9] and Mansour and Robertson [6] studied the distribution of fixed points over pattern classes whose basis is a subset of S_{3}. Elizalde [4] gave an alternate approach to the distribution of fixed points using bijections with Dyck paths and also determined the distribution of excedances over the same pattern classes.

Dokos, Dwyer, Johnson, Sagan, and Selsor [3] defined two pattern sets {ρ_{1}, …, ρ_{p}} and {ρ′_{1}, …, ρ′_{p}} to be st-Wilf equivalent if a_{n,k}^{st}(ρ_{1}, …, ρ_{p}) = a_{n,k}^{st}(ρ′_{1}, …, ρ′_{p}) for all n and k and determined all st-Wilf equivalences for subsets of S_{3} when st is the number of inversions or the major index.

Fixed points and excedances are statistics involving a single digit of π at a time, while inversions and major index involve multiple digits. The statistics we study in this paper may best be thought of as consecutive patterns in π. In particular, asc(π) is the number of consecutive 12 patterns in π, des(π) is the number of consecutive 21 patterns in π, dasc(π) is the number of consecutive 123 patterns in π and ddes(π) is the number of consecutive 321 patterns in π. Meanwhile, pk(π) is the number of consecutive 132 patterns plus the number of consecutive 231 patterns in π and vl(π) is the number of consecutive 213 patterns plus the number of consecutive 312 patterns in π. In the following subsections, we review the history of results involving these statistics over specific pattern classes.

2.1 Ascents and Descents

Studying ascents and descents over S_{n}(ρ) where ρ ∈ S_{3} yields one of exactly two sequences: \underline{A001263} (the Narayana numbers) or \underline{A091156}.

For ρ ∈ \{132, 213, 231, 312\}, a_{n,k}^{asc}(ρ) = a_{n,k}^{des}(ρ) = \frac{\binom{n−1}{k}\binom{n}{k}}{k + 1} (\underline{A001263}). This enumeration

follows by a bijection between permutations in S_{n}(231) with k ascents with Dyck paths of semilength n with k DU factors, which are known to be enumerated by \underline{A001263}. For more details, see Petersen [8].

On the other hand, for ρ ∈ \{123, 321\} a_{n,k}^{asc}(ρ) = a_{n,k}^{des}(ρ) is given by \underline{A091156}. In 2010, Barnabei, Bonetti, and Silimbani [1] showed that

G(q, z) = ∑_{n≥0} ∑_{k≥0} a_{n,k}^{des}(321)q^{k}z^{n}

satisfies

z(1 − z + qz)G^{2} − G + 1 = 0.

Their work features a bijection between 321-avoiding permutations of length n and Dyck paths of semilength n. Tracking descents in the permutations corresponds to tracking both DU and DDD factors in the corresponding Dyck path. In Section 3, we make use of the same bijection to study the distribution of peaks over 321-avoiding permutations. As a corollary, we obtain a simpler way of tracking descents in permutations via the corresponding Dyck paths.

2.2 Peaks, Valleys, and More

Table 2 shows the distributions of pk, vl, dasc, and ddes over S_{n}(ρ) for ρ ∈ S_{3}. Notice that by reversal, understanding the distributions when ρ ∈ {231, 312, 321} determines the distributions for the remaining patterns. The relationship between the first two rows of the table follows from the fact that 231^{rc} = 312.

ρ\ st  pk  vl  dasc  ddes
231 \underline{A091894} \underline{A236406} \underline{A092107} \underline{A092107}
312 \underline{A236406} \underline{A091894} \underline{A092107} \underline{A092107}
321 \underline{A236406} \underline{A236406} new  (none)

Table 2: Distribution of statistics over S_{n}(ρ) for ρ ∈ S_{3}

In a recent paper, Pan, Qiu, and Remmel [7] investigated the distribution of consecutive patterns of length 3 over S_{n}(132) and S_{n}(123). As seen above, their work directly addresses the distributions of dasc and ddes. However, pk and vl involve combining the distributions of two of their statistics at a time. Since the results for dasc and ddes are already studied in [7], we focus on pk and provide an alternate approach in Section 3. Once we have determined a_{n,k}^{pk}(ρ) for ρ ∈ {231, 312, 321}, by symmetry, we have determined the distributions of pk and vl over all S_{n}(ρ) for ρ ∈ S_{3}. In Section 4 we extend this work to pattern classes that avoid two or more patterns.

3 Peaks

We now wish to determine a_{n,k}^{pk}(ρ) for ρ ∈ {231, 312, 321}.

Theorem 1. For n ≥ 1, k ≥ 0, a_{n,k}^{pk}(231) = \frac{2^{n−2k−1}\binom{n−1}{2k}\binom{2k}{k}}{k + 1}.

We prove Theorem 1 via a bijection with Dyck paths. The bijection in this proof is given by Petersen [8] for the purpose of determining a_{n,k}^{des}(ρ) and the eumeration given in Theorem 1 is given by Petersen in \underline{A091894} of the On-line Encyclopedia of Integer Sequences. We include the argument here for completeness.

Proof. Define a bijection ϕ : S_{n}(231) → D_{n} recursively as follows. The empty permutation maps to the empty path and ϕ(1) = UD. Now, for π ∈ S_{n}(231) where n ≥ 2, suppose that π_{i} = n and write π = π_{1} ⋯ π_{i−1}nπ_{i+1} ⋯ π_{n}. Let α = red(π_{1} ⋯ π_{i−1}) and β = red(π_{i+1} ⋯ π_{n}). Notice that α or β could be empty. Now ϕ(π) = ϕ(α)Uϕ(β)D.

Notice that π has a peak involving n exactly when α and β are both non-empty. Since ϕ(α) ends in a D and ϕ(β) begins in a U, by construction, there is a peak in π involving n exactly when the corresponding U in ϕ(π) is part of a DUU factor. Recursively, the number of peaks of π corresponds to the number of DUU factors of ϕ(π), or, equivalently, to the number of DDU factors in the reversal of ϕ(π). The number of paths in D_{n} with k DDU

factors is given to be \frac{2^{n−2k−1}\binom{n−1}{2k}\binom{2k}{k}}{k + 1} in OEIS sequence \underline{A091894}.

The fact that a_{n,k}^{pk}(312) = a_{n,k}^{pk}(321) requires another well-known bijection.

Theorem 2. For all n and k, a_{n,k}^{pk}(312) = a_{n,k}^{pk}(321).

The bijection below is a symmetry of a well-known bijection of Simion and Schmidt [10] using left-to-right maxima. They used this bijection to to show that s_{n}(312) = s_{n}(321) for all n, while we use it to show the refinement that a_{n,k}^{pk}(312) = a_{n,k}^{pk}(321). We say that π_{i} is a left-to-right maximum of π if π_{i} > π_{j} for j < i. For example the left-to-right maxima of 32658741 are 3, 6, and 8.

Proof. We define a bijection ζ : S_{n}(312) → S_{n}(321) that preserves left-to-right maxima.

Consider π ∈ S_{n}(312). Suppose that the left-to-right maxima of π are ℓ_{1}, …, ℓ_{k} and that they are located in positions j_{1}, …, j_{k}. We claim that π is the unique 312-avoiding permutation with left-to-right maxima ℓ_{1}, …, ℓ_{k} in positions j_{1}, …, j_{k}. In particular, we determine the other entries of π from left to right by placing in position i the largest unused digit that is smaller than the rightmost left-to-right maxima before position i.

Similarly, there is a unique 321-avoiding permutation with left-to-right maxima ℓ_{1}, …, ℓ_{k} in positions j_{1}, …, j_{k}. In particular, the digits that are not left-to-right maxima must appear in increasing order. Let ζ(π) be this permutation.

Notice that any peak of π must involve a left-to-right maxima as its middle entry, and similarly any peak of ζ(π) must involve a left-to-right maxima as its middle entry. Since ζ preserves left-to-right maxima both in value and in position, ζ preserves peaks.

Figure 1: Bijection ψ applied to π = 617238459

Finally, we determine a_{n,k}^{pk}(321), which is the central result of this paper. Previously, Baxter [2] computed data about a_{n,k}^{pk}(321) using an enumeration scheme algorithm; however our generating function is new and our bijective argument ties together a number of previously-known generating function results.

Theorem 3.

∑_{n≥0} ∑_{k≥0} a_{n,k}^{pk}(321)q^{k}z^{n} = 1 + z (−\frac{−1 + \sqrt{−4z^{2}q + 4z^{2} − 4z + 1}}{2z(zq − z + 1)})^{2} .

We first describe a bijection ψ : S_{n}(321) → D_{n} that is due to Krattenthaler [5]. Consider π ∈ S_{n}(321) and plot the points (i, π_{i}) for 1 ≤ i ≤ n. Let P = {(p_{1}, π_{p_{1}}), …, (p_{k}, π_{p_{k}})} be the set of points (i, π_{i}) such that π_{i} is not a left-to-right maxima of π and p_{1} < p_{2} < ⋯ < p_{k}. Then define a path of E = ⟨1, 0⟩ steps and N = ⟨0, 1⟩ steps from (1, 0) to (n + 1, n) in the following way: use p_{1} − 1 E steps followed by π_{p_{1}} N steps to get from (1, 0) to (p_{1}, π_{p_{1}}). For 1 ≤ i ≤ k − 1, use (p_{i+1} − p_{i}) E steps followed by (π_{p_{i+1}} − π_{p_{i}}) N steps to get from (p_{i}, π_{p_{i}}) to (p_{i+1}, π_{p_{i+1}}). Finally, take ((n + 1) − p_{k}) E steps followed by (n − π_{p_{k}}) N steps to get from (p_{k}, π_{p_{k}}) to (n + 1, n). Figure 1 shows this process for π = 617238459. By construction, this path stays below the line y = x − 1, and we obtain the Dyck path ψ(π) by replacing all E steps with U and all N steps with D. Therefore, ψ(617238459) = UDUUDUDUUDUDUUDDDD.

We know that a 321-avoiding permutation can be partitioned into two increasing subsequences: namely, the left-to-right maxima, and the remaining digits. Necessarily, the middle digit of a peak in such a permutation must be a left-to-right maxima, and the final digit is not. After π_{1}, whenever we have a left-to-right maxima in π, we have a UU factor in ψ(π). Whenever we have a non-left-to-right maxima in π, we have at least one D in ψ(π). Therefore, a peak of π ∈ S_{n}(321) corresponds to a UUD factor in ψ(π), with one exception. A UUD factor that is followed only by Ds indicates that π ended with a left-to-right maxima.

To this end, we introduce two statistics on Dyck paths. Let st(d) be the number of UUD factors in Dyck path d, and let st^{∗}(d) be the number of UUD factors in Dyck path d that appear before the last U. For example, st(UUUDDDUD) = st^{∗}(UUUDDDUD) = 1, while st(UUUDDDUUDD) = 2 and st^{∗}(UUUDDDUUDD) = 1. We have just seen that

∑_{n≥0} ∑_{k≥0} a_{n,k}^{pk}(321)q^{k}z^{n} = ∑_{n≥0} ∑_{d∈D_{n}} q^{st^{∗}(d)}z^{|d|}.

It remains to study the distribution of st^{∗} on Dyck paths of semilength n.

We define the following four generating functions, which are weight-enumerators on Dyck paths. Throughout, st(d) and st^{∗}(d) are as defined above, D_{n} is the set of all Dyck paths of semilength n, and I_{n} is the set of indecomposable Dyck paths of semilength n.

A := ∑_{n≥0} ∑_{d∈D_{n}} q^{st(d)}z^{n}, B := ∑_{n≥0} ∑_{d∈I_{n}} q^{st(d)}z^{n},
C := ∑_{n≥0} ∑_{d∈D_{n}} q^{st^{∗}(d)}z^{n}, D := ∑_{n≥0} ∑_{d∈I_{n}} q^{st^{∗}(d)}z^{n}.

Notice that our goal is to find C(q, z). By construction we have C = 1 + AD and A = 1 + AB. We prove Theorem 3 by first determining A and D.

Lemma 4.

D(q, z) = ∑_{n≥0} ∑_{k≥0} a_{n,k}^{des}(321)q^{k}z^{n+1}.

Proof. Suppose π ∈ S_{n}(321). Any descent in π consists of a left-to-right maxima followed by a non-left-to-right-maxima. Using bijection ψ, defined above, π has a left-to-right maxima at the beginning of π and also whenever ψ(π) has a UU factor. Similarly, π has a non-left-to-right maxima whenever it has a UD factor, unless the D is at the end of ψ(π). Together, we detect a descent in π when ψ(π) begins with a UD factor and whenever ψ(π) has a UUD factor before the last U. To convert the first case into a UUD factor, let ψ̂(π) be the Dyck path obtained by adding a U to the beginning and a D to the end of ψ(π). By construction, ψ̂(π) is an indecomposable Dyck path of semilength n + 1. Now, each descent in π corresponds to a UUD factor in ψ̂(π) that appears before the final U, which proves the lemma.

Next, we consider A(q, z).

Lemma 5.

A(q, z) = ∑_{n≥0} ∑_{k≥0} a_{n,k}^{des}(321)q^{k}z^{n}.

Proof. By definition, A(q, z) tracks all UUD factors across Dyck paths of semilength n.

We have seen in the proof of Lemma 4 that there is at most one UUD factor in ψ(π) that does not correspond to a descent of π, namely a UUD factor that is followed only by Ds.

d with st(d) = 2 and des(ψ^{−1}(d)) = 3

ι(d) with st(ι(d)) = 3 and des(ψ^{−1}(ι(d))) = 2

Figure 2: An example of ι(d)

Similarly, there is at most one descent in π that does not correspond to a UUD factor in ψ(π), namely a descent at the beginning of π corresponds to ψ(π) beginning with a UD factor. In other words, given π ∈ S_{n}(321) with d = ψ(π), either st(d) = des(π), st(d) + 1 = des(π), or st(d) = des(π) + 1,

We prove the lemma by giving an involution ι on D_{n}.

If d = ψ(π) with st(d) = des(π), then ι(d) = d.

Now, consider d = ψ(π) with st(d) = k and des(π) = k +1. Since π has one more descent than st(d), we know that ψ(π) begins with UD and d does not have a UUD factor at the end. In other words, d = (UD)^{i}d′DUD^{j} for some positive i and j where d′ is a sequence of n − i − 1 Us and n − i − j − 1 Ds that does not begin in UD. Let ι(d) = d′DU(U^{i}D^{i})D^{j}. Now, by construction, ι(d) has k + 1 UUD factors, since a new UUD factor was introduced at the end, but des(ϕ^{−1}(ι(d))) = k since there is no longer an initial UD in ι(d).

Finally, consider d = ψ(π) with st(d) = k +1 and des(π) = k. Since d has one more UUD factor than des(π), we know that d ends with DU^{i}D^{j} for some j ≥ i ≥ 2 and d does not begin with UD. In other words, d = d′DU^{i}D^{j} where d′ is a sequence of n−i Us and n−j −1 Ds that does not begin in UD. Let ι(d) = (UD)^{i−1}d′DUD^{j−i}. Now, by construction, ι(d) has k UUD factors, since a UUD factor was removed at the end, but des(ϕ^{−1}(ι(d))) = k + 1 since there is a new initial UD in ι(d).

By involution ι, we see that UUD factors on Dyck paths are equidistributed with descents in 321-avoiding permutations.

An example of ι in action is shown in Figure 2.

As a consequence of Lemmas 4 and 5, we see that D = zA. Therefore, C(q, z) = 1+AD = 1 + zA^{2}. Using Barnabei, Bonetti, and Silimbani’s result for A(q, z) in [1] yields Theorem 3.

Two nice observations follow from this proof. First, Barnabei, Bonetti, and Silimbani determined A(q, z) by counting the number of DU factors plus the number of DDU factors in ϕ(π). We have shown in Lemma 5 that A(q, z) can be determined by counting only the

Patterns \Statistic  asc  des
213,312  \binom{n−1}{k}  \binom{n−1}{k}
132,213  \binom{n−1}{k}  \binom{n−1}{k}
213,231  \binom{n−1}{k}  \binom{n−1}{k}
123,132  \binom{n}{2k}  \binom{n}{2(n−k−1)}
132,321  \begin{matrix}1, & k = n − 1; \\ \binom{n}{2}, & k = n − 2. \end{matrix} \begin{matrix}1, & k = 0; \\ \binom{n}{2}, & k = 1. \end{matrix}

Table 3: Distribution of asc and des over pattern classes of the form S_{n}(ρ_{1}, ρ_{2}) with ρ_{1}, ρ_{2} ∈ S_{3}

number of UUD factors in ϕ(π). Second, by Lemma 5 and the fact that A = 1 + AB, we can determine B(q, z). It turns out

B(q, z) = z(1 − q) + ∑_{n≥0} ∑_{k≥0} a_{n,k}^{pk}(231)q^{k+1}z^{n+1},

matching the enumeration in Theorem 1.

Thus, the distributions of both st and st^{∗} are in bijection with distributions of statistics over pattern-avoiding permutations whether we consider them over all Dyck paths or only over indecomposable Dyck paths.

4 Avoiding Two Patterns

We now consider a_{n,k}^{stat}(ρ_{1}, ρ_{2}) where stat ∈ {asc, des, dasc, ddes, pk, vl} and ρ_{1}, ρ_{2} ∈ S_{3}. Using the symmetries of reverse and complement, there are 6 pairs of patterns to consider: {123, 321}, {213, 312}, {132, 213}, {213, 231}, {123, 132}, and {132, 321}. Simion and Schmidt [10] determined |S_{n}(ρ_{1}, ρ_{2})| for each of these classes. We now use the permutation structures they determined to find a_{n,k}^{stat}(ρ_{1}, ρ_{2}) for our desired statistics. We already know that |S_{n}(123, 321)| = 0 for n ≥ 5, so there are 5 non-trivial pairs of permutation patterns to consider. A summary of the results of this section is given in Tables 3, 4, and 5. Just as many results for a_{n,k}^{stat}(ρ) with ρ ∈ S_{3} follow from bijections with Dyck paths, many results in this section follow from bijections with binary sequences.

We consider each pattern pair in turn.

4.1 Statistics on S_{n}(213, 312)

We first describe the structure of a {213, 312}-avoiding permutation. Let π ∈ S_{n}(213, 312). Suppose that π_{i} = n. Then π_{1} ⋯ π_{i−1} must form an increasing subpermutation (otherwise π has a 213 pattern), and π_{i+1} ⋯ π_{n} must form a decreasing subpermutation (otherwise π has

Patterns \Statistic  dasc  ddes
213,312  \begin{matrix}n, & k = 0; \\ \binom{n − 1}{k + 1}, & k ≥ 1. \end{matrix} \begin{matrix}n, & k = 0; \\ \binom{n − 1}{k + 1}, & k ≥ 1. \end{matrix}
132,213  \underline{A076791}  \underline{A076791}
213,231  \underline{A076791}  \underline{A076791}
123,132  trivial  \binom{n−2}{k} + 2\binom{n−3}{k}

132,321  \begin{matrix}1, & k = n − 2; \\ n, & k = n − 3; \\ \binom{n}{2} − n, & k = n − 4. \end{matrix}  trivial

Table 4: Distribution of dasc and ddes over pattern classes of the form S_{n}(ρ_{1}, ρ_{2}) with ρ_{1}, ρ_{2} ∈ S_{3}

Patterns \Statistic  pk  vl
213,312  \begin{matrix}2, & k = 0; \\ 2^{n−1} − 2, & k = 1. \end{matrix}  trivial
132,213  \binom{n}{2k+1}  \binom{n}{2k+1}
213,231  \binom{n}{2k+1}  \binom{n}{2k+1}
123,132  \binom{n}{2k+1}  2 · \binom{n−1}{2k}
132,321  \begin{matrix}n, & k = 0; \\ \binom{n − 1}{2}, & k = 1. \end{matrix} \begin{matrix}2, & k = 0; \\ \binom{n}{2} − 1, & k = 1. \end{matrix}

Table 5: Distribution of pk and vl over pattern classes of the form S_{n}(ρ_{1}, ρ_{2}) with ρ_{1}, ρ_{2} ∈ S_{3} a 312 pattern). There are \binom{n−1}{i−1} ways to choose the digits before π_{i} = n, so summing over all possible values for i, we have that |S_{n}(213, 312)| = ∑_{i=1}^{n} \binom{n−1}{i−1} = 2^{n−1}. This structure helps prove the following propositions.

Proposition 6.

a_{n,k}^{asc}(213, 312) = a_{n,k}^{des}(213, 312) = \binom{n − 1}{k}.

Proof. By the structure above, π ∈ S_{n}(213, 312) has k ascents if and only if π_{k+1} = n. There are \binom{n−1}{k} ways to determine the digits before π_{k+1}, which uniquely determines π.

Now, π ∈ S_{n} has k descents if and only if π has n − k − 1 ascents. There are \binom{n−1}{n−k−1} permutations π ∈ S_{n}(213, 312) with n − k − 1 ascents, so there are \binom{n−1}{n−k−1} = \binom{n−1}{k} such permutations with k descents.

Proposition 6 gives a new interpretation of Pascal’s triangle (\underline{A007318}).

Proposition 7. For n ≥ 1,

a_{n,k}^{dasc}(213, 312) = a_{n,k}^{ddes}(213, 312) = \begin{cases}n, & k = 0; \\ \binom{n−1}{k+1}, & k ≥ 1. \end{cases}

Proof. Suppose π ∈ S_{n}(213, 312) has no double ascents. Then either π_{1} = n or π_{2} = n. In other words, the digit π_{1} determines π, and there are n choices of π_{1}, so we have the first case.

Otherwise, if k ≥ 1, then π ∈ S_{n}(213, 312) has k double ascents if and only if π_{k+2} = n. There are \binom{n−1}{k+1} ways to determine the digits before π_{k+2}, which uniquely determines π.

Since reversing π is an involution on S_{n}(213, 312) that sends double ascents to double descents and vice versa, we get the same enumeration for a_{n,k}^{ddes}(213, 312).

While the triangle in Proposition 7 is straightforward to compute, it is new to OEIS and given in \underline{A299927}.

Proposition 8.

a_{n,k}^{pk}(213, 312) = \begin{cases}2, & k = 0; \\ 2^{n−1} − 2, & k = 1; \\ 0, & otherwise. \end{cases}

Proof. Consider π ∈ S_{n}(213, 312). By the structure described above, π has at most one peak, and if there is a peak, it must use n as its middle digit. There are two ways to not have a peak; namely, the increasing permutation where π_{n} = n and the decreasing permutation where π_{1} = n. All other 2^{n−1} − 2 permutation in S_{n}(213, 312) have one peak.

Proposition 9.

a_{n,k}^{vl}(213, 312) \begin{cases}2^{n−1}, & k = 0; \\ 0, & otherwise. \end{cases}

Proof. A valley is either a 213 pattern or a 312 pattern. By definition every permutation in S_{n}(213, 312) has 0 valleys.

4.2 Statistics on S_{n}(132, 213) and S_{n}(213, 231)

The pattern classes S_{n}(132, 213) and S_{n}(213, 231) provide the one non-trivial instance where a_{n,k}^{stat}(ρ_{1}, ρ_{2}) = a_{n,k}^{stat}(ρ′_{1}, ρ′_{2}) for the statistics of this paper.

We first describe the structure of a {132, 213}-avoiding permutation. Suppose π ∈ S_{n}(132, 213). Since π avoids 213, all digits before π_{i} = n must be in increasing order. Since π avoids 132, all digits before π_{i} = n are larger than all digits after n. These observations imply that if π ∈ S_{n}(132, 213), then π = I_{i_{1}} ⊖ ⋯ ⊖ I_{i_{m}} for some positive integers i_{1}, …, i_{m}. In fact, there is a natural bijection ϕ_{132,213} between S_{n}(132, 213) and binary sequences s = s_{1} ⋯ s_{n−1} of length n − 1; namely, if s = ϕ_{132,213}(π) then s_{i} = 1 when π_{i} < π_{i+1} and s_{i} = 0 when π_{i} > π_{i+1}. This bijection implies |S_{n}(132, 213)| = 2^{n−1}.

Next, we describe the structure of a {213, 231}-avoiding permutation. Suppose π ∈ S_{n}(213, 231). Then, for all i, either π_{i} = min(π_{i}, π_{i+1}, … π_{n}) or π_{i} = max(π_{i}, π_{i+1}, … π_{n}). If not, then π_{i} together with min(π_{i}, π_{i+1}, … π_{n}) and max(π_{i}, π_{i+1}, … π_{n}) form either a 213 pattern or a 231 pattern. Since there are two choices for each digit of π before the last digit, |S_{n}(213, 231)| = 2^{n−1}. In fact, there is a natural bijection ϕ_{213,231} from S_{n}(213, 231) to the set of binary sequences s = s_{1} ⋯ s_{n−1} of length n − 1; namely, s_{i} = 0 when π_{i} = max(π_{i}, π_{i+1}, … π_{n}) and s_{i} = 1 when π_{i} = min(π_{i}, π_{i+1}, … π_{n}).

Both bijections ϕ_{132,213} and ϕ_{213,231} help prove the following propositions.

Proposition 10.

a_{n,k}^{asc}(132, 213) = a_{n,k}^{des}(132, 213) = a_{n,k}^{asc}(213, 231) = a_{n,k}^{des}(213, 231) = \binom{n − 1}{k}.

Proof. By construction π ∈ S_{n}(132, 213) has an ascent at i if and only if s = ϕ_{132,213}(π) has s_{i} = 1. Therefore, a_{n,k}^{asc}(132, 213) is the number of binary sequences of length n − 1 with exactly k 1s, which is given by \binom{n−1}{k}. Also, a_{n,k}^{des}(132, 213) is the number of binary sequences of length n − 1 with exactly k 0s, which is given by \binom{n−1}{k}.

Similarly, π ∈ S_{n}(213, 231) has an ascent at i if and only if s = ϕ_{213,231}(π) has s_{i} = 1 and π has a descent at i if and only if s = ϕ_{213,231}(π) has s_{i} = 0, so the same enumerations follow.

Proposition 10 gives a new interpretation of Pascal’s triangle (\underline{A007318}).

Proposition 11.

a_{n,k}^{dasc}(132, 213) = a_{n,k}^{ddes}(132, 213) = a_{n,k}^{dasc}(213, 231) = a_{n,k}^{ddes}(213, 231)

and

∑_{n≥0} ∑_{k≥0} a_{n,k}^{ddes}(132, 213)q^{k}z^{n} = \frac{1 − qz}{1 − z − z^{2} − qz + qz^{2}} .

Proof. By construction π ∈ S_{n}(132, 213) has a double ascent at i if and only if s = ϕ_{132,213}(π) has s_{i} = s_{i+1} = 1 and π has a double descent at i if and only if s = ϕ_{132,213}(π) has s_{i} = s_{i+1} = 0. Similarly, π ∈ S_{n}(213, 231) has a double ascent at i if and s = ϕ_{213,231}(π) has s_{i} = s_{i+1} = 1 and a double descent at i if and only if s = ϕ_{213,231}(π) has s_{i} = s_{i+1} = 0. Therefore a_{n,k}^{dasc}(132, 213) = a_{n,k}^{ddes}(132, 213) = a_{n,k}^{dasc}(213, 231) = a_{n,k}^{ddes}(213, 231).

While there is not a straightforward closed formula, the number of binary strings with k 00 factors can be determined recursively.

Let a(n, k) be the number of strings of length n with k 00 factors, and then let a_{i}(n, k) be the number of strings of length n with exactly k 00 factors and that begin with i 0s. By definition

a_{n,k}^{ddes}(132, 213) = a(n − 1, k) = ∑_{i=0}^{n−1} a_{i}(n − 1, k).

First, consider the case when i = 0. We have a_{0}(n, k) = a(n − 1, k) since i = 0 implies the string must start with 1. The remaining n − 1 digits may be any string of length n − 1 with k 00 factors.

Now, for i ≥ 1, we have a_{i}(n, k) = a(n − 1 − i, k − (i − 1)). This is because the initial i digits of our string are 0. These 0s account for i − 1 00 factors. The next digit is a 1. The remaining n−1−i digits may be any binary string of length n−i with k −(i−1) 00 factors.

Together, we have:

a(n − 1, k) = ∑_{i=0}^{n−1} a_{i}(n − 1, k) = a(n − 2, k) + ∑_{i=1}^{n−1} a(n − 2 − i, k − (i − 1))

= a(n − 2, k) + ∑_{i=1}^{k+1} a(n − 2 − i, k − (i − 1)).

Equivalently:

a_{n,k}^{ddes}(132, 213) = a_{n−1,k}^{ddes}(132, 213) + ∑_{i=1}^{k+1} a(n − 1 − i, k − (i − 1)).

This recurrence implies that

∑_{n≥0} ∑_{k≥0} a_{n,k}^{ddes}(132, 213)q^{k}z^{n} = \frac{1 − qz}{1 − z − z^{2} − qz + qz^{2}} .

The number of binary sequences with exactly k 00 factors is given in OEIS entry \underline{A076791}, and Proposition 11 gives a new permutation statistic interpretation of the sequence.

Proposition 12.

a_{n,k}^{pk}(132, 213) = a_{n,k}^{vl}(132, 213) = a_{n,k}^{pk}(213, 231) = a_{n,k}^{vl}(213, 231) = \binom{n}{2k + 1}.

Proof. By construction π ∈ S_{n}(132, 213) has a peak at i if and only if s = ϕ_{132,213}(π) has s_{i} = 1 and s_{i+1} = 0 and π has a valley at i if and only if s = ϕ_{132,213}(π) has s_{i} = 0 and s_{i+1} = 1. By symmetry, a_{n,k}^{pk}(132, 213) = a_{n,k}^{vl}(132, 213). Similarly, π ∈ S_{n}(213, 231) has a peak at i if and only if s = ϕ_{213,231}(π) has s_{i} = 1 and s_{i+1} = 0 and a valley at i if and only if s = ϕ_{213,231}(π) has s_{i} = 0 and s_{i+1} = 1. Therefore, a_{n,k}^{pk}(132, 213) = a_{n,k}^{vl}(132, 213) = a_{n,k}^{pk}(213, 231) = a_{n,k}^{vl}(213, 231).

Let a(n, k) denote the number of binary sequences of length n with k 10 factors. We wish to determine a(n − 1, k).

Clearly a(n, 0) = n+1, since a binary sequence with no 10 factors consists of i 0s followed by n−i 1s, and there are n+1 choices for the value of i. On the other hand, a sequence with k 10 factors requires at least 2k digits, so if n < 2k, then a(n, k) = 0. Similarly, a(2k, k) = 1 corresponds to the 1 way to have a binary sequence of length 2k with k 10 factors, namely 1010 ⋯ 10.

Now that we have determined the boundary conditions, suppose that 0 < k < \frac{n−1}{2}. Now suppose s is a binary sequence of length n with k 10 factors. We call a position s_{i} a switch if s_{i} ≠ s_{i+1}. In all, a sequence of length n has n − 1 positions where a switch could occur.

If s starts with 1, the sequence switches from 1 to 0 k times and from 0 to 1 either k times or k − 1 times, so there are 2k or 2k − 1 switches. In the first case, there are \binom{n−1}{2k} ways to choose the locations of the switches and in the second case there are \binom{n−1}{2k−1} ways to choose the locations of the switches for a total of \binom{n−1}{2k} + \binom{n−1}{2k−1} = \binom{n}{2k} binary sequences of length n with k 10 factors that begin in 1.

If s starts with 0, the sequence switches from 1 to 0 k times and from 0 to 1 either k times or k + 1 times, so there are 2k or 2k + 1 switches. In the first case, there are \binom{n−1}{2k} ways to choose the locations of the switches and in the second case there are \binom{n−1}{2k+1} ways to choose the locations of the switches for a total of \binom{n−1}{2k} + \binom{n−1}{2k+1} = \binom{n}{2k+1} binary sequences of length n with k 10 factors that begin in 0.

Combining these two cases, we have that a(n, k) = \binom{n}{2k} + \binom{n}{2k+1} = \binom{n+1}{2k+1}. Therefore,

a_{n,k}^{pk}(132, 213) = a(n − 1, k) = \binom{n}{2k + 1}.

Proposition 12 gives a new interpretation of OEIS sequence \underline{A034867}.

4.3 Statistics on S_{n}(123, 132)

We first describe the structure of a {123, 132}-avoiding permutation. For π ∈ S_{n}(123, 132), either π_{n−1} = 1 or π_{n} = 1; otherwise, 1, π_{n−1} and π_{n} would form a forbidden pattern.

There is a natural bijection ϕ_{123,132} between S_{n}(123, 132) and binary sequences of length n − 1 that is described recursively as follows: ϕ_{123,132}(1) = ϵ, the empty string. Then, for π ∈ S_{n}(123, 132),

ϕ_{123,132}(π) = \begin{cases}ϕ_{123,132}(red(π_{1} ⋯ π_{n−2}π_{n}))0, & π_{n−1} = 1; \\ ϕ_{123,132}(red(π_{1} ⋯ π_{n−1}))1, & π_{n} = 1. \end{cases}

For example, ϕ_{123,132}(653241) = 11001. We can also read a binary string s of length n − 1 from left to right to construct the corresponding permutation ϕ_{123,132}^{−1}(s). Namely, begin with π^{(1)} = n. Then for 1 ≤ i ≤ n − 1, if s_{i} = 0, then π^{(i+1)} = π_{1}^{(i)} ⋯ π_{i−1}^{(i)}(n − i)π_{i}^{(i)}, and if s_{i} = 1, then π^{(i+1)} = π^{(i)}(n − 1). π = ϕ_{123,132}^{−1}(s) = π^{(n)}. Because of the bijection ϕ_{123,132} with binary strings, we have |S_{n}(123, 132)| = 2^{n−1}. We use this bijection to prove the following propositions.

Proposition 13.

a_{n,k}^{asc}(123, 132) = \binom{n}{2k}.

Proof. Suppose π ∈ S_{n}(123, 132) has k ascents and consider s = ϕ_{123,132}(π) and the sequence of partial permutations π^{(1)}, π^{(2)}, …, π^{(n)} where π^{(n)} = π. By construction, asc(π^{(i+1)}) = asc(π^{(i)}) or asc(π^{(i+1)}) = asc(π^{(i)}) + 1 for all i, so we seek to characterize factors in s that introduce a new ascent in π^{(i+1)} compared to π^{(i)}.

By construction, asc(π^{(1)}) = 0 and π^{(2)} has an ascent if and only if s_{1} = 0. For i ≥ 3, asc(π^{(i)}) = asc(π^{(i−1)}) + 1 if and only if s_{i−2} = 1 and s_{i−1} = 0.

Therefore, in order to determine a_{n,k}^{asc}(123, 132) we wish to count binary strings of length n − 1 that either begin with 0 and have k − 1 10 factors or that begin with 1 and have k 10 factors. As before, we call a position s_{i} a switch if s_{i} ≠ s_{i+1}, and in all, a sequence of length n − 1 has n − 2 positions where a switch could occur.

In the first case, since s_{1} = 0 and there are k − 1 switches from 1 to 0, there must be either k − 1 or k switches from 0 to 1 for a total of either 2k − 2 or 2k − 1 switches. In all there are \binom{n−2}{2k−2} + \binom{n−2}{2k−1} = \binom{n−1}{2k−1} such binary strings.

In the second case, since s_{1} = 1 and there are k switches from 1 to 0 there must be either k − 1 or k switches from 0 to 1 for a total of 2k − 1 or 2k switches. In all there are \binom{n−2}{2k−1} + \binom{n−2}{2k} = \binom{n−1}{2k} such binary strings.

Combining both cases, there are \binom{n−1}{2k−1} + \binom{n−1}{2k} = \binom{n}{2k} permutations of length n that avoid 123 and 132 and have exactly k ascents.

Proposition 13 gives an alternate interpretation to OEIS \underline{A034839}.

Proposition 14.

a_{n,k}^{des}(123, 132) = \binom{n}{2(n − k − 1)}.

Proof. For any permutation π ∈ S_{n}, asc(π) + des(π) = n − 1. Therefore, a permutation of length n with k descents has n − k − 1 ascents. By Proposition 13, a_{n,k}^{des}(123, 132) = \binom{n}{2(n−k−1)}.

Proposition 14 gives an alternate interpretation to OEIS \underline{A109446}, which is a symmetry of OEIS \underline{A034839}.

Proposition 15. For n ≥ 3

a_{n,k}^{dasc}(123, 132) = \begin{cases}2^{n−1}, & k = 0; \\ 0, & otherwise. \end{cases}

Proof. Since a consecutive 123 pattern is a double ascent, any permutation that avoids 123 has 0 double ascents.

Proposition 16. For n ≥ 3,

a_{n,k}^{ddes}(123, 132) = \binom{n − 2}{k} + 2\binom{n − 3}{k}.

Proof. For n ≤ 2, every permutation has 0 double descents, so we focus on the case where n ≥ 3. Similarly, no permutation has more than n − 2 double descents, so we focus on k ≤ n − 2.

Suppose π ∈ S_{n}(123, 132) has k ascents and consider s = ϕ_{123,132}(π) and the sequence of partial permutations π^{(1)}, π^{(2)}, …, π^{(n)} where π^{(n)} = π. By construction, ddes(π^{(i+1)}) = ddes(π^{(i)}) or ddes(π^{(i+1)}) = ddes(π^{(i)}) + 1 for all i, so we seek to characterize factors in s that introduce a new double descent in π^{(i+1)} compared to π^{(i)}.

By construction, ddes(π^{(1)}) = ddes(π^{(2)}) = 0 and π^{(3)} has a double descent if and only if s_{1} = s_{2} = 1. For i ≥ 4, ddes(π^{(i)}) = ddes(π^{(i−1)}) + 1 if and only if s_{i−2} = s_{i−1} = 1 or s_{i−2} = s_{i−1} = 0.

Therefore we wish to count the number of binary strings of length n − 1 that begin with 00 and have k additional 00 or 11 factors plus the number of binary strings of length n − 1 that do not begin with 00 and have k total 00 or 11 factors.

Now, suppose k = 0. By our characterization, there are exactly 3 such permutations. They correspond to ϕ_{123,132}^{−1}(0101 ⋯), ϕ_{123,132}^{−1}(1010 ⋯), and ϕ_{123,132}^{−1}(00101010 ⋯). This matches our formula above since \binom{n−2}{0} + 2\binom{n−3}{0} = 3 for n ≥ 3.

Notice that if k = n − 2 there is \binom{n−2}{n−2} + 2\binom{n−3}{n−2} = 1 permutation with n − 2 double descents, namely the strictly decreasing permutation, which corresponds to ϕ_{123,132}^{−1}(11 ⋯ 1).

Now, let a_{n,k} be the number of binary strings of length n with k 00 or 11 factors (other than a possible initial 00). We wish to determine a_{n−1,k}. Suppose n ≥ 4 and s = s_{1} ⋯ s_{n} is such a string. If s_{n−1} = s_{n} then s_{1} ⋯ s_{n−1} is a string of length n-1 with k −1 00 or 11 factors (other than a possible initial 00). If s_{n−1} ≠ s_{n}, then s_{1} ⋯ s_{n−1} is a string of length n-1 with k 00 or 11 factors (other than a possible initial 00). This implies that a_{n,k} = a_{n−1,k−1} + a_{n−1,k}.

We now proceed to show that a_{n,k} = \binom{n−1}{k}+2\binom{n−2}{k} by induction. We have confirmed this formula holds when when k = 0 and k = n−2. In particular, this implies a_{n,k} = \binom{n−1}{i}+2\binom{n−2}{i} for 0 ≤ i ≤ n − 1 for the case when n = 2.

Now, suppose that a_{n−1,i} = \binom{n−2}{i} + 2\binom{n−3}{i} for 0 ≤ i ≤ n − 2. We know that a_{n,k} = a_{n−1,k−1} + a_{n−1,k}. Therefore:

a_{n,k} = a_{n−1,k−1} + a_{n−1,k}

= \binom{n − 2}{k − 1} + 2\binom{n − 3}{k − 1} + \binom{n − 2}{k} + 2\binom{n − 3}{k}

= (\binom{n − 2}{k − 1} + \binom{n − 2}{k}) + 2 (\binom{n − 3}{k − 1} + \binom{n − 3}{k})

= \binom{n − 1}{k} + 2\binom{n − 2}{k},

which is what we wanted to show.

Proposition 16 gives a new interpretation of OEIS \underline{A093560}.

Proposition 17.

a_{n,k}^{pk}(123, 132) = \binom{n}{2k + 1}.

Proof. Suppose π ∈ S_{n}(123, 132) has k ascents and consider s = ϕ_{123,132}(π) and the sequence of partial permutations π^{(1)}, π^{(2)}, …, π^{(n)} where π^{(n)} = π. By construction, pk(π^{(i+1)}) = pk(π^{(i)}) or pk(π^{(i+1)}) = pk(π^{(i)}) + 1 for all i, so we seek to characterize factors in s that introduce a new peak in π^{(i+1)} compared to π^{(i)}.

By construction, pk(π^{(1)}) = pk(π^{(2)}) = 0. Also, for i ≥ 3, pk(π^{(i)}) = pk(π^{(i−1)}) + 1 if and only if s_{i−2} = 0 and s_{i−1} = 1. Therefore, we wish to count the number of binary strings s of length n − 1 with exactly k 01 factors. We have two cases.

If s begins with 0 then s switches from 0 to 1 k times and s switches from 1 to 0 either k − 1 times or k times for a total of 2k − 1 or 2k switches. There are \binom{n−2}{2k−1} + \binom{n−2}{2k} = \binom{n−1}{2k} sequences in this case.

If s begins with a 1 then s switches from 0 to 1 k times and s switches from 1 to 0 either k times or k + 1 times for a total of 2k or 2k + 1 switches. There are \binom{n−2}{2k} + \binom{n−2}{2k+1} = \binom{n−1}{2k+1} sequences in this case.

Combining both cases yields a total of \binom{n−1}{2k} + \binom{n−1}{2k+1} = \binom{n}{2k+1} binary sequences of length n − 1 with k 01 factors. By bijection ϕ_{123,132}, this implies a_{n,k}^{pk}(123, 132) = \binom{n}{2k+1}.

Proposition 17 gives a new interpretation of OEIS \underline{A034867}, which also appeared in Proposition 12.

Proposition 18.

a_{n,k}^{vl}(123, 132) = 2\binom{n − 1}{2k}.

Proof. Suppose π ∈ S_{n}(123, 132) has k ascents and consider s = ϕ_{123,132}(π) and the sequence of partial permutations π^{(1)}, π^{(2)}, …, π^{(n)} where π^{(n)} = π. By construction, vl(π^{(i+1)}) = vl(π^{(i)}) or vl(π^{(i+1)}) = vl(π^{(i)}) + 1 for all i, so we seek to characterize factors in s that introduce a new valley in π^{(i+1)} compared to π^{(i)}.

By construction, vl(π^{(1)}) = vl(π^{(2)}) = 0, and vl(π^{(3)}) = 1 if and only if s_{1} = 0 and s_{2} = 0. For i ≥ 4, vl(π^{(i)}) = vl(π^{(i−1)}) + 1 if and only if s_{i−2} = 1 and s_{i−1} = 0. Therefore, we wish to count the number of binary strings s of length n − 1 that either begin with 00 and have k − 1 10 factors or that don’t begin with 00 and have k 10 factors. We consider three cases: s begins with 1, s begins with 01, and s begins with 00.

If s_{1} = 1, there are k switches from 1 to 0 and either k − 1 or k switches from 0 to 1 for a total of 2k − 1 or 2k switches. There are \binom{n−2}{2k−1} + \binom{n−2}{2k} = \binom{n−1}{2k} such sequences of length n − 1.

If s_{1} = 0 and s_{2} = 1 there are still k switches from 1 to 0 and either k−1 or k switches from 0 to 1 after s_{2} for a total of 2k − 1 or 2k switches after s_{2}. There are \binom{n−3}{2k−1} + \binom{n−3}{2k} = \binom{n−2}{2k} such sequences of length n − 1.

If s_{1} = 0 and s_{2} = 0 there are k − 1 switches from 1 to 0 and either k − 1 or k switches from 0 to 1 for a total of 2k − 2 or 2k − 1 switches. There are \binom{n−3}{2k−2} + \binom{n−3}{2k−1} = \binom{n−2}{2k−1} such sequences of length n − 1.

Combining these cases yields

\binom{n − 1}{2k} + (\binom{n − 2}{2k} + \binom{n − 2}{2k − 1}) = \binom{n − 1}{2k} + \binom{n − 1}{2k} = 2\binom{n − 1}{2k}

such sequences.

Proposition 18 gives a new interpretation of OEIS \underline{A119462}.

4.4 Statistics on S_{n}(132, 321)

We first describe the structure of a {132, 321}-avoiding permutation.

Proposition 19. If π ∈ S_{n}(132, 321) then π = (I_{a} ⊖ I_{b}) ⊕ I_{n−a−b} for some 1 ≤ a ≤ n and 0 ≤ b ≤ n − 1.

Proof. We proceed by induction on n; that is, assume that every member of S_{n−1}(132, 321) is of the form (I_{a} ⊖ I_{b}) ⊕ I_{(n−1)−a−b} and prove this is the case for members of S_{n}(132, 321).

For the base case, notice that S_{1}(132, 321) = {1} and 1 = I_{1}, so the permutation 1 has the desired form where a = 1 and b = 0.

For the induction step, suppose π ∈ S_{n}(132, 321). This implies that π̂ = red(π_{1} ⋯ π_{n−1}) ∈ S_{n−1}(132, 321). By the induction hypothesis, either π̂ = I_{n−1}, π̂ = I_{a} ⊖ I_{n−1−a} or π̂ = (I_{a} ⊖ I_{b}) ⊕ I_{(n−1)−a−b}.

If π̂ = I_{n−1}, there are two choices for π_{n}. Either π_{n} = 1, which means π = I_{n−1} ⊖ I_{1} or π_{n} = n, which means π = I_{n}. Any other choice of π_{n} produces a 132 pattern involving π_{n}.

If π̂ = I_{a} ⊖ I_{n−1−a}, there are two choices for π_{n}. Either π_{n} = n − a which means π = I_{a} ⊖ I_{n−a} or π_{n} = n which means π = (I_{a} ⊖ I_{n−1−a}) ⊕ I_{1}. Any other choice of π_{n} produces a 132 pattern or a 321 pattern involving π_{n}.

If π̂ = (I_{a} ⊖ I_{b}) ⊕ I_{(n−1)−a−b}, then π_{n} = n which means (I_{a} ⊖ I_{b}) ⊕ I_{n−a−b}. Any other choice for π_{n} produces a 132 pattern or a 321 pattern.

As a consequence of Proposition 19, we have the following Corollary.

Corollary 20. |S_{n}(132, 321)| = \binom{n}{2} + 1.

Proof. The permutation I_{n} is in S_{n}(132, 321) for all n.

Otherwise, there are n positions in π. We may choose one position to be the last digit of I_{a} and a second position to be the last position of I_{b}. This choice of two positions uniquely determines the permutation. There are \binom{n}{2} permutations in S_{n}(132, 321) \ \{I_{n}\}.

The propositions below follow from the structure given in Proposition 19.

Proposition 21.

a_{n,k}^{asc}(132, 321) = \begin{cases}1, & k = n − 1; \\ \binom{n}{2}, & k = n − 2; \\ 0, & otherwise. \end{cases}

and

a_{n,k}^{des}(132, 321) = \begin{cases}1, & k = 0; \\ \binom{n}{2}, & k = 1; \\ 0, & otherwise. \end{cases}

Proof. We know π = (I_{a} ⊖ I_{b}) ⊕ I_{n−a−b}. If a = n, π has n − 1 ascents and 0 descents. Otherwise, the only descent in π is at position a, so π has n − 2 ascents and 1 descent.

Proposition 22.

a_{n,k}^{dasc}(132, 321) = \begin{cases}1, & k = n − 2; \\ n, & k = n − 3; \\ \binom{n}{2} − n, & k = n − 4; \\ 0, & otherwise. \end{cases}

Proof. We know π = (I_{a} ⊖ I_{b}) ⊕ I_{n−a−b}.

If a = n, π has n − 2 double ascents. There is one such permutation.

If a = n − 1 then b = 1. This means π has n − 3 double ascents in I_{a}. There is one such permutation.

If a = 1 then there are 0 double ascents in a and there are (n − 1) − 2 double ascents in I_{b} ⊕ I_{n−a−b} = I_{n−1} for a total of n − 3 double ascents. There are n − 1 such permutations since there are n − 1 choices for the value of b, i.e., 1 ≤ b ≤ n − 1.

So far we have accounted for 1 permutation with n−2 double ascents and 1+(n−1) = n permutations with n − 3 double ascents.

If 2 ≤ a ≤ n − 2, then π has a − 2 double ascents in I_{a} and (n − a) − 2 double ascents in I_{b} ⊕ I_{n−a−b} = I_{n−1} for a total of (a − 2) + (n − a − 2) = n − 4 double ascents. The remaining \binom{n}{2} − n permutations fall into this category, which completes the proof.

Proposition 23. For n ≥ 3,

a_{n,k}^{ddes}(132, 321) = \begin{cases}\binom{n}{2} + 1, & k = 0; \\ 0, & otherwise. \end{cases}

Proof. Since a consecutive 321 pattern is a double descent, any permutation that avoids 321 has 0 double descents.

Proposition 24.

a_{n,k}^{pk}(132, 321) = \begin{cases}n, & k = 0; \\ \binom{n−1}{2}, & k = 1; \\ 0, & otherwise. \end{cases}

Proof. There is at most one peak in a permutation of the form (I_{a} ⊖ I_{b}) ⊕ I_{n−a−b}. In particular, we get a peak exactly when 2 ≤ a ≤ n − 1.

There are n − 1 permutations where a = 1, and there is 1 permutation where a = n, so there are a total of n permutations with 0 peaks.

The remaining \binom{n}{2} + 1 − n = \binom{n−1}{2} permutations have one peak.

Proposition 25.

a_{n,k}^{vl}(132, 321) \begin{cases}2, & k = 0; \\ \binom{n}{2} − 1, & k = 1; \\ 0, & otherwise. \end{cases}

Proof. There is at most one valley in a permutation of the form (I_{a} ⊖ I_{b}) ⊕ I_{n−a−b}. In particular, we get a valley exactly when 2 ≤ n − a ≤ n − 1. The only permutations that violate this rule are when a = n and when a = n − 1. There is one permutation with a = n, i.e., I_{n}. There is one permutation with a = n − 1, i.e., I_{n−1} ⊖ I_{1}. All other \binom{n}{2} − 1 permutations avoiding 132 and 321 have a valley involving the last digit in I_{a} and the first two digits of I_{b} ⊕ I_{n−a−b}.

5 Acknowledgments

This work was partially supported by NSF grant DUE-1068346.

References

[1] M. Barnabei, F. Bonetti, and M. Silimbani, The descent statistic on 123 avoiding permutations, Sém. Lothar. Combin. 68 (2010), B63a.

[2] A. M. Baxter, Refining enumeration schemes to count according to permutation statistics, Electron. J. Combin. 21 (2014), #P2.50.

[3] T. Dokos, T. Dwyer, B. P. Johnson, B. E. Sagan, and K. Selsor, Permutation patterns and statistics. Discrete Math. 312 (2012), 2760–2775.

[4] S. Elizalde, Statistics on pattern-avoiding permutations, Ph.D. thesis, MIT, 2004.

[5] C. Krattenthaler, Permutations with restricted patterns and Dyck paths, Adv. Appl. Math. 27 (2001), 510–530.

[6] T. Mansour and A. Robertson, Refined restricted permutations avoiding subsets of patterns of length three, Ann. Comb. 6 (2003), 407–418.

[7] R. Pan, D. Qiu, and J. Remmel, Counting consecutive pattern matches in S_{n}(132) and S_{n}(123), Adv. Appl. Math. 105 (2019), 130–167.

[8] T. K. Petersen, Eulerian Numbers, Birkhäuser, 2015.

[9] A. Robertson, D. Saracino, and D. Zeilberger, Refined restricted permutations, Ann. Comb. 6 (2003), 427–444.

[10] R. Simion and F. W. Schmidt, Restricted permutations, European J. Combin. 6 (1985), 383–406.

[11] N. Sloane, The Encyclopedia of Integer Sequences, 2018. Available at https://oeis.

    org.

[12] FindStat, 2018. Available at http://findstat.org.

2010 Mathematics Subject Classification: Primary 05A05; Secondary 05A10, 05A15, 05A19. Keywords: permutation pattern, permutation statistic, Dyck path, ascent, descent, peak, valley.

(Concerned with sequences \underline{A000108}, \underline{A001263}, \underline{A007318}, \underline{A008292}, \underline{A034839}, \underline{A034867}, \underline{A076791}, \underline{A091156}, \underline{A091894}, \underline{A092107}, \underline{A093560}, \underline{A109446}, \underline{A119462}, \underline{A236406}, and \underline{A299927}.)

Received December 18 2018; revised version received March 25 2019. Published in Journal of Integer Sequences, March 28 2019.

Return to Journal of Integer Sequences home page.