Width-k Generalizations of Classical Permutation Statistics

Robert Davis Department of Mathematics Michigan State University East Lansing, MI 48824-1027 USA

                  davisr@math.msu.edu

Abstract

We introduce new natural generalizations of the classical descent and inversion statistics for permutations, called width-k descents and width-k inversions. These variations induce generalizations of the excedance and major statistics, providing a framework in which well-known equidistributivity results for classical statistics are paralleled. We explore additional relationships among the statistics providing specific formulas in certain special cases. Moreover, we explore the behavior of these width-k statistics in the context of pattern avoidance.

1 Introduction

Let 𝔖_{n} denote the set of permutations σ = a_{1} ⋯ a_{n} of [n] = {1, …, n}, and let 𝔖 = 𝔖_{1}∪𝔖_{2}∪ · · ·. A function st : 𝔖_{n} → ℕ is called a statistic, and the systematic study of permutation statistics is generally accepted to have begun with MacMahon [6]. In particular, four of the most well-known statistics are the descent, inversion, major, and excedance statistics, defined respectively by

des σ = |{i ∈ [n − 1] | a_{i} > a_{i+1}}|
inv σ = |{(i, j) ∈ [n]^{2} | i < j and a_{i} > a_{j}}|
maj σ = ∑_{i∈Des σ} i
exc σ = |{i ∈ [n] | a_{i} > i}|,

where Des σ = {i ∈ [n − 1] | a_{i} > a_{i+1}}.

Given any statistic st, one may form the generating function

F_{n}^{st}(q) = ∑_{σ∈𝔖_{n}} q^{st σ}.

A famous result due to MacMahon [6] states that F_{n}^{des}(q) = F_{n}^{exc}(q), and that both are equal to the Eulerian polynomial A_{n}(q). The Eulerian polynomials themselves may be defined via the identity

∑_{j≥0}(1 + j)^{n}q^{j} = \frac{A_{n}(q)}{(1 − q)^{n+1}} .

Another well-known result, due to MacMahon [5] and Rodrigues [7], states that F_{n}^{inv}(q) = F_{n}^{maj}(q) = [n]_{q}!. Foata famously provided combinatorial proofs of the equidistributivity of each; Lothaire [4] gives a treatment of these. Thus any statistic st for which F_{n}^{st}(q) = A_{n}(q) is called Eulerian, and if F_{n}^{st}(q) = [n]_{q}! then st is called Mahonian. These four statistics have many generalizations; in this article, we discuss new variations, induced from a simple generalization of des.

For each of the following definitions, we assume n ∈ ℤ_{>0}, k ∈ [n − 1], ∅ ≠ K ⊆ [n − 1], and σ = a_{1}a_{2} ⋯ a_{n} ∈ 𝔖_{n}. We define a width-k descent of σ to be an index i ⊆ [n − k] for which a_{i} > a_{i+k}. Thus the width-1 descents are the usual descents of a permutation. Let

Des_{k}(σ) = {i ∈ [n − k] | a_{i} > a_{i+k}}

denote the set of all width-k descents of σ, and set

des_{k}(σ) = | Des_{k}(σ)|.

If one is interested in descents of σ of various widths, first let K ⊆ [n − 1] denote the set of widths under consideration. Then, define Des_{K}(σ) to be the multiset ⋃_{k∈K} Des_{k}(σ), and des_{K}(σ) = | Des_{K}(σ)|.

Now, define a width-k inversion of σ to be a pair (i, j) for which a_{i} > a_{j} and j − i = mk for some positive integer m. Let

Inv_{k}(σ) = {(i, j) ∈ [n]^{2} | a_{i} > a_{j} and j − k = mk, k ∈ ℤ}

denote the set of width-k inversions of σ, and set

inv_{k}(σ) = | Inv_{k}(σ)|.

Again, one may be interested in width-k inversions for multiple values of k, so for K ⊆ [n−1] define Inv_{K}(σ) = ⋃_{k∈K} Inv_{k}(σ). Additionally, let inv_{K}(σ) = | Inv_{K}(σ)|.

Example 1. If σ = 4136572, then

Des_{{2,3}}(σ) = {1, 4, 5} and Inv_{{2,3}}(σ) = {(1, 3), (1, 7), (3, 7), (4, 7), (5, 7)}.

Thus, des_{{2,3}}(σ) = 3, inv_{{2,3}}(σ) = 5.

As we will see in the next section, the above definitions motivate us to generalize exc and maj in such a way that well-known known relationships among des, inv, maj, exc are paralleled. However, it is not very convenient to work with exc_{K} and maj_{K} directly. So, this paper will focus much more on des_{K} and inv_{K}.

The main focus of this paper is to explore these new statistics and their relationships among each other. While they are well-behaved for special cases of K ⊆ [n − 1], formulas for more general cases have been more elusive. Section 3 continues this exploration by considering the same statistics for classes of permutations avoiding a variety of patterns.

2 Main results

We begin with simple expressions for des_{K}(σ) and inv_{K}(σ) for a fixed σ ∈ 𝔖_{n}. First, we point out that if K ⊆ [n − 1], j ∈ K and ij ∈ K for some positive integer i, then for any σ ∈ 𝔖_{n}, inv_{K}(σ) = inv_{K\{ij}}(σ). This occurs because for any k ∈ [n − 1], inv_{k}(σ) counts all descents whose widths are multiples of k. Thus ij is already accounted for in inv_{K\{ij}}(σ). This follows quickly from the definitions of inv_{k} and des_{k}.

Proposition 2. For any nonempty K ⊆ [n − 1],

inv_{K}(σ) = ∑_{∅⊊K′⊆K}(−1)^{|K′|+1} inv_{lcm(K′)}(σ),

where we set inv_{lcm(K′)}(σ) = 0 if lcm(K′) ≥ n.

Proof. We first consider the case where K = {k}. The elements of Inv_{k}(σ) are pairs of the form (i, i + jk) for some positive integer j. Such an element exists if and only if there is a width-(jk) descent of σ at i. Thus, inv_{k}(σ) simply counts the number of width-jk descents of σ for all possible j. This leads to the equality

inv_{k}(σ) = ∑_{j≥1} des_{jk}(σ).

The formula for general K then follows from inclusion-exclusion: by adding the number of all width-k inversions for all k ∈ K, we are twice counting any instances of a width-lcm(k_{1}, k_{2}) inversion since such an inversion is also of widths k_{1} and k_{2}. If K contains three distinct elements k_{1}, k_{2}, k_{3}, then lcm(k_{1}, k_{2}, k_{3}) would have been added three times (once for each inv_{k_{i}}(σ)) and subtracted three times (once for each inv_{{k_{i},k_{j}}}(σ), i < j), so it must be added again for the sum. Extending this argument to range over larger subsets of K results in the claimed formula.

Example 3. Let us return to σ = 4136572. We saw from Example 1 that inv_{{2,3}}(σ) = 5, where four inversions have width 2 and two have width 3. But since the inversion (1, 7) has width both 2 and 3, it must also have width lcm(2, 3) = 6. So, it contributes two summands of 1 and one summand of −1.

We come now to a function which helps demonstrate the interactions among the width-k statistics. Let n and k be positive integers for which n = dk + r for some d, r ∈ ℤ with 0 ≤ r < k. To each σ = a_{1} ⋯ a_{n} ∈ 𝔖_{n} we may then associate the set of disjoint substrings β_{n,k}(σ) = {β_{n,k}^{1}(σ), …, β_{n,k}^{k}(σ)} where

β_{n,k}^{i}(σ) = \begin{cases}a_{i}a_{i+k}a_{i+2k} ⋯ a_{i+dk}, & if i ≤ r; \\ a_{i}a_{i+k}a_{i+2k} ⋯ a_{i+(d−1)k}, & if r < i < k. \end{cases}

Now, define

ϕ : 𝔖_{n} → 𝔖_{d+1}^{r} × 𝔖_{d}^{k−r}

by setting ϕ(σ) = (std β_{n,k}^{1}(σ), …, std β_{n,k}^{k}(σ)), where std is the standardization map, that is, the permutation obtained by replacing the smallest element of σ with 1, the second-smallest element with 2, etc. Note in particular that each std β_{n,k}^{i}(σ) is a permutation of [d + 1] or [d].

Example 4. Suppose that σ = 829317645, suppose k = 4. We then have

β_{9,4}(σ) = (std β_{9,4}^{1}(σ), std β_{9,4}^{2}(σ), std β_{9,4}^{3}(σ), std β_{9,4}^{4}(σ))
= (std 815, std 27, std 96, std 34)
= (312, 12, 21, 12).

The first of the identities in the following proposition was originally established by Sack and Úlfarsson [8], though with slightly different notation. We provide an alternate proof and extend their result to width-k inversions.

Theorem 5. Let n and k be positive integers such that n = dk + r, where 0 ≤ r < k, and let A_{i}(q) denote the i^{th} Eulerian polynomial. Also let M_{n,k} denote the multinomial coefficient

M_{n,k} = \binom{n}{(d + 1)^{∗r}, d^{∗(k−r)}}

where i^{∗j} indicates i repeated j times. We then have the identities

F_{n}^{des_{k}}(q) = M_{n,k}A_{d+1}^{r}(q)A_{d}^{k−r}(q)
F_{n}^{inv_{k}}(q) = M_{n,k}[d + 1]_{q}^{r}![d]_{q}^{k−r}!

Proof. Let k ∈ [n − 1] and consider ϕ defined above. Note that ϕ is an M_{n,k}-to-one function since, given (σ_{1}, …, σ_{k}) ∈ 𝔖_{d+1}^{r} × 𝔖_{d}^{k−r}, there are M_{n,k} ways to partition [n] into the subsequences β_{n,k}^{i}(σ) such that std β_{n,k}^{i}(σ) = σ_{i} for all i. Also note that

des_{k}(σ) = ∑_{i=1}^{k} des(std β_{n,k}^{i}(σ)).

Thus,

F_{n}^{des_{k}}(q) = ∑_{σ∈𝔖_{n}} q^{des_{k} σ}

= M_{n,k} (  ∑_{(σ_{1},...,σ_{k})∈𝔖_{d+1}^{r}×𝔖_{d}^{k−r}} q^{des σ_{1}} ⋯ q^{des σ_{k}} )

= M_{n,k}A_{d+1}^{r}(q)A_{d}^{k−r}(q).

This proves the first identity.

The second identity follows completely analogously, with the main modification being that an element of Inv_{k}(σ) corresponds to a usual inversion in some unique std β_{n,k}^{j}(σ).

We note that the sequences of coefficients of F_{n}^{des_{2}}(q) appear as OEIS sequence \underline{A180887}. No other nontrivial choice of k appears to have been studied before, for either des_{k} for inv_{k}.

Given des_{K} and inv_{K}, one must wonder what the corresponding generalizations of exc and maj are whose relationships with des_{K} and inv_{K} parallel that of the classical statistics. To do this, we define the multiset

Exc_{K}(σ) = ⋃_{k∈K} ⨄_{i=1}^{k}{{⌈j/k⌉ ∈ [n − 1] | ⌈j/k⌉ ∈ Exc(std β_{n,k}^{i}(σ))}}

and set exc_{K}(σ) = | Exc_{K}(σ)|, and also set

maj_{K}(σ) = ∑_{k∈K} ∑_{i∈Des_{k}(σ)} ⌈\frac{i}{k} ⌉ .

We could equivalently state that

maj_{K}(σ) = ∑_{k∈K} ∑_{i=1}^{k} maj(std β_{n,k}^{i}(σ)) and exc_{K}(σ) = ∑_{k∈K} ∑_{i=1}^{k} exc(std β_{n,k}^{i}(σ)).

These are exactly the definitions needed in order to obtain identities that parallel F_{n}^{des}(q) = F_{n}^{exc}(q) and F_{n}^{inv}(q) = F_{n}^{maj}(q), as we will soon see.

One important distinction to make between exc and exc_{K} is the following. If σ = a_{1}a_{2} ⋯ a_{n} and τ = b_{1}b_{2} ⋯ b_{n}, then even if a_{i} = b_{i} for some i, one cannot say i ∈ Exc_{K}(σ) if and only if i ∈ Exc_{K}(τ). For example, if σ = 4136572, then 1 ∈ Exc_{2}(σ), but if τ = 4153627 then 1 ∉ Exc_{2}(τ).

Example 6. Again let σ = 4136572. We then have

exc_{{2,3}}(σ) = |{{1, 3, 1, 2}}| = 4

and

maj_{\{2,3\}}(σ) = ⌈\frac{1}{2}⌉ + ⌈\frac{5}{2}⌉ + ⌈\frac{4}{3}⌉ = 6.

k  G_{6,k}(q)  G_{8,k}(q)  G_{9,k}(q)
1  6A_{5}(q)  8A_{7}(q)  9A_{9}(q)
2 180A_{2}(q)^{2}  1120A_{3}(q)^{2}  9q^{−1}A_{9}(q)
3  6!  8q^{−2}A_{7}(q)  45360A_{2}(q)^{3}
4 180q^{−2}A_{2}(q)^{2}  8!  9q^{−3}A_{9}(q)
5 6q^{−4}A_{5}(q)  8q^{−4}A_{7}(q)  9q^{−4}A_{9}(q)
6  1120q^{−4}A_{3}(q)^{2} 45360q^{−3}A_{2}(q)^{3}
7 8q^{−6}A_{7}(q) 9q^{−6}A_{9}(q)
8  9q^{−7}A_{9}(q)

Table 1: The polynomials G_{n,k}(q) for n = 6, 8, 9 and 1 ≤ k ≤ n.

By constructing a nearly identical argument as in the proof Theorem 5, and using the facts that F_{n}^{des}(q) = F_{n}^{exc}(q) and F_{n}^{inv}(q) = F_{n}^{maj}(q), we have the following corollary.

Corollary 7. The identities F_{n}^{des_{k}}(q) = F_{n}^{exc_{k}}(q) and F_{n}^{inv_{k}}(q) = F_{n}^{maj_{k}}(q) hold.

Now that we have established the analogous parallels between the four classical statistics and their width-k counterparts, we wish to explore what other structure is present. A simple proposition relates des_{k} and inv_{k} when k is large.

Corollary 8. For all k ≥ n/2, F_{n}^{des_{k}}(q) = F_{n}^{inv_{k}}(q).

Proof. Since k ≥ n/2, the sets β_{n,k}^{i}(σ) contain at most two elements. So, width-k descents and width-k inversions of σ are identical.

We now show that interesting behavior occurs when considering the function

G_{n,k}(q) = ∑_{σ∈𝔖_{n}} q^{des_{k}(σ)−des_{n−k}(σ)}.

According to computational data, the following conjecture holds for all n ≤ 9 and 1 ≤ k < n for which gcd(k, n) = 1.

Conjecture 9. If gcd(k, n) = 1, then G_{n,k}(q) = nq^{1−k}A_{n−1}(q).

Several illustrative polynomials are given in Table 2. This does not hold more generally, and it would be interesting to determine if a general formula exists.

Question 10. For which values of n, k does there exist a closed formula for G_{n,k}(q), and what is the formula?

3 Pattern avoidance

We say that a permutation σ ∈ 𝔖_{n} contains the pattern π ∈ 𝔖_{m} if there exists a subsequence σ′ of σ such that std(σ′) = π. If no such subsequence exists, then we say that σ avoids the pattern π. If Π ⊆ 𝔖, then we say σ avoids Π if σ avoids every element of Π. Let Av_{n}(Π) denote the set of all permutations of 𝔖_{n} avoiding Π. In a mild abuse of notation, if Π = {π}, we will write Av_{n}(π).

In this section, we consider the functions

F_{n}^{st}(Π; q) = ∑_{σ∈Av_{n}(Π)} q^{st σ},

which specializes to F_{n}^{st}(q) if Π = ∅. In most instances, F_{n}^{des_{k}} will be the main focus, but F_{n}^{des_{K}} and F_{n}^{inv_{k}} will also make appearances.

An important concept within pattern avoidance is that of Wilf equivalence. Two sets Π, Π′ ⊂ 𝔖 are said to be Wilf equivalent if | Av_{n}(Π)| = | Av_{n}(Π′)| for all n. In this case, we write Π ≡ Π′ to denote this Wilf equivalence, which is indeed an equivalence relation. For example, independent work of MacMahon and Knuth [3, 6] show that that whenever π, π′ ∈ 𝔖_{3}, then | Av_{n}(π)| = | Av_{n}(π′)| = C_{n}, where

C_{n} = \frac{1}{n + 1}\binom{2n}{n}

is the n^{th} Catalan number.

Proving whether Π ≡ Π′ is often quite difficult, and their Wilf equivalence does not imply that F_{n}^{st}(Π; q) = F_{n}^{st}(Π′; q). However, in some instances, the problems of establishing these identities have straightforward solutions by applying basic transformations on the elements of the avoidance classes. Given π = a_{1} ⋯ a_{n} ∈ 𝔖_{m}, let π^{r} denote its reversal and π^{c} denote its complement, respectively defined by

π^{r} = a_{m}a_{m−1} ⋯ a_{1} and π^{c} = (m + 1 − a_{1})(m + 1 − a_{2}) ⋯ (m + 1 − a_{m}).

Similarly, given Π ⊆ 𝔖, we let

Π^{r} = {π^{c} | π ∈ Π} and Π^{c} = {π^{r} | π ∈ Π}

be the reversal and complement of Π, respectively.

Our results of this section begin with a multivariate generalization of F_{n}^{st}(Π; q), and with showing how its specializations describe relationships among Π, Π^{r}, and Π^{c}.

Definition 11. Fix Π ⊆ 𝔖. Define

T_{n}(Π; t_{1}, …, t_{n−1}) = ∑_{σ∈Av_{n}(Π)} ∏_{k=1}^{n−1} t_{k}^{des_{k}(σ)}.

The function T_{n} specializes to F_{n}^{des_{K}}(Π; q) by setting t_{i} = q for i ∈ K and t_{i} = 1 for all i ∉ K. We can also recover F_{n}^{inv_{K}}(Π; q) from T_{n} by setting t_{i} = q whenever i ∈ [n − 1] ∩ kℤ for some k ∈ K, and setting t_{i} = 1 otherwise. Additionally, when Π = {π}, a nice duality appears, providing a mild generalization of [1, Lemma 2.1].

Proposition 12. For any Π ⊆ 𝔖, let Π′ denote either Π^{r} or Π^{c}. We then have

T_{n}(Π′; t_{1}, …, t_{n−1}) = t_{1}^{n−1}t_{2}^{n−2} ⋯ t_{n−1}T_{n}(Π; t_{1}^{−1}, …, t_{n−1}^{−1}).

Consequently,

T_{n}((Π^{r})^{c}; t_{1}, …, t_{n−1}) = T_{n}(Π; t_{1}, …, t_{n−1}).

Proof. It is enough to prove the claim when the set of patterns being avoided is {π} for some π ∈ 𝔖_{m}, since the full result follows by applying the argument to all elements of Π simultaneously.

First consider when π′ = π^{c} and σ ∈ Av_{n}(π). Because σ ∈ Av_{n}(π) if and only if σ^{c} ∈ Av_{n}(π^{c}), we have that for each k, i ∈ Des_{k}(σ) if and only if i ∉ Des_{k}(σ^{c}). This implies Des_{k}(σ^{c}) = [n − k] \ Des_{k}(σ), hence des_{k}(σ^{c}) = n − k − des_{k}(σ). So,

T_{n}(π^{c}; t_{1}, …, t_{n−1}) = ∑_{σ∈Av_{n}(π^{c})} ∏_{k=1}^{n−1} t_{k}^{des_{k}(σ)}

= ∑_{σ∈Av_{n}(π)} ∏_{k=1}^{n−1} t_{k}^{des_{k}(σ^{c})}

= ∑_{σ∈Av_{n}(π)} ∏_{k=1}^{n−1} t_{k}^{n−k−des_{k}(σ)}
= t_{1}^{n−1}t_{2}^{n−2} ⋯ t_{n−1}T_{n}(π; t_{1}^{−1}, …, t_{n−1}^{−1}).

Proving that the result holds for π′ = π^{r} follows similarly.

The second identity in the proposition statement holds by applying the first identity twice: first for Π^{r} and then for Π^{c}.

The above identities significantly reduce the amount of work needed to study F_{n}^{des_{K}}(Π; q) for all Π ⊆ 𝔖_{n}. For the remainder of this paper, we systematically approach Π for |Π| ≤ 2.

3.1 Avoiding singletons

By Proposition 12, we immediately get

F_{n}^{des_{k}}(123; q) = q^{n−k}F_{n}^{des_{k}}(321; q^{−1})

and

F_{n}^{des_{k}}(132; q) = F_{n}^{des_{k}}(213; q) = q^{n−k}F_{n}^{des_{k}}(231; q^{−1}) = q^{n−k}F_{n}^{des_{k}}(312; q^{−1}).

So, studying F_{n}^{des_{k}}(π; q) for π ∈ 𝔖_{3} reduces to studying the function for a choice of one pattern from {123, 321} and one from the remaining patterns. For some choices of Π, the permutations in Av_{n}(Π) are especially highly structured, which leads to similar arguments throughout the rest of this paper.

We begin with π = 312. Notice that if a_{1} ⋯ a_{n} ∈ Av_{n}(312) and a_{i} = 1, then we know std(a_{1} ⋯ a_{i−1}) ∈ Av_{i−1}(312), std(a_{i+1} ⋯ a_{n}) ∈ Av_{n−i}(312), and

max{a_{1}, …, a_{i−1}} < min{a_{i+1}, …, a_{n}}.

Proposition 13. For all n,

F_{n}^{des_{k}}(312; q) = ∑_{i=1}^{k} C_{i−1}F_{n−i}^{des_{k}}(312; q) + ∑_{i=k+1}^{n} qF_{i−1}^{des_{k}}(312; q)F_{n−i}^{des_{k}}(312; q)

where C_{i} is the i^{th} Catalan number.

Proof. First consider when σ = a_{1} ⋯ a_{n} ∈ Av_{n}(312) and a_{i} = 1 for some i ≤ k. By the discussion preceding this proposition, j ∉ Des_{k}(σ) for any j ≤ i. So, none of the C_{i−1} possible permutations that make up std(a_{1} ⋯ a_{i−1}) contribute to des_{k}(σ). The only contributions to des_{k}(σ) come from std(a_{i+1} ⋯ a_{n}) ∈ Av_{n−i}(312; q). The overall contribution to F_{n}^{des_{k}}(312; q) is the second summand of the identity.

Now suppose a_{i} = 1 for some i > k. Each choice of a_{1} ⋯ a_{i}, contributes to des_{k}(σ) as usual, but there will be an additional width-k descent produced at i − k. The elements a_{i+1} ⋯ a_{n} contribute to des_{k}(σ) as before. The overall contribution to F_{n}^{des_{k}}(312; q) is the first summand of the identity. Since we have considered all possible indices i for which we could have a_{i} = 1, we add the two cases together and are done.

Note that when we set q = 1, the above recursion specializes to the well-known recursion for Catalan numbers C_{n+1} = ∑_{i=0}^{n} C_{i}C_{n−i}. For more about the Catalan numbers see \underline{A000108}. Also, when k = 1, the coefficients of F_{n}^{des_{k}}(312; q) are the Narayana numbers, appearing in the OEIS as sequence \underline{A001263}. The sequence of coefficients of the polynomials F_{n}^{des_{n−1}}(312; q) appear as \underline{A026008}, where the coefficients are listed with the degree-1 summand first and then the constant term second.

We can use the previous proposition in conjunction with Proposition 12 to produce formulae for F_{n}^{des_{k}}(Π; q) and F_{n}^{inv_{k}}(Π; q) whenever Π is a single element of 𝔖_{3} other than 123 or 321. The only nontrivial work required, then, is to compute the degrees of the two polynomials.

Corollary 14. For all n,

deg F_{n}^{des_{k}}(312; q) = n − k and deg F_{n}^{inv_{k}}(312; q) = ∑_{i=1}^{n−k} ⌊\frac{n − i}{k}⌋ .

Proof. The degrees of the above polynomials are given by identifying a permutation in Av_{n}(312) with the most possible descents. This is satisfied by n(n − 1) ⋯ 21 ∈ Av_{n}(312) which has n − k descents of width k. Determining the number of width-k inversions in this permutation is done similarly.

Although 321 is Wilf equivalent to 312, it is not so obvious how to construct a recurrence relation for F_{n}^{des_{k}}(321; q) in general. In the special case of k = 1, the coefficients are given by sequence \underline{A166073}, but the coefficients for other k are not easily identifiable. To help describe the elements of Av_{n}(321), first let σ = a_{1} ⋯ a_{n} ∈ 𝔖 and call a_{i} a left-right maximum if a_{i} > a_{j} for all j < i. Thus σ ∈ Av_{n}(321) if and only if its set of non-left-right maxima form an increasing subsequence of σ. Indeed, if the non-left-right maxima did contain a descent, then there would be some left-right maximum preceding both elements, which violates the condition that σ avoid 321. Despite such a description, using it to reveal F_{n}^{des_{k}}(321; q) has thus far been unsuccessful. So, we leave the following as an open question.

Question 15. Is there a closed formula or simple recursion for F_{n}^{des_{k}}(321; q) (equivalently, for F_{n}^{des_{k}}(123; q))?

3.2 Avoiding doubletons

At this point, we begin studying the functions F_{n}^{des_{k}}(Π; q) when avoiding doubletons from 𝔖_{3}. Recall that, by the Erdős-Szekeres theorem [2], there are no permutations in 𝔖_{n} for n ≥ 5 that avoid both 123 and 321. Thus, we will not consider this pair. Additionally, the functions F_{n}^{inv_{k}}(Π; q) are quite unwieldy, so we will not consider these either.

For our first nontrivial example, we begin with {123, 132}. Permutations a_{1} ⋯ a_{n} ∈ Av_{n}(123, 132) have the following structure: for any i = 1, …, n, if a_{i} = n, then the substring a_{1}a_{2} ⋯ a_{i−1} is decreasing and consists of the elements from the interval [n − i + 1, n − 1]. Additionally, the substring a_{i+1} ⋯ a_{n} is an element of Av_{n−i}(123, 132). This structure makes it easy to show that there are 2^{n−1} elements of Av_{n}(123, 132) [9].

Proposition 16. For all n and 1 ≤ k ≤ n − 1,

F_{n}^{des_{k}}(123, 132; q) = ∑_{i=1}^{k} q^{min(i,n−k)}F_{n−i}^{des_{k}}(123, 132; q)

+ ∑_{i=k+1}^{n−k} q^{min(i−1,n−k−1)}F_{n−i}^{des_{k}}(123, 132; q)

+2^{n−max(k+1,n−k+1)}q^{n−k−1}.

Proof. Let σ = a_{1} ⋯ a_{n} ∈ Av_{n}(123, 132; q). If a_{i} = n for i ≤ k, then it is clear from the preceding description of the elements in Av_{n}(123, 132) that all of 1, …, min(i, n − k) are elements of Des_{k}(σ). If j > n − k for some j, then j ∉ Des_{k}(σ) since a_{j+k} does not exist.

The remaining elements of Des_{k}(σ) arise as a width-k descent of a_{i+1} ⋯ a_{n}, which accounts for the factor of F_{n−i}^{des_{k}}(123, 132; q) in the first summand.

Now, if k + 1 ≤ n − k and a_{i} = n for i = k + 1, …, n − k, then every element of 1, …, i except i−k is an element of Des_{k}(σ). If k+1 > n−k, then the second summand is empty and nothing is lost by continuing to the case of a_{i} = n for i ≥ max(k + 1, n − k + 1). Again, the remaining elements of Des_{k}(σ) are the width-k descents of a_{i+1} ⋯ a_{n}, hence the additional factor of F_{n−i}^{des_{k}}(123, 132; q). This accounts for the second summand.

Finally, let m = max(k + 1, n − k + 1). If a_{i} = n for i ≥ m, then all of 1, …, n − k are descents except i − k, and these are the only possible width-k descents. In particular, none of i + 1, i + 2, …, n can be the index for a width-k descent. This leads to the sum

∑_{i=m}^{n} q^{n−k−1}| Av_{n−i}(123, 132)| = (1 + ∑_{i=m}^{n−1} 2^{n−i−1}) q^{n−k−1} = 2^{n−m}q^{n−k−1},

which accounts for the third summand.

Again, the sequence of coefficients for k = 1 has appeared already, this time as sequence \underline{A109446}, but the sequences for nontrivial k > 1 appear to be entirely unstudied.

Next, we consider {123, 312}. We proceed similarly as before but with some minor differences, reflecting the new structure we encounter. If σ = a_{1} ⋯ a_{n} ∈ Av_{n}(123, 312) and a_{i} = 1 for some i < n, then σ is of the form

σ = i(i − 1) ⋯ 21n(n − 1) ⋯ (i + 2)(i + 1),

since neither subsequence a_{1} ⋯ a_{i−1} and a_{i+1} ⋯ a_{n} may contain an ascent. If a_{n} = 1, though, then std(a_{1} ⋯ a_{n−1}) ∈ Av_{n−1}(123, 312).

Proposition 17. For all n and 1 ≤ k < n,

F_{n}^{des_{k}}(123, 312; q) = ∑_{i=1}^{k} q^{max(0,n−k−i)} + ∑_{i=k+1}^{n−1} q^{max(n−2k,i−k)}
+qF_{n−1}^{des_{k}}(123, 312; q)

Proof. Suppose a_{i} = 1 for some i ≤ k. Using the description of elements in Av_{n}(123, 312), we know there are n − k − i width-k descents. Since there is only one such permutation for each i, we simply add all of the q^{n−k−i}, so long as n − k − i ≥ 0. If this inequality does not hold, then there are no width-k descents in this range. This accounts for the first summand.

The second summand is computed very similarly to that of the second summand in Proposition 16. The final summand is a direct result of noting that when a_{n} = 1, then (a_{1} − 1) ⋯ (a_{n−1} − 1) may be any element of Av_{n−1}(123, 312; q), which accounts for the factor F_{n−1}^{des_{k}}(123, 312; q). For each of these choices, we know n − k ∈ Des_{k}(σ), hence the factor of q. Adding the sums results in the identity claimed.

Now we consider {132, 231}. Note that if a_{1} ⋯ a_{n} ∈ Av_{n}(132, 231), then a_{i} ≠ n for any 1 < i < n. If a_{1} = n, then std(a_{2} ⋯ a_{n}) ∈ Av_{n−1}(132, 231), and similarly if a_{n} = n. Once again, this allows us to quickly compute that | Av_{n}(132, 231)| = 2^{n−1}.

Proposition 18. Let K = {k_{1}, …, k_{l}} be a nonempty subset of [n − 1] whose elements are listed in increasing order. We then have

F_{n}^{des_{K}}(132, 231; q) = ∏_{i=1}^{l+1}(1 + q^{i−1})^{k_{i}−k_{i−1}}

where k_{0} = 1 and k_{l+1} = n.

Proof. It follows from the description of elements in Av_{n}(132, 231) that there are two summands in a recurrence for F_{n}^{des_{K}}(132, 231; q): one corresponding to a_{1} = n and one corresponding to a_{n} = n. When a_{1} = n, then there are |K| = l copies of 1 ∈ Des_{K}(σ); if a_{n} = n, then a_{n} makes no contribution to Des_{K}(σ). Thus, by deleting n from σ, we get the recurrence

F_{n}^{des_{K}}(132, 231; q) = (1 + q^{l})F_{n−1}^{des_{K}}(132, 231; q).

Repeating this, a factor of 1 + q^{l} appears until we get to

F_{n}^{des_{K}}(132, 231; q) = (1 + q^{l})^{n−k_{l}}F_{k_{l}}^{des_{K}}(132, 231; q).

At this point, note that

F_{k_{l}}^{des_{K}}(132, 231; q) = F_{k_{l}}^{des_{K\{k_{l}}}}(132, 231; q).

Repeating the previous argument ends up with the identity claimed.

Next, consider {132, 213}. If σ = a_{1} ⋯ a_{n} ∈ Av_{n}(132, 213), then if a_{i} = n for any i, then a_{1} ⋯ a_{i−1} must be increasing in order to avoid 213. Moreover,

max(a_{i+1}, ⋯, a_{n}) < a_{1}

in order to avoid 132, and std(a_{i+1} ⋯ a_{n}) ∈ Av_{n−i}(132, 213).

Proposition 19. For all n and 1 ≤ k < n,

F_{n}^{des_{k}}(132, 213; q) = ∑_{i=1}^{k} q^{min(i,n−k)}F_{n−i}^{des_{k}}(132, 213; q)

+ ∑_{i=k+1}^{n−k} q^{min(k,n−i)}F_{n−i}^{des_{k}}(132, 213; q)

+ ∑_{i=max(k+1,n−k+1)}^{n} q^{n−i}F_{n−i}^{des_{k}}(132, 213; q).

Proof. The proof of this is entirely analogous to the proof of Proposition 16.

In this case, when k = 2, the sequence of coefficients as n grows is the sequence \underline{A208343}. No other nontrivial choice of k appears to have been previously studied. Additionally, for all remaining choices of Π we consider, the instances of previously-studied sequences appear to be only when k = 1.

Next, we consider {132, 312}. For each i = 1, …, n−1, either a_{i+1} = max{a_{1}, …, a_{i}}+1 or a_{i+1} = min{a_{1}, …, a_{i}} − 1. This doubleton often results in especially pleasant formulas, and our results are no exception.

Proposition 20. Let K = {k_{1}, …, k_{l}} be a nonempty subset of [n − 1] whose elements are listed in increasing order. We then have

F_{n}^{des_{K}}(132, 312; q) = ∏_{i=1}^{l+1}(1 + q^{i−1})^{k_{i}−k_{i−1}}

where k_{0} = 1 and k_{l+1} = n.

Proof. From the description of elements σ = a_{1} ⋯ a_{n} ∈ Av_{n}(132, 312), we know that either a_{n} = 1 or a_{n} = n. In the former case, n − k ∈ Des_{K}(σ) for each k ∈ K, and in the latter case, n − k ∉ Des_{K}(σ) for each k ∈ K. This leads to the recurrence

F_{n}^{des_{K}}(132, 312; q) = (1 + q^{l})F_{n−1}^{des_{K}}(132, 312; q).

Following an analogous argument as in the proof of Proposition 18 obtains the result.

From the general formula given above, we are able to quickly determine F_{n}^{inv_{k}}(132, 312; q).

Corollary 21. For fixed n, k, write n = dk + r for unique nonnegative integers d, r such that 0 ≤ r < k. We then have

F_{n}^{inv_{k}}(132, 312; q) = F_{n}^{inv_{k}}(132, 231; q) = 2^{k−1}(1 + q^{d})^{r} ∏_{i=1}^{d−1}(1 + q^{i})^{k}.

Proof. This is a direct consequence of the general formulas from Propositions 18 and 20, and recalling that

F_{n}^{inv_{k}}(Π; q) = F_{n}^{des_{[n−1]∩kℤ}}(Π; q).

4 Acknowledgments

The author thanks Bruce Sagan and the anonymous referee for their many helpful comments.

References

[1] Theodore Dokos, Tim Dwyer, Bryan P. Johnson, Bruce E. Sagan, and Kimberly Selsor, Permutation patterns and statistics, Discrete Math. 312 (2012), 2760–2775.

[2] Paul Erdős and George Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935), 463–470.

[3] Donald E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 2nd printing, Addison-Wesley, 1969.

[4] M. Lothaire, Combinatorics on Words, Vol. 17 of Encyclopedia of Mathematics and its Applications, Addison-Wesley, 1983.

[5] Percy A. MacMahon, The indices of permutations and the derivation therefrom of functions of a single variable associated with the permutations of any assemblage of objects, Amer. J. Math. 35 (1913), 281–322.

[6] Percy A. MacMahon, Combinatory Analysis, Chelsea Publishing Co., 1960.

[7] Olinde Rodrigues, Note sur les inversions, ou derangements produits dans les permutations, Journal de Mathématiques 4 (1839), 236–240.

[8] Joshua Sack and Henning Úlfarsson, Refined inversion statistics on permutations, Electron. J. Combin. 19 (1) (2012), Paper #P29.

[9] Rodica Simion and Frank W. Schmidt, Restricted permutations, European J. Combin. 6 (1985), 383–406.

2010 Mathematics Subject Classification: Primary 05A05; Secondary 05A15. Keywords: permutation statistics, pattern avoidance, generating function.

(Concerned with sequences \underline{A000108}, \underline{A001263}, \underline{A026008}, \underline{A109446}, \underline{A166073}, \underline{A180887}, and \underline{A208343}.)

Received January 19 2017; revised version received May 31 2017. Published in Journal of Integer Sequences, June 25 2017.

Return to Journal of Integer Sequences home page.