Pattern-Avoidance and Fuss–Catalan Numbers

Per Alexandersson Department of Mathematics

Stockholm University S-106 91 Stockholm Sweden

per.w.alexandersson@gmail.com

Samuel Asefa Fufa Department of Mathematics

Addis Ababa University

1176 Addis Ababa Ethiopia

samuel.asefa@aau.edu.et

Frether Getachew Kebede Department of Mathematics Addis Ababa University 1176 Addis Ababa Ethiopia

                                 frigetach@gmail.com

Dun Qiu Center for Combinatorics, LPMC Nankai University Tianjin 300071 P. R. China

                                 qiudun@nankai.edu.cn

Abstract

We study a subset of permutations where entries are restricted to having the same remainder as the index, modulo some integer k ≥ 2. We show that by also imposing the classical 132- or 213-avoidance restriction on the permutations, we recover the Fuss–Catalan numbers and some special cases of the Raney numbers.

Surprisingly, an analogous statement also holds when we impose the mod k restriction on a Catalan family of subexcedant functions.

Finally, we completely enumerate all combinations of mod-k-alternating permutations that avoid two patterns of length 3. This is analogous to the systematic study by Simion and Schmidt, of permutations avoiding two patterns of length 3.

1 Introduction

It is classically known that the number of permutations of length n avoiding a permutationpattern of length 3 is counted by the Catalan number, C_{n}. There is a plethora of other combinatorial objects that are counted by C_{n}; see, e.g., [18]. One classical Catalan family are the Dyck paths—paths using steps in {(1, 0), (0, 1)}, starting at (0, 0), ending at (n, n), and never going below the line y = x. This family can be generalized to counting paths that never go below y = kx and end at (kn, n) for some fixed positive integer k. The number of such paths is the Fuss–Catalan number:

C_{n}^{k+1} := \frac{1}{(k + 1)n + 1}\binom{(k + 1)n + 1}{n} = \frac{1}{kn + 1}\binom{(k + 1)n}{n}.

In this paper, we find several Fuss-generalizations of pattern-avoiding permutations by imposing additional restrictions on the entries in the permutations.

A parity-alternating permutation starting with an odd integer (PAP) sends even integers to even integers and odd integers to odd. This set of permutations has been studied previously in [19] when considering the ascent statistic and signed Eulerian numbers, and later in [6] where parity-alternating derangements are enumerated.

We generalize the notion of parity-alternating permutations to mod-k-alternating permutations. Here, we require that π_{i} is congruent to i (mod k), where k ≥ 1 is a fixed integer. This notion is not to be confused with the generalization in [13], where the size of blocks of entries with the same parity are restricted (but not restricted to be 1).

We enumerate the mod-k-alternating permutations under pattern-avoidance, for each of the patterns in {132, 213, 231, 312}. Moreover, we also enumerate the mod-k-alternating permutations that avoid two patterns of length 3. The number of mod-k-alternating permutations of length n avoiding σ is denoted 𝔪𝔭_{σ}(n, k).

We also consider subexcedant functions. These are simply words of positive integers, f_{1}, f_{2}, …, f_{n}, such that f_{i} ≤ i. There is a (specific) bijection between permutations of length n and subexcedant functions of length n (introduced in [12]) so one can study subexcedant functions instead of permutations. The mod-k-alternating restriction translates under this bijection to the exact same restriction on the subexcedant function. In other words, f_{i} ≡ i (mod k); see Proposition 20.

1.1 Main results

In Section 4 we prove the following theorem. In particular, this shows that 𝔪𝔭_{σ}(n, k) is a Raney number and that 𝔪𝔭_{σ}(km, k) is a Fuss–Catalan number.

Theorem 1 (Corollary 15 below). Let σ ∈ {132, 213} and n, k ≥ 1. Let m and j be defined via n = km + j with 0 ≤ j < k. Then

𝔪𝔭_{σ}(n, k) = \frac{j + 1}{km + j + 1}\binom{(k + 1)m + j}{km + j}.

In particular

𝔪𝔭_{σ}(km, k) = \frac{1}{(k + 1)m + 1}\binom{(k + 1)m + 1}{m} = \frac{1}{km + 1}\binom{(k + 1)m}{m}.

In Section 5, we prove our second main result. We let 𝔪𝔭_{C}(n, k) denote the set of modk-alternating permutations whose subexcedant function satisfy the following two properties:

• f_{i} ≡ i (mod k),

• 1 ≤ f_{i} ≤ f_{i−1} + 1 for all i ∈ {2, 3, …, n}.

The first property is analogous to the mod-k-alternating property on permutations. Subexcedant functions that satisfy the second property are enumerated by the Catalan numbers. The second condition is therefore a natural analog to permutations avoiding a fixed-length-3 pattern. We have the following result:

Theorem 2 (Corollary 28 below). Let m and j be defined via n = km + j with 0 ≤ j < k. Then

𝔪𝔭_{C}(n, k) = \frac{j + 1}{km + j + 1}\binom{(k + 1)m + j}{km + j}

and in particular

𝔪𝔭_{C}(km, k) = \frac{1}{(k + 1)m + 1}\binom{(k + 1)m + 1}{m} = \frac{1}{km + 1}\binom{(k + 1)m}{m}.

We prove these two enumerative results by showing that the combinatorial objects satisfy certain recursions. These recursions can then be used to produce a canonical bijection between 𝔪𝔭_{132}(n, k) and 𝔪𝔭_{C}(n, k), for example. However, this bijection is not a restriction of any classical bijection that sends subexcedant functions to permutations.

Finally, in Section 6 we systematically enumerate all families of mod-k-alternating permutations avoiding two (different) patterns of length 3.

2 Preliminaries

Given a word w = [w_{1}, …, w_{ℓ}] and an integer n, we let n + w denote the word

[w_{1} + n, w_{2} + n, …, w_{ℓ} + n].

This convention is extended to the expressions w − n and n − w in a natural manner. If α = [α_{1}, …, α_{r}] and β = [β_{1}, …, β_{s}] are words, then [α, β] denotes the concatenation [α_{1}, …, α_{r}, β_{1}, …, β_{s}]. We use several variants of this convention. We use the term subword to denote a sequence of consecutive entries in a word.

The set {1, 2, …, n} is denoted by [n] (the context should make it clear that this is not to be interpreted as the word of one letter). The set of permutations of [n] is denoted by S_{n}. We use brackets for permutations in one-line notation and regular parenthesis to denote cycles. We make use of four well-known involutions on S_{n}, inverse, reverse, flip, and revflip; for π = [π_{1}, …, π_{n}] ∈ S_{n}, we let

rev(π) := [π_{n}, π_{n−1}, …, π_{1}], flip(π) := n + 1 − π, and revflip(π) := flip(rev(π)).

For permutations π, ω ∈ S_{n}, we think of multiplication as a composition of functions so that (π∘ω)(k) = π(ω(k)) whenever 1 ≤ k ≤ n. Given π, we associate it with its permutation matrix;

M_{π} := (δ_{i,π(j)})_{1≤i,j≤n}.

The permutation matrix of the composition π ∘ ω is M_{π}M_{σ}. We follow the convention in [7] and illustrate permutation matrices by letting row indices start at the bottom, as in Figure 1. From now on, this is the picture we have in mind when referring to permutation matrices.

M_{π} = (\begin{matrix}0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}) \begin{aligned}8 & & • \\ 7 & & & & & • \\ 6 & & & & & & & • \\ 5 & & & • \\ 4 & & & & & & • \\ 3 & & & & • \\ 2 & & & & & & & & • \\ 1 & • \\ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \end{aligned}

Figure 1: The permutation matrix M_{π} associated with π = [1, 8, 5, 3, 7, 4, 6, 2], where the bottom row is the first row. The rightmost figure is simply the graph of the function i ↦ π(i) in Cartesian coordinates.

2.1 Permutation patterns

A permutation π ∈ S_{n} is said to contain the pattern σ ∈ S_{k} if there is a subsequence of π that is order-isomorphic to σ. Otherwise, π is said to avoid σ and S_{σ}(n) denotes the set of σ-avoiding permutations over [n]. We simply write the pattern as a word. For example, π = [1, 8, 5, 3, 7, 4, 6, 2] contains the pattern 231 as the subsequence 3, 6, 2 in π. However, [1, 7, 6, 4, 2, 3, 5, 8] avoids the pattern 231.

A pattern of length 3 is the first non-trivial case to consider and we use a one-line notation without the parentheses to represent such a pattern. In Figure 3, we show the structure of 132-avoiding permutations. Any permutation of length n avoiding the pattern 132 must be of the form

π = [α_{1}, …, α_{j}, n, β_{1}, …, β_{n−1−j}],

M_{π} = • ; • ; ∗ ; • ; • ; ∗ ; ∗ ; • M_{σ} = ∗ ; ∗ ; ∗

Figure 2: The permutation matrices associated with π = [1, 8, 5, 3, 7, 4, 6, 2] and σ = 231. Here we see that π contains the pattern σ (there are other instances of this pattern in π).

n

Figure 3: The structure of a permutation matrix that avoids the pattern 132. The larger regions on the left and right are also 132-avoiding which explains the “Catalan structure”.

where min(α_{1}, …, α_{j}) > max(β_{1}, …, β_{n−1−j}).

Permutations avoiding one pattern of length 3 have been studied extensively and it is well-known (first proved by Knuth [8, 9]) that for all n ≥ 0, we have

|S_{123}(n)| = |S_{132}(n)| = |S_{213}(n)| = |S_{231}(n)| = |S_{312}(n)| = |S_{321}(n)| = \frac{1}{n + 1}\binom{2n}{n}.

For patterns σ of length 3, the inverse map, the rev map, and the revflip map are bijections between some of the sets S_{σ}(n); see Figure 4.

3 Fuss–Catalan numbers and Raney numbers

The main result in this section is Proposition 3, where we give a closed-form formula for numbers a_{k}(n) (defined in (1) below) that generalize the Fuss–Catalan numbers. The recurrence defining the a_{k}(n) shows up in several places in the later sections.

The Fuss–Catalan numbers, C_{n}^{p}, generalize the classical Catalan numbers. Note that for p = 2 we recover the classical Catalan numbers; see Table 1. There is an extensive literature on Catalan numbers and we refer readers to Stanley’s large collection of Catalan objects and information [18].

If we set

F_{p}(z) := ∑_{n≥0} \frac{1}{pn + 1}\binom{pn + 1}{n}z^{n},

then Lambert [10, 11] proved that

F_{p}(z) = 1 + z(F_{p}(z))^{p}.

A modern proof can be found in [4, Eq. 7.68]. It follows that for all α ∈ ℕ_{≥0}^{p}, we have

C_{n}^{p} = ∑_{α} C_{α_{1}}^{p} · C_{α_{2}}^{p} · · · · · C_{α_{p}}^{p} C_{0}^{p} = 1,

where the sum of the entries in α equals n − 1. Note that this relation uniquely defines the sequence (C_{n}^{p})_{n≥0}.

132 213 231 312 321 123 revflip inverse inverse revflip inverse rev rev revflip revflip

Figure 4: Bijections between sets of permutations that avoid a pattern of length 3; see [16] for details. There are more well-known bijections but the ones shown above also respect the parity-alternating property.

The Fuss–Catalan numbers can be modeled as the number of non-crossing partitions of certain polygons using (p + 1)-gons; see [3, p. 78]. Another interpretation using lattice paths was mentioned in the introduction.

1 2 3 4  5  6  7  8
C_{n}^{1} 1 1 1 1  1  1  1  1
C_{n}^{2} 1 2 5 14 42 132  429  1430
C_{n}^{3} 1 3 12 55 273 1428 7752 43263
C_{n}^{4} 1 4 22 140 969 7084 53820 420732
C_{n}^{5} 1 5 35 285 2530 23751 231880 2330445
Table 1: The values of C_{n}^{p}, with n = 1, 2, …, 8 and p = 1, 2, …, 5.

The Raney numbers (introduced in [15]) may be defined as

R_{m}(p, r) := \frac{r}{mp + r}\binom{mp + r}{m}

and are sometimes called the two-parameter Fuss–Catalan numbers. Note that C_{n}^{p} = R_{n}(p, 1), so the Raney numbers contain the Fuss–Catalan numbers as a sub-family.

Proposition 3. Fix k ∈ ℕ and let the sequence (a_{k}(n))_{n=0}^{∞} be defined by the recursion

a_{k}(n + 1) = ∑_{\begin{matrix}0≤i≤n \\ k|i \end{matrix}} a_{k}(i)a_{k}(n − i),  a_{k}(0) := 1.  (1)

The closed-form expression for a_{k}(n) is then given by

a_{k}(km + j) = \frac{j + 1}{km + j + 1}\binom{(k + 1)m + j}{km + j}  (2)

where we write n = km + j with 0 ≤ j < k. In particular,

a_{k}(km + j) = R_{m}(k + 1, j + 1) and a_{k}(km) = C_{m}^{k+1}  (3)

so the a_{k}(n) form a sub-family of the Raney numbers, which includes the Fuss–Catalan numbers.

Proof. Let us first set

A_{k}(t) := ∑_{m≥0} a_{k}(km)t^{m} and B_{k,j}(t) := ∑_{m≥0} a_{k}(km + j)t^{m} for 0 ≤ j ≤ k.

Our first goal is to obtain functional equations for the B_{k,j}(t). We shall first prove that

B_{k,j}(t) = (A_{k}(t))^{j+1}  and  A_{k}(t) = 1 + t · (A_{k}(t))^{k+1}.  (4)

Let j now be fixed with 1 ≤ j ≤ k. The recursion in (1) can then be rewritten as

∑_{m≥0} a_{k}(km + j)t^{m} = ∑_{m≥0} t^{m} ∑_{i} a_{k}(ki) · a_{k}(km + j − 1 − ki)

by first substituting n ↦ km + j − 1 and then multiplying by t^{m} on both sides followed by summing over m. We then have

B_{k,j}(t) = ∑_{m≥0} ∑_{i} a_{k}(ki)t^{i} · a_{k}(km − ki + j − 1)t^{m−i} = A_{k}(t) · B_{k,j−1}(t).

A simple inductive argument over j concludes the proof and the first set of relations in (4) is established. On one hand, we now have B_{k,k}(t) = (A_{k}(t))^{k+1}. On the other hand, the definition of the B_{k,j} tells us that 1 + tB_{k,k}(t) = A_{k}(t). So

A_{k}(t) = 1 + t(A_{k}(t))^{k+1}

which is the second relation in (4).

Recall that Lagrange inversion (see [20, Thm. 5.1.1]) states that if x(t) satisfies the functional equation x(t) = t · ϕ(x(t)) with ϕ(0) ≠ 0, then

f(x(t))|_{t^{n}} = \frac{1}{n}f′(x)ϕ(x)^{n}|_{x^{n−1}}.  (5)

The recursion for A_{k}(t) we had before is precisely of the form x(t) = t · ϕ(x(t)) when x(t) = A_{k}(t) − 1, f(x) = 1 + x and ϕ(x) = (1 + x)^{k+1}. Hence, Lagrange inversion gives

A_{k}(t)|_{t^{m}} = \frac{1}{m}(1 + x)^{(k+1)m}|_{x^{m−1}},

which gives the j = 0 case of (2).

If we instead choose f(x) = (1 + x)^{j+1} but keep x(t) = A_{k}(t) − 1 and ϕ(x) = (1 + x)^{k+1} in (5), then

B_{k,j}(t)|_{t^{m}} = (A_{k}(t))^{j+1}|_{t^{m}} = \frac{j + 1}{m}(1 + x)^{(k+1)m+j}|_{x^{m−1}} = \frac{j + 1}{m}\binom{(k + 1)m + j}{m − 1}.

This proves the remaining cases in (2).

Lemma 4. For a fixed r in {0, 1, …, k − 1} and m ≥ 1, we have

a_{k}(km) = ∑_{j=0}^{m−1} a_{k}(kj + r)a_{k}(k(m − j) − r − 1)  (6)

where a_{k}(n) is the sequence in Proposition 3.

Proof. In the notation of Proposition 3 it is straightforward to prove that

A_{k}(t) = 1 + tB_{k,r}(t)B_{k,k−1−r}(t)

by using (4). Comparing coefficients now gives the desired formula.

4 Mod-k-alternating permutations and pattern avoidance

4.1 Mod-k-alternating permutations

Let P(n) denote the set of parity alternating permutations (PAP) starting with an odd entry and let 𝔭(n) be the cardinality of P(n). Moreover, we let P_{σ}(n) be the set of PAPs avoiding the permutation pattern σ. We also let P_{σ,τ}(n) be the set of PAPs avoiding patterns σ and τ.

Similarly, P^{∗}(n) denotes the set of parity-alternating permutations starting with an even entry; P_{σ}^{∗}(n) and P_{σ,τ}^{∗}(n) are defined analogously.

The following lemma is straightforward to verify.

Lemma 5. For m ≥ 0, the maps

rev : P_{132}(2m) → P_{231}^{∗}(2m)
rev : P_{231}(2m) → P_{132}^{∗}(2m)
rev : P_{132}(2m + 1) → P_{231}(2m + 1)
rev : P_{231}(2m + 1) → P_{132}(2m + 1)

are bijections.

For instance, 34561278 is mapped to 87216543, and 5234167 is mapped to 7614325 under the reverse map. Note that 34561278 and 5234167 are 132-avoiding and 87216543 and 7614325 are 231-avoiding.

Definition 6. Given k ≥ 2, a mod-k-alternating permutation of size n is a permutation π ∈ S_{n} such that

π(i) ≡ i (mod k) for all i = 1, 2, …, n.

Let MP(n, k) be the set of such mod-k-alternating permutations and we set

MP_{σ}(n, k) := MP(n, k) ∩ S_{σ}(n).

Note that it can be easily seen that MP(n, k) is closed under compositions and taking inverses, so that it is a subgroup of S_{n}.

For k = 2 we recover the classical parity-alternating permutations starting with an odd integer. Note that

𝔪𝔭(n, k) := |MP(n, k)| = (⌈\frac{n}{k}⌉!)^{j}(⌊\frac{n}{k}⌋!)^{k−j}

where j is the remainder when n is divided by k. We set 𝔪𝔭_{σ}(n, k) := |MP_{σ}(n, k)|.

Example 7. For example, MP(7, 3) has (3!)^{1} · (2!)^{2} = 24 elements:

[1, 2, 3, 4, 5, 6, 7] [1, 2, 6, 4, 5, 3, 7] [1, 5, 3, 4, 2, 6, 7] [1, 5, 6, 4, 2, 3, 7] [1, 2, 3, 7, 5, 6, 4]
[1, 2, 6, 7, 5, 3, 4] [1, 5, 3, 7, 2, 6, 4] [1, 5, 6, 7, 2, 3, 4] [4, 2, 3, 1, 5, 6, 7] [4, 2, 6, 1, 5, 3, 7]
[4, 5, 3, 1, 2, 6, 7] [4, 5, 6, 1, 2, 3, 7] [4, 2, 3, 7, 5, 6, 1] [4, 2, 6, 7, 5, 3, 1] [4, 5, 3, 7, 2, 6, 1]
[4, 5, 6, 7, 2, 3, 1] [7, 2, 3, 1, 5, 6, 4] [7, 2, 6, 1, 5, 3, 4] [7, 5, 3, 1, 2, 6, 4] [7, 5, 6, 1, 2, 3, 4]
[7, 2, 3, 4, 5, 6, 1] [7, 2, 6, 4, 5, 3, 1] [7, 5, 3, 4, 2, 6, 1] [7, 5, 6, 4, 2, 3, 1].

We shall also introduce some notation for mod-k-alternating permutations starting with the remainder r mod k.

Definition 8. Let MP(n, k, r) denote the set of permutations of length n that satisfy

π(i) ≡ (r + i − 1) (mod k)  for all 1 ≤ i ≤ n.  (7)

Moreover, we set MP_{σ}(n, k, r) := MP(n, k, r) ∩ S_{σ}(n), 𝔪𝔭(n, k, r) := |MP(n, k, r)|, and 𝔪𝔭_{σ}(n, k, r) := |MP_{σ}(n, k, r)|.

Lemma 9. We have 𝔪𝔭(n, k, r) = 0 unless r = 1 or n = mk for some integer m.

Proof. Suppose 2 ≤ r ≤ k and π ∈ MP(n, k, r). By (7), the number of positions in π where the entry has a remainder r always exceeds the number of entries with a remainder r − 1, unless n is a multiple of k. This is due to the fact that the first position has a remainder r, so that the remainders must form the pattern

[r, r + 1, r + 2, …, 0, 1, …, r − 1, r, …].

Now, the number of entries with index equal to r mod k is never larger than the number of entries with index equal to r − 1 mod k. This is because the entries are from [n]. Since these two counts must agree for π, the statement follows.

Lemma 10. The cardinality of MP(nk, k, r) is (n!)^{k}.

Proof. This is straightforward.

Lemma 11. We have 𝔪𝔭_{σ}(n, k) = 𝔪𝔭_{revflip(σ)}(n, k). Moreover,

𝔪𝔭_{σ}(n, k, r) = 𝔪𝔭_{revflip(σ)}(n, k, 2 − r).  (8)

In particular, 𝔪𝔭_{132}(n, k) and 𝔪𝔭_{213}(n, k) have the same cardinality.

Proof. Note that it is enough to prove (8), and that it suffices to show that

revflip : MP_{σ}(n, k, r) → MP_{revflip(σ)}(n, k, 2 − r)

is a bijection.

For π ∈ MP_{σ}(n, k, r), we have that the last element in π has remainder r − 1 + n mod k. Hence, the first element of revflip(π) has remainder n + 1 − (r − 1 + n) = 2 − r mod k. The remaining properties are now straightforward to verify; that is,

revflip(π) ∈ MP_{revflip(σ)}(n, k, 2 − r).

Lemma 12. We have 𝔪𝔭_{σ}(n, k) = 𝔪𝔭_{σ^{−1}}(n, k).

Proof. We have π ∈ S_{σ}(n) ⟺ π^{−1} ∈ S_{σ^{−1}}(n) (this is classical; see [16, Lem. 1]) so π ∈ MP_{σ}(n, k) holds if and only if π^{−1} ∈ MP_{σ^{−1}}(n, k).

Proposition 13. For k ≥ 3 and n ≥ 1 we have

𝔪𝔭_{312}(n, k, r) = \begin{cases}1, & if r = 1; \\ 2^{n/k−1}, & if r = 2 and k | n; \\ 0, & otherwise. \end{cases}  (9)

Note that by Lemma 11, a corresponding statement holds for the pattern 231.

Proof. We shall prove the stronger statement that MP_{312}(n, k, 1) consists of only the identity permutation.

We proceed by induction over n and assume that the statement in (9) is true for permutations of length less than n; the base cases n = 1 and n = 2 are straightforward to verify. Note that since k ≥ 3, r = 0 and r = 2 are different cases.

Suppose that π ∈ MP_{312}(n, k, r) is of the form

π = [α, 1, β]  (10)

for some n ≥ 3.

Case r = 1. If α is the empty sequence, then [β − 1] ∈ MP_{312}(n − 1, k, 1) which must be the identity permutation by induction. Hence, we can assume that the length, say s, of α is greater than 0 and we must therefore have n ≥ k + 1.

Since π avoids 312, we have max(α) < min(β). In particular, α is constructed from

{2, 3, …, s + 1}.

So [α, 1] ∈ MP_{312}(s + 1, k, 1).

On the other hand, β consists of numbers in {s + 2, …, n} and

β − (s + 1) ∈ MP_{312}(n − (s + 1), k, 1).

Thus, β − (s + 1) is an identity permutation by the induction hypothesis. However, [α − 1] is an element in MP_{312}(s, k, 0), but this set is empty (by induction hypothesis). Hence, the case r = 1 is done.

Case r ≠ 1. By Lemma 9, we can assume k | n and α − 1 ∈ MP_{312}(s, k, r − 1). But this set is empty unless r = 2 or r = 3 and k | s. The latter is impossible, since the form in (10) tells us r + s ≡ 1 (mod k), which implies that k ∤ s. For the first case (r = 2) there is only one possibility for α, namely [2, 3, …, s + 1] by induction.

We also know that [β − s − 1] ∈ MP_{312}(n−s−1, k, 2). Moreover, we also need that k | (n−s−1) and there are (by induction) 2^{(n−s−1)/k−1} options for β. Accounting for all possible values of n−s−1 in {0, k, 2k, …, n−k}, we have 1+1+2+4+⋯+2^{(n/k−1)−1} = 2^{n/k−1} ways to obtain π.

The following proposition is analogous to Proposition 13.

Proposition 14. Let k ≥ 1. With a_{k}(n) defined as in Proposition 3, we have

𝔪𝔭_{213}(n, k, r) = \begin{cases}a_{k}(n), & if r = 1 or k | n; \\ 0, & otherwise. \end{cases}  (11)

By Lemma 11, a similar statement holds for the pattern 132.

Proof. If k = 1, then r = 1 and 𝔪𝔭_{213}(n, 1) is the Catalan number. From now on assume that k ≥ 2.

For the case r = 1, let us consider π ∈ MP_{213}(n + 1, k). It must be of the form

π = [α_{1}, …, α_{j}, 1, β_{1}, …, β_{n−j}]

where we must have α_{t} > β_{s} for all relevant t, s; see Figure 5.

\begin{matrix}1 \\ β \\ α \end{matrix}

Figure 5: The structure of a 213-avoiding permutation.

Since 1 can only appear at some position km + 1 for some m ∈ ℕ, we must have that k | j. Hence, setting

α′ := [α_{1} − (n − j + 1), α_{2} − (n − j + 1), …, α_{j} − (n − j + 1)]
β′ := [β_{1} − 1, β_{2} − 1, …, β_{n−j} − 1]

we have that α′ ∈ MP_{213}(j, k) if k | n+1 and α′ ∈ MP_{213}(j, k, r′≠1) otherwise. In both cases, α′ exists since k | j and followed by inductive argument. In addition, we have

β′ ∈ MP_{213}(n − j, k).

Thus we have a bijective proof of the recursion in (1).

The “otherwise” case follows from Lemma 9. Hence, only the case k | n, r ≠ 1 needs to be proved. Note that it suffices to show that 𝔪𝔭_{213}(km, k, r) = a_{k}(km).

It is straightforward to verify that (11) holds whenever n ≤ 2. Now suppose π is in MP_{213}(n, k, r) for some r ∈ {2, 3, …, k} and n ≥ 3 with n = km. Then π is of the form

[α_{1}, 1, α_{2}]

where min(α_{1}) > max(α_{2}) as seen in Figure 5. Let α_{1} have length s, so that α_{2} has length n − 1 − s. Note that we must have k | s + r − 1 in order for the first entry in α_{1} to have remainder r mod k. We then have

(α_{2} − 1) ∈ MP_{213}(n − 1 − s, k, 1) and (α_{1} − (n − s)) ∈ MP_{213}(s, k, 1).

Conversely, given permutations τ_{1} ∈ MP_{213}(s, k, 1) and τ_{2} ∈ MP_{213}(n − 1 − s, k, 1) for some s satisfying k | s+r −1, we can construct a unique π ∈ MP_{213}(n, k, r) by reversing the process above. Hence, when k | n we have

𝔪𝔭_{213}(n, k, r) = ∑_{\begin{matrix}s=1 \\ k|s+r−1 \end{matrix}}^{n−1} 𝔪𝔭_{213}(s, k, 1) · 𝔪𝔭_{213}(n − s − 1, k, 1).

Now, setting n = km, s = kj + r′ (note that s can be expressed in this way for the fixed r′ = k − r + 1), and using that a_{k}(i) = 𝔪𝔭_{213}(i, k, 1), we get

𝔪𝔭_{213}(km, k, r) = ∑_{j=0}^{m−1} a_{k}(kj + r′) · a_{k}(km − (kj + r′) − 1).

By (6) in Lemma 4 we may now conclude that 𝔪𝔭_{213}(km, k, r) = a_{k}(km).

We can now give two new combinatorial interpretations of the Fuss–Catalan numbers.

Corollary 15. Let σ ∈ {132, 213} and n, k ≥ 1. Let m and j be defined via n = km + j with 0 ≤ j < k. Then

𝔪𝔭_{σ}(n, k) = \frac{j + 1}{km + j + 1}\binom{(k + 1)m + j}{km + j}

and in particular

𝔪𝔭_{σ}(km, k) = \frac{1}{(k + 1)m + 1}\binom{(k + 1)m + 1}{m} = \frac{1}{km + 1}\binom{(k + 1)m}{m}.

Proof. This follows from Proposition 3 and Equation (3).

4.2 PAPs avoiding one of 132, 213, 231, and 312

The case k = 2 is rather different from k ≥ 3 as indicated by Proposition 13. In this subsection, we treat the k = 2 case for the patterns in {132, 213, 231, 312}.

Lemma 16. Let π ∈ P_{132}(n) with n ≥ 2. Then either n appears after n − 1 in π or n is odd and appears at position 1.

Proof. The case n = 2 is easy so suppose n ≥ 3 and π(1) ≠ n. Then the numbers to the left of n must be greater than the numbers from the right of n in π (since we must avoid the pattern 132; see Figure 3). In particular, n − 1 must appear before n and we are done.

Proposition 17. For m ≥ 0, set

a_{m} := 𝔭_{132}(2m), b_{m} := 𝔭_{132}(2m + 1),
a′_{m} := 𝔭_{231}(2m), b′_{m} := 𝔭_{231}(2m + 1).

We then have a_{m} = a′_{m} and b_{m} = b′_{m} for all m.

Proof. We already know that b_{m} = b′_{m} since rev : P_{132}(2m+1) → P_{231}(2m+1) is a bijection. Claim: We have

a_{m} = ∑_{\begin{matrix}i+j+k=m−1 \\ i,j,k≥0 \end{matrix}} a_{i}a′_{j}a_{k}, and a′_{m} = ∑_{\begin{matrix}i+j+k=m−1 \\ i,j,k≥0 \end{matrix}} a′_{i}a_{j}a′_{k}.  (12)

First set n := 2m and suppose π ∈ P_{132}(2m). By Lemma 16, we know that it must be of the form

[\underbrace{α_{1}, α_{2}, …, α_{2i}}_{α}, n − 1, \underbrace{β_{1}, …, β_{2j}}_{β}, n, \underbrace{γ_{1}, …, γ_{2k}}_{γ}].

Moreover, since the permutation is 132-avoiding (see Figure 3), it must be of the form

\begin{matrix}n \\ n−1 \\ γ \\ β \\ α \end{matrix}

Figure 6: The structure of a 132-avoiding PAP with even length.

Now, the permutation matrices α and γ can be interpreted as smaller permutations in some P_{132}(2i) and P_{132}(2k), respectively. Moreover, the permutation β can be seen as an element in P_{132}^{∗}(2j). By the reversal bijection, we have that β corresponds to some element in P_{231}(2j) whose cardinality is a′_{j}. Hence, we can conclude the first formula in (12).

Using a similar argument (just reverse everything) we can show the second recursive identity. An inductive argument over m now allows us to conclude that a_{m} = a′_{m} for all m ≥ 0.

Corollary 18. For any σ ∈ {132, 213, 231, 312}, we have

𝔭_{σ}(2m) = \frac{1}{2m + 1}\binom{3m}{m} and 𝔭_{σ}(2m + 1) = \frac{1}{2m + 1}\binom{3m + 1}{m + 1}.

Proof. The formulas follow from Corollary 15 for σ = 132. By Proposition 17, the statement holds for the pattern 231. By applying the revflip map we obtain the same counts for the other two patterns.

5 Mod-k-alternating subexcedant functions

Subexcedant functions and their close connection with permutations was initially studied in [12]. We refer to [1] and [2] as examples of applications of these objects.

Definition 19. A subexcedant function f on [n] is a map f : [n] ⟶ [n] such that

1 ≤ f(i) ≤ i for all 1 ≤ i ≤ n.

We denote the set of all subexcedant functions on [n] by F_{n}.

One can easily see that F_{n} has cardinality n!. The bijection sefToPerm : F_{n} ⟶ S_{n} is defined as a product

sefToPerm(f) := (n f(n)) ⋯ (2 f(2))(1 f(1))  (13)

of cycles of maximum length 2. This bijection is the one described in [12].

The inverse map is defined as follows:

sefToPerm^{−1}(σ)_{j} := \begin{cases}σ(n), & if j = n; \\ sefToPerm^{−1}( (n σ(n)) ∘ σ )_{j}, & otherwise \end{cases}  (14)

where σ ∈ S_{n} and j ∈ [n].

Proposition 20. Suppose π ∈ S_{n} and f_{π} is the corresponding element in F_{n}. Then π is in MP(n, k) if and only if f_{π}(i) ≡ i (mod k).

Proof. First, suppose that f_{π}(i) ≡ i (mod k) for some π ∈ S_{n}. In the product (13), we see that f_{π} has k disjoint cycle products, then the first product contains integers that are congruent to 1 (mod k), the second product contains integers that are congruent to 2 (mod k), and so on, with the last product containing integers that are congruent to k (mod k). Hence π ∈ MP(n, k).

On the other hand, suppose now that π ∈ MP(n, k) and consider f_{π} = sefToPerm^{−1}(π). In the recursion in (14), we always interchange integers at positions i and j, where

j ≡ i (mod k).

So (via an inductive argument) we must have that f_{π}(i) ≡ i (mod k) for all i.

Example 21. The subexcedant function 12341634 corresponds to the permutation

[5, 2, 7, 8, 1, 6, 3, 4]

in MP(8, 4).

Definition 22. A word w = (w_{1}, …, w_{n}) ∈ ℕ^{n} is a Catalan word if

w_{1} = 1 and 1 ≤ w_{i} ≤ w_{i−1} + 1 whenever 2 ≤ i ≤ n.

A permutation π in P(n) is called a Catalan PAP if f_{π} is a Catalan word. Let P_{C}(n) be the set of Catalan PAPs and let 𝔭_{C}(n) be its cardinality. We define MP_{C}(n, k) in the same manner and set 𝔪𝔭_{C}(n, k) := |MP_{C}(n, k)|.

There are \frac{1}{n+1} \binom{2n}{n} Catalan words of length n and we shall see below that Catalan words are essentially the same as the well-known area sequences.

Definition 23. A sequence (a_{1}, …, a_{n}) is an area sequence if

a_{1} = 0 and 0 ≤ a_{i} ≤ a_{i−1} + 1 whenever 2 ≤ i ≤ n.

Area sequences are in bijection with Catalan words. The array (a_{1}, …, a_{n}) is an area sequence if and only if (a_{1} + 1, a_{2} + 1, …, a_{n} + 1) is a Catalan word. The notion of area sequences plays an important role in diagonal harmonics; see [5].

There is a well-known bijection between Dyck paths and area sequences. We illustrate this bijection in the following example.

Example 24. The Dyck path P = nnennneneeneee has the area sequence a = (0, 1, 1, 2, 3, 3, 2).

P = 1 2 3 4 5 6 7

The number of shaded boxes in row i (from the bottom) is given by a_{i} and this provides the bijection between area sequences and Dyck paths.

We denote the set of all Dyck paths of size n such that the number of boxes in each row above the path is a multiple of k by L_{n}^{k}; see Example 26.

Corollary 25. The set MP_{C}(n, k) has the same cardinality as L_{n}^{k}.

Proof. Let π ∈ MP_{C}(n, k). By Proposition 20, the corresponding subexcedant function f_{π} = w_{1}w_{2} ⋯ w_{n} is a Catalan word with the property i − w_{i} = α_{i}k for all i ∈ [n], where α_{i} ∈ ℕ. Hence, a = (w_{1} − 1, w_{2} − 1, …, w_{n} − 1) is an area sequence for some Dyck path. Now, the number of boxes in the i^{th} row above the Dyck path is given by

(i − 1) − (w_{i} − 1) = α_{i}k,

since the i^{th} row has i − 1 boxes above the diagonal in the n × n grid.

Example 26. Here are the 9 Dyck paths corresponding to the entries in MP_{C}(7, 3).

1 2 3 4 5 6 7  1 2 3 4 5 6 7  1 2 3 4 5 6 7  1 2 3 4 5 6 7  1 2 3 4 5 6 7

1 2 3 4 5 6 7  1 2 3 4 5 6 7  1 2 3 4 5 6 7  1 2 3 4 5 6 7

Theorem 27. Let r_{k}(n) := 𝔪𝔭_{C}(n, k). Then

r_{k}(n + 1) = ∑_{\begin{matrix}0≤j≤n \\ k|j \end{matrix}} r_{k}(j)r_{k}(n − j), r_{k}(0) := 1.

Proof. Let π be in MP_{C}(n + 1, k). Consider the last 1 in f_{π}. Then we have

f_{π} = γ_{j}, 1, γ_{n−j},

where γ_{j} is the subword having length j. Clearly, j is a multiple of k and 0 ≤ j ≤ n. Finally γ_{j} ∈ MP_{C}(j, k) and γ_{n−j}−1 ∈ MP_{C}(n − j, k), since γ_{n−j} starts with 2.

In the same manner as the proof of Corollary 15, we have the following corollary.

Corollary 28. Let m and j be defined via n = km + j with 0 ≤ j < k. Then

𝔪𝔭_{C}(n, k) = \frac{j + 1}{km + j + 1}\binom{(k + 1)m + j}{km + j}

and in particular,

𝔪𝔭_{C}(km, k) = \frac{1}{(k + 1)m + 1}\binom{(k + 1)m + 1}{m} = \frac{1}{km + 1}\binom{(k + 1)m}{m}.

The fact that our Dyck paths are counted by Raney numbers is not new; this is a classical interpretation of Raney numbers. We decided to include this interpretation mainly for context and to illustrate the surprising fact that a Catalan family with mod-k-restrictions again gives Raney numbers, just as for mod-k-alternating permutations and pattern-avoidance.

6 Mod-k-alternating permutations avoiding two patterns

The systematic study of permutations avoiding two patterns of length 3 was completed by Simion and Schmidt [16]. In this section, we do the same for parity-alternating permutations and mod-k-alternating permutations.

Due to Proposition 13, the situation for k ≥ 3 is, in general, simpler than the k = 2 case. In Table 2, we present an overview of our results in the k = 2 case. We consider the sequence (𝔭_{σ,τ}(n))_{n≥1} and separate it into the cases n = 2m and n = 2m + 1. Closed-form formulas for the sequences (𝔭_{σ,τ}(2m))_{m≥1} and (𝔭_{σ,τ}(2m + 1))_{m≥0}, where

σ, τ ∈ {123, 132, 213, 231, 312, 321},

are shown in the table.

The bold letters refer to cases that are treated below. Note that Lemmas 11 and 12 can easily be generalized to sets of permutations avoiding two or more patterns. For example, 𝔭_{σ,τ}(n, k) = 𝔭_{revflip(σ),revflip(τ)}(n, k). Cases marked with the same letter indicate situations that give the same enumeration after applying these lemmas. We emphasize that the formulas are only valid for permutations of length at least 1.

123  132  213  231 312 321
123 *
132 A; 2^{m−1}, 1  *
213 A; 2^{m−1}, 1  D; 2^{m−1}, F_{2m+1} *
231 B; m, \binom{m}{2}+1 E; 2^{m−1}, 2^{m}  E; 2^{m−1}, 2^{m} *
312 B; m, \binom{m}{2}+1 E; 2^{m−1}, 2^{m}  E; 2^{m−1}, 2^{m} F; F_{n} *
321 C; 0  G; \binom{m}{2}+1  G; \binom{m}{2}+1 I; 1 I; 1 *

Table 2: Pair of formulas in an entry represent the cases n = 2m and n = 2m+1, respectively. A single formula covers to both cases. The Fibonacci numbers are denoted by F_{n}, with F_{1} = F_{2} = 1.

Remark 29. There are no permutations of length 5 or more that avoid 123 and 321. On the other hand, we only get the identity permutation that avoids 231 and 321 due to Proposition 13 or (in the case k = 2) a simple argument.

Only the cases A, D, and G are interesting for k ≥ 3. Otherwise at least one pattern is covered by Proposition 13 and then the number of mod-k-alternating permutations over [n] that avoid the two patterns is 1, for all n. The general formula for 𝔪𝔭_{σ,τ}(n, k) in cases A, D, and G is given in the corresponding subsection.

6.1 Case A, (132, 123)

Lemma 30. Any permutation in S_{132,123}(n) starts with at least n − 1.

Proof. Suppose π ∈ S_{132,123}(n) and π(1) < n − 1. Then π contains either the 123 pattern π(1) n−1 n or the 132 pattern π(1) n n−1. Hence, π(1) ≥ n − 1.

Proposition 31. For n odd, the set P_{132,123}(n) consists only of the permutation [n, n − 1, …, 1]. When n = 2m, we have 𝔭_{132,123}(2m) = 2^{m−1}.

Proof. Suppose π ∈ P_{132,123}(n) for odd n. From Lemma 30, π starts with n and then the rest of the permutation must follow the same rule. Hence, π is the unique permutation [n, n − 1, …, 1].

For the second claim, suppose that

π = [α, 2m, β] ∈ P_{132,123}(2m).

Then it is easy to verify that the permutations

[2m + 1, 2m + 2, α, 2m, β] and [2m + 1, 2m, α, 2m + 2, β]  (15)

are elements in P_{132,123}(2m + 2).

Now, for any π′ ∈ P_{132,123}(2m + 2), by Lemma 30 we have that 2m + 1 is in the very first position. In a similar manner, we must have that π′(2) ∈ {2m, 2m + 2}. We have now shown that all elements in P_{132,123}(2m + 2) are in one of the forms described in (15). By an inductive argument it follows that 𝔭_{132,123}(2m) = 2^{m−1}.

Proposition 32. Let k ≥ 3 and write n = km + l, where 0 ≤ l < k. We then have

𝔪𝔭_{132,123}(km + l, k) = \begin{cases}1, & if (k, l) ∈ \{(3, 1), (3, 2), (4, 2)\}; \\ 0, & otherwise. \end{cases}

Proof. Suppose π ∈ MP_{132,123}(n, k) and consider the position of 1 in π. Since π avoids both 132 and 123, we must have that 1 is in the last or penultimate position. Consequently, l ∈ {1, 2} and we shall treat these two cases separately.

Case l = 1. Since k ≥ 3, we see that 2 must appear to the left of 1 with at least one entry in between. Moreover, since π must avoid both 132 and 123, there cannot be more than one entry between 2 and 1, which implies that k = 3. The same reasoning as above shows that 3 must be placed between 2 and 1, so π ends with 231. We may now treat the first n − 3 entries in π as an element in MP_{132,123}(n − 3, k). By induction, we can then conclude that π is the unique permutation

π = [3m+1, 3m−1, 3m, 3m−2, …, 8, 9, 7, 5, 6, 4, 2, 3, 1],

where the largest entry is first and the remaining entries appear in blocks of 3.

Case l = 2. It is straightforward to show that we must have 2 at the last position of π in order to avoid the two patterns. Now, a similar argument as above shows that

π = […, 3, 1, 2] or π = […, 3, j, 1, 2]

where 4 ≤ j ≤ n. The first option gives k = 3 while the second option forces k = 4 and j = 4.

In case k = 3, we have that π ends with 3, 1, 2 and an inductive argument then gives

π = [3m+1, 3m+2, 3m, 3m−2, 3m−1, …, 9, 7, 8, 6, 4, 5, 3, 1, 2].

Similarly, the case k = 4 gives

π = [4m+1, 4m+2, 4m−1, 4m, 4m−3, 4m−2, …, 7, 8, 5, 6, 3, 4, 1, 2].

6.2 Case B, (231, 123)

For n odd, we have 𝔭_{321,132}(n) = 𝔭_{231,123}(n) because the reversal map (Lemma 5) gives a bijection between the sets. The latter set is enumerated further down in Case G.

The case of even n is covered by the following lemma.

Lemma 33. Suppose π ∈ P_{231,123}(2m). Then

π = [k, k − 1, k − 2, …, 1, 2m, 2m − 1, …, k + 1]

for some odd k. Consequently, 𝔭_{231,123}(2m) = m.

Proof. Because π is 231-avoiding, all entries to the right of 2m must be larger than all entries to its left. Moreover, it is then straightforward to show that both these intervals must be decreasing in order for π to avoid the pattern 123. There are exactly m choices of the first entry in π—any odd number in [2m]. The lemma follows from these observations.

6.3 Case D, (213, 132)

Proposition 34. For k ≥ 1 and 0 ≤ l < k, we have

𝔪𝔭_{213,132}(km + l, k) = \begin{cases}2^{m−1}, & if l = 0; \\ F_{2m+1}, & otherwise. \end{cases}

Proof. For k = 1, this reduces to proving that S_{213,132}(m) = 2^{m−1}. This has been done already by Simion and Schmidt [16]. We treat the case k ≥ 2 in the remaining part of the proof.

Case l ≥ 1. From the recursive formula F_{2m+1} = F_{2m} + F_{2m−1} of the Fibonacci numbers, we can easily deduce the following recursive formula involving only the odd indexed Fibonacci numbers:

F_{2m+1} = 2F_{2(m−1)+1} + F_{2(m−2)+1} + F_{2(m−3)+1} + ⋯ + F_{3} + F_{1}.  (16)

Our goal is to show the same recursive structure for elements in MP_{213,132}(km + l, k).

Suppose π ∈ MP_{213,132}(km + l, k). We claim that π can be obtained in one of the following three ways, corresponding to the factor 2 in 2F_{2(m−1)+1} and the remaining terms in (16), respectively.

(1a) From π′ ∈ MP_{213,132}(k(m − 1) + l, k) by inserting the consecutive integers

k(m−1)+l+1, k(m−1)+l+2, …, km+l−1, km+l

(in this order) immediately after the largest entry in π′.

(1b) From π′ ∈ MP_{213,132}(k(m − 1) + l, k) by inserting the two sequences of consecutive

integers

k(m−1)+l+i, k(m−1)+l+i+1, …, km+l,

and then

k(m−1)+l+1, …, k(m−1)+l+i−1,

(in this order) for some 1 < i ≤ k such that k(m−1)+l+i ≡ 1 (mod k), in the beginning of π′. In fact, we have i = k − l + 1.

(2) From π′′ ∈ MP_{213,132}(ks + l, k) for any 1 ≤ s < m − 1 by inserting the two sequences of consecutive integers

k(m−1)+l+i, k(m−1)+l+i+1, …, km+l,

and then

ks+l+1, ks+l+2, …, k(m−1)+l+i−1

in the beginning of π′′, where i satisfies the same condition as in the previous case.

It is straightforward to verify that the three cases are mutually exclusive, and are indeed elements of MP_{213,132}(km + l, k). We must show that every element in MP_{213,132}(km + l, k) belongs to one of these cases.

Consider the largest element, km + l, in π. All elements to its left must appear in increasing order. Moreover, there cannot be any gaps as that would produce a 132-pattern. There are two cases to consider. The first one is if km + l occurs after k(m − 1) + l and there are exactly k − 1 elements, all are greater than k(m − 1) + l, between them in increasing order. This implies that π belongs to case (1a) above. Otherwise, the entries to the left of km + l form the interval

\underbrace{k(m−1)+l+i, k(m−1)+l+i+1, …, km+l − 1}_{k−i}, km+l

for a unique i ∈ [k]. The largest entry in π (to the right of km + l) is k(m−1)+l+i − 1, so the entries between km + l and k(m−1)+l+i − 1 must form an increasing sequence of consecutive integers. The first one being of the form ks + l + 1 for some s ∈ [m − 1]. This puts π in either case (1b) (for s = m − 1) or case (2).

This shows that we have the recursion

𝔪𝔭_{213,132}(km + l, k) = 2 𝔪𝔭_{213,132}(k(m − 1) + l, k) + 𝔪𝔭_{213,132}(k(m − 2) + l, k)
+ ⋯ + 𝔪𝔭_{213,132}(k + l, k) + 𝔪𝔭_{213,132}(l, k).

Thus, (after checking initial conditions) we have that (𝔪𝔭_{213,132}(km + l, k))_{m=0}^{∞} satisfies the same recursion as in (16). Therefore, 𝔪𝔭_{213,132}(km + l, k) = F_{2m+1}.

Case l = 0. Suppose that π ∈ MP_{213,132}(k(m + 1), k).

By a similar argument as above, π either starts with

km+1, km+2, …, k(m+1)−1, k(m+1)

or km is followed by this sequence of integers. Thus, we can obtain π from π′ ∈ MP_{213,132}(km, k) by inserting

km+1, km+2, …, k(m+1)−1, k(m+1)

either immediately after km, or at the beginning of π′. Hence,

𝔪𝔭_{213,132}(k(m + 1), k) = 2 𝔪𝔭_{213,132}(km, k).

We also have the initial condition 𝔪𝔭_{213,132}(k, k) = 1 (the identity permutation) so it follows that 𝔪𝔭_{213,132}(km, k) = 2^{m−1}.

Corollary 35. We have

𝔭_{213,132}(2m) = 2^{m−1}  and  𝔭_{213,132}(2m + 1) = F_{2m+1}.

6.4 Case E, (231, 132)

Proposition 36. We have

𝔭_{231,132}(2m) = 2^{m−1} and 𝔭_{231,132}(2m + 1) = 2^{m}.

Proof. If π ∈ S_{231,132}(n), it is clear that n must be either in the very beginning or at the very end of π. Thus, π ∈ P_{231,132}(2m + 1) is obtained from π′ ∈ P_{231,132}(2m − 1) by inserting 2m, 2m+1 at the end of π′ or by inserting 2m+1, 2m at the beginning of π′. Moreover, every π ∈ P_{231,132}(2m) can be obtained from some π′ ∈ P_{231,132}(2m − 1) by inserting 2m at the end of π′. Hence,

𝔭_{231,132}(2m + 1) = 2 𝔭_{231,132}(2m − 1) and 𝔭_{231,132}(2m) = 𝔭_{231,132}(2m − 1),

where 𝔭_{231,132}(1) = 1 and 𝔭_{231,132}(2) = 1. The statement then follows by a simple inductive argument.

6.5 Case F, (312, 231)

For k ≥ 3, the set MP_{312,231}(n, k) contains only the identity permutation due to Proposition 13.

For k = 2, we have the following proposition.

Proposition 37. We have 𝔭_{312,231}(n) = F_{n}, the n^{th} Fibonacci number.

Proof. It is easy to verify that this holds for n ≤ 3 so suppose that π ∈ P_{312,231}(n) for some n ≥ 4.

If π(n) ≠ n, then n − 1 must appear on the right of n; otherwise n − 1, n, π(n) forms a 231-pattern so n is immediately followed by n − 1 in order to avoid 312.

Similarly, n − 2 cannot be anywhere left of n, since then n − 2, n, π(n) would form a 231-pattern.

Now, if there was some element between n−1 and n−2, then there would be a 312-pattern in π. Hence, n, n − 1, n − 2 must be a subword of π.

It follows that any π ∈ P_{312,231}(n) can be constructed either from some π′ ∈ P_{312,231}(n−1), by appending n at the very end, or by inserting n, n − 1 immediately before n − 2 in some π′′ ∈ P_{312,231}(n − 2). Thus, we have the classical Fibonacci recursion and the statement follows.

Observe that for odd n we may apply Lemma 5 and then see that 𝔭_{312,231}(n) = 𝔭_{132,213}(n), where the latter is F_{n} according to Case D.

6.6 Case G, (321, 132)

Lemma 38. Let π ∈ MP_{321,132}(km+l, k), where 0 ≤ l < k and k ≥ 2. Then for any j ∈ [m], the entries

k(j−1)+1, k(j−1)+2, …, kj−1, kj

form a subword of π. Moreover, the last l numbers in [km + l] must appear in increasing order at the very end of π.

Proof. Suppose k(j − 1) + i is on the left of k(j − 1) + i − 1 for some 1 < i ≤ k. Then π(1), k(j−1)+i, k(j−1)+i−1 form either a 132- or a 321-pattern, depending on the value of π(1) (we know π(1) ≠ k(j − 1) + i since π(1) ≡ 1 (mod k)). Therefore,

k(j−1)+1, k(j−1)+2, …, kj−1, kj

appear in this order.

Now suppose that k(j − 1) + i − 1 and k(j − 1) + i are not adjacent for some 1 < i ≤ k. Then there are at least k entries between them since π is a mod-k-alternating permutation. Each such entry must be less than k(j − 1) + i − 1, otherwise we have a 132-pattern. Now consider the position of 1 in π and let t be the number succeeding k(j − 1) + i − 1. If 1 appears to the left of k(j − 1) + i − 1, then 1, …, k(j−1)+i−1, t form a 132-pattern. If 1 is on the right, it can not be immediately after k(j − 1) + i − 1 since i > 1. Thus, t ≠ 1 and k(j−1)+i−1, t, …, 1 form a 321-pattern.

Now, it remains to show the last statement in the lemma. For l = 0, there is nothing more to prove. If l > 0 we can argue in the same manner as above, that km+1, km+2, …, km+l must form a subword of π. Since all other entries are partitioned into blocks of length k, we must have that the l largest entries appear at the very end. Otherwise, the entry immediately after km + l would have the wrong remainder mod k.

Proposition 39. For any k ≥ 1, m ≥ 0, and 0 ≤ l < k, we have

𝔪𝔭_{321,132}(km + l, k) = \binom{m}{2} + 1.

Proof. Let π ∈ MP_{321,132}(km + l, k). By the second statement in Lemma 38, we can simply disregard the last l entries and conclude that 𝔪𝔭_{321,132}(km + l, k) = 𝔪𝔭_{321,132}(km, k). By the first property in Lemma 38, we note that there is a simple bijection from MP_{321,132}(km, k) to S_{321,132}(m). We simply keep only the first entry in each block of k letters and standardize the result. Thus, 𝔪𝔭_{321,132}(km+l, k) = |S_{321,132}(m)|. Finally, it has already been shown that |S_{321,132}(m)| = \binom{m}{2} + 1; see [16, Prop. 11].

Corollary 40. We have

𝔭_{321,132}(2m) = 𝔭_{321,132}(2m + 1) = \binom{m}{2} + 1.

7 Remarks

The attentive reader has most likely noticed that we have said nothing about parity– alternating permutations avoiding the single pattern 123, or the single pattern 321.

The sequence with the number of 123-avoiding PAPs of size n starts as

1, 1, 1, 3, 3, 10, 11, 37, 44, 146, 185, 603, 808, 2576, ….

Similarly, for 321-avoiding PAPs, we get

1, 1, 1, 2, 3, 6, 11, 22, 44, 89, 185, 382, 808, 1702, ….

Recall from Lemma 5 that the reversal map is a bijection between the sets P_{321}(2m + 1) and P_{123}(2m + 1), so 𝔭_{321}(2m + 1) = 𝔭_{123}(2m + 1) for all m ≥ 0.

We have not managed to produce recursive formulas for these sequences. The numbers above were obtained by brute-force enumeration—we construct the odd and even parts separately and then check if the merged permutation is 123- (or 321)-avoiding.

However, we have managed to find a property of 321-avoiding PAPs which may be exploited to produce a recursive formula. This property is proved in Proposition 42 but we need a definition first in order to state it.

Definition 41. A left-to-right maximum of π ∈ S_{n} is an integer i ∈ [n] such that i > j for all j ∈ [n] to the left of i in the one-line notation of π. We call the integers that are not left-to-right maxima hole values.

Proposition 42. Let π ∈ P_{321}(n) be non-identity. Then

1. there exists a pair of hole values in π that are consecutive and

2. the highest such pair of numbers either stands in adjacent positions or has an even length sequence of consecutive left-to-right-maxima between the numbers.

Proof. Let i ∈ [1, n−1] be the highest position with no excedance in π ∈ P_{321}(n) till i. Then π_{j} = j, for all j = 1, 2, …, i−1 and π_{i+1} > i+1 since π_{i} > i and π is a 321-avoiding PAP. Thus, i and i + 1 are hole values, which show the existence.

Now consider the highest such pair of consecutive hole values in π, say h and h + 1. The integer h + 1 is always to the right of h. Otherwise, π_{h}, h+1, h forms a 321 pattern. If h and h + 1 are adjacent, then we are done. Otherwise, there is an even number (at least two) of positions between h and h + 1 since π is a PAP. Moreover, the numbers between h and h + 1 are left-to-right maxima since π is 321-avoiding. If the numbers in between are consecutive, then we are done. Otherwise, we have a pair of consecutive hole values which are greater than h and h + 1. This is a contradiction since h and h + 1 are the highest.

8 Acknowledgments

Thanks to Ran Pan [14] for proposing the problem about pattern avoidance of parityalternating permutations.

We appreciate the hospitality we get from the Department of Mathematics, Stockholm University. We especially acknowledge the useful discussions with Jörgen Backelin and Joel Persson. The second and third authors are grateful for the financial support extended by the cooperation agreement between the International Science Program (ISP) at Uppsala University and Addis Ababa University. We are also grateful for the financial support provided by the Wennergren foundation. Dun Qiu is supported by the National Natural Science Foundation of China (NSFC) grants, 12001037, 12171034, and 12271023.

The On-line Encyclopedia of Integer Sequences (OEIS) has been a valuable tool in this research project.

We are thankful for the valuable suggestions from the anonymous referee, in particular for simplifying the proof of Proposition 3.

References

[1] Per Alexandersson and Frether Getachew An involution on derangements, arxiv preprint arXiv:2105.08455, 2021. Available at http://arxiv.org/abs/2105.08455.

[2] Fufa Beyene and Roberto Mantaci. Flattened partitions and subxceedant functions, arxiv preprint arXiv:2101.07081, 2021. Available at http://arxiv.org/abs/2101.

07081.

[3] R. Brak and N. Mahony. Fibonacci, Motzkin, Schroder, Fuss-Catalan and other combinatorial structures: Universal and embedded bijections, arxiv preprint arXiv:1909.09296, 2019. Available at http://arxiv.org/abs/1909.09296.

[4] Ronald Graham, Donald Knuth, and Oren Patashnik. Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley, second edition, 1994.

[5] James Haglund. The q, t-Catalan Numbers and the Space of Diagonal Harmonics (University lecture series). Amer. Math. Soc., 2007. Available at https://www.math.upenn.

edu/~jhaglund/books/qtcat.pdf.

[6] Frether Getachew Kebede and Fanja Rakotondrajao. Parity alternating permutations starting with an odd integer. Enumer. Comb. Appl. 1 (2021), Paper No. S2R16.

https://doi.org/10.54550/eca2021v1s2r16.

[7] Sergey Kitaev. Patterns in Permutations and Words. Springer, 2011.

[8] Donald E. Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms. Addison Wesley Longman Publishing Co., Inc., third edition, 1997.

[9] Donald E. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching. Addison Wesley Longman Publishing Co., Inc., second edition, 1998.

[10] J. H. Lambert. Observationes variæ in mathesin puram. Acta Helvetica Physico-Mathematico-Anatomico-Botanico-Medica, Basileae 3 (1758), 128–168. Available at

https://www.biodiversitylibrary.org/bibliography/9661.

[11] J. H. Lambert. Observations analytiques. Nouveaux Mémoires de l’Académie royale des Sciences et Belles-Lettres de Berlin (1770), 225–244.

[12] Roberto Mantaci and Fanja Rakotondrajao. A permutations representation that knows what “Eulerian” means. Discrete Math. Theoret. Comput. Sci. 4 (2001), 101–108. Avail-

    able at https://dmtcs.episciences.org/271.

[13] Augustine Munagi. Parity-alternating permutations and successions. Cent. Eur. J.

    Math. 2 (2014), 1390–1402. https://doi.org/10.2478/s11533-014-0421-2.
[14] Ran Pan. Problem 10, Project P, 2015. https://mathweb.ucsd.edu/~projectp/
    problems/p10.html.

[15] George N. Raney. Functional composition patterns and power series reversion. Trans. Amer. Math. Soc. 94 (1960), 441–451. https://doi.org/10.1090/

    s0002-9947-1960-0114765-9.

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

[17] Neil J. A. Sloane. The On-Line Encyclopedia of Integer Sequences, 2019. Available at

    https://oeis.org.

[18] Richard P. Stanley. Catalan Numbers. Cambridge University Press, 2015.

[19] Shinji Tanimoto. Combinatorics of the group of parity alternating permutations, Adv. Appl. Math. 44 (2010), 225–230.

[20] Herbert S. Wilf, generatingfunctionology. Elsevier, 1994. Available at https://www2.

    math.upenn.edu/~wilf/gfologyLinked2.pdf.

2020 Mathematics Subject Classification: Primary 05A05; Secondary 05A15, 05A19. Keywords: mod-k-alternating permutation, Fuss–Catalan number, Raney number.

(Concerned with sequences \underline{A000027}, \underline{A000045}, \underline{A000079}, \underline{A000124}, \underline{A047749}, \underline{A079508}, \underline{A335109}, \underline{A354208}, \underline{A355089}, and \underline{A355262}.)

Received May 24 2022; revised versions received January 23 2023; January 24 2023; February 25 2023; April 6 2023. Published in Journal of Integer Sequences, April 7 2023.

Return to Journal of Integer Sequences home page.