Sets of Flattened Partitions with Forbidden Patterns

Olivia Nabawanda^{1} Department of Mathematics Makerere University P. O. Box 7062 Kampala Uganda

                 onabawanda@must.ac.ug

Fanja Rakotondrajao Département de Mathématiques et Informatique Université d’Antananarivo, Antananarivo Antananarivo Madagascar

                   frakoton@yahoo.fr

Abstract

The study of pattern avoidance in permutations, and specifically in flattened partitions is an active area of current research. In this paper, we count the number of distinct flattened partitions over [n] avoiding a single pattern, as well as a pair of two patterns. Several counting sequences, namely Catalan numbers, powers of two, Fibonacci numbers and Motzkin numbers arise. We also consider other combinatorial statistics, namely runs and inversions, and establish some bijections in situations where the statistics coincide.

1Corresponding author.

1 Introduction and preliminaries

Counting permutations based on avoidance of a given pattern has been studied from various perspectives in both enumerative and algebraic combinatorics [3, 5, 7, 8, 9, 11, 19]. It provides an easier way for understanding the properties of different combinatorial objects through bijective proofs.

For a fixed positive integer n, we define the set [n] := {1, 2, …, n}. A permutation σ over [n] will be represented as a word σ(1)σ(2) ⋯ σ(n), where σ(i) is the image of i under σ. We say that σ has an occurrence of a pattern τ, if there exists a subsequence in σ which is order-isomorphic to τ, else we say that σ is τ-avoiding [15]. The elements of an occurrence τ may be consecutive or non consecutive in σ. For example, σ = 7345612 contains several 231 occurrences among which include: 561, 352, 362, 452, 461 and 463, and is 213-avoiding. A run in σ is a subsequence of the form σ(i)σ(i + 1) ⋯ σ(i + p)σ(i + p + 1) where i, i + 1, …, i + p are consecutive ascents, i−1 (if it does exist) and i+p+1 are non-ascents, where i ∈ [n] [17]. We call σ(i) the starting point of the run. A flattened partition is a permutation consisting of runs arranged from left to right such that their starting points are in increasing order [17]. Notice that if σ is a flattened partition, then σ(1) = 1. For example, the permutation σ = 139278456 is a flattened partition with three runs namely 139, 278, 456 whose starting points are 1, 2, and 4 respectively. Given a non-empty finite subset S of positive integers, a set partition P of S is a collection of disjoint non-empty subsets B_{1}, B_{2}, …, B_{k} of S (called blocks) such that ∪_{i=1}^{k}B_{i} = S [13, 18]. We shall maintain the name and notion of “flattened partition” introduced by Callan [4]. Callan borrowed the notion “Flatten” from the Mathematica programming language, where it acts by taking lists of sets arranged in increasing order, removes their parentheses, and writes them as a single list [20]. However, different set partitions can have the same resulting flattened partition under the command “Flatten” from Mathematica. For example Flatten(1|2|3) = 123 = Flatten(12|3). In his work, Callan [4] studied partitions of a set [n], whose flattening avoids a single 3-letter pattern. Along the same direction, Mansour et al. [15] also studied avoidance of a single 3letter pattern in set partitions of size n. For more details on flattened partitions and pattern avoidance, see [12, 14, 16]. We study the number of distinct flattened partitions avoiding a pattern τ, using fairly similar methods as those used by Mansour et al. [15], though we work on different sets of permutations.

Definition 1. Let (i_{1}, i_{2}, i_{3}), (j_{1}, j_{2}, j_{3}) ∈ ℕ^{3} where ℕ denotes the set of positive integers. We say that (i_{1}, i_{2}, i_{3}) is lexicographically smaller than (j_{1}, j_{2}, j_{3}), denoted by (i_{1}, i_{2}, i_{3}) ≤_{lex} (j_{1}, j_{2}, j_{3}), if we have

(i) i_{1} < j_{1} or

(ii) i_{1} = j_{1} and i_{2} < j_{2} or

(iii) i_{1} = j_{1}, i_{2} = j_{2} and i_{3} ≤ j_{3}.

A permutation σ over [n] has an ascent or descent at position i if σ(i) < σ(i + 1) or σ(i) > σ(i + 1), respectively, for i ∈ [n − 1].

A permutation σ over [n] has an inversion if there exists a pair (π(i), π(j)) for i < j such that π(i) > π(j).

In this paper, we count the number of distinct flattened partitions over [n] avoiding an occurrence of a single pattern τ, as well as a pair of patterns (τ_{1}, τ_{2}).

Let τ ∈ {123, 132, 213, 231, 312, 321}, S(n; τ) the set of all permutations over [n] which are τ-avoiding, F(n; τ) the set of τ-avoiding flattened partitions over [n], and F(n; τ_{1}, τ_{2}) the set of (τ_{1}, τ_{2})-avoiding flattened partitions over [n]. Let |F(n; τ)| and |F(n; τ_{1}, τ_{2})| denote the cardinalities of the sets F(n; τ) and F(n; τ_{1}, τ_{2}) respectively. Let inv(π) = |{(i, j) : i < j, π(i) > π(j)}| denote the number of inversions in a permutation π and runs(π) the number of runs in π. In Table 1, we give the first few values of the numbers of 3-letter pattern avoiding flattened partitions and the On-Line Encyclopedia of Integer Sequences (OEIS) they correspond to (for detailed discussions on these sequences, see Section 2).

Pattern τ  |F(n; τ)|_{n≥1}  OEIS sequence
123  1, 1, 1, 0, 0, 0, 0, ….  ⋯
132  1, 1, 1, 1, 1, 1, 1, ….  \underline{A000012}
213  1, 1, 2, 4, 8, 16, 32, ….  \underline{A011782}
231  1, 1, 2, 4, 9, 21, 51, ….  \underline{A001006}
312  1, 1, 2, 4, 8, 16, 32, ….  \underline{A011782}
321  1, 1, 2, 5, 14, 42, 132, ….  \underline{A000108}

Table 1: The numbers of 3-letter pattern avoiding flattened partitions

We say that a flattened partition avoids two patterns τ_{1} and τ_{2} if it does not contain an occurrence of either τ_{1} or τ_{2} or both. In Section 3, we explain the combinatorics behind the sequences in Table 2 by giving their recurrence relations and corresponding combinatorial proofs. The sequences in Table 2 were obtained by computing for the first few values of n (for detailed discussions on these sequences, see Section 3).

Pattern τ  |F(n; τ)|_{n≥1}  OEIS sequence
(213, 231), (231, 312) 1, 1, 2, 3, 5, 8, 13, …  \underline{A000045}
{(132, 213), (132, 231), \atop (132, 312), (132, 321)} 1, 1, 1, 1, 1, 1, 1, …  \underline{A000012}
{(213, 321), (231, 321), \atop (312, 321)} 1, 1, 2, 4, 8, 16, 32, …  \underline{A011782}
(213, 312)  1, 1, 2, 3, 4, 5, 6 …  \underline{A028310}
(123, 132)  1, 1, 0, 0, 0, 0, 0 …  ⋯
{(123, 213), (123, 231), \atop (123, 312), (123, 321)} 1, 1, 1, 0, 0, 0, 0 …  ⋯

Table 2: Summary of (τ_{1}, τ_{2})-avoiding flattened partitions

In Section 2, we explain the combinatorics behind the sequences in Table 1 by finding recurrence relations, as well as establishing bijections between flattened partitions avoiding certain patterns and other combinatorial structures counted by the same sequences. One such bijection is given in Theorem 6, where we show that the lengths of runs of the permutations in the involved sets are preserved. Another interesting result is Theorem 4, where we show, using runs, that 213-avoiding flattened partitions are counted by powers of two. We also describe the recurrence relation for 312-avoiding flattened partitions in terms of the number of inversions preserved or created. In Section 3, we find recurrence relations for flattened partitions in the set F(n; τ_{1}, τ_{2}) and their corresponding combinatorial proofs.

2 Three letter pattern-avoiding flattened partitions

We shall consider avoidance of patterns τ ∈ {123, 132, 213, 231, 312, 321}. The cases of 123-avoiding and 132-avoiding flattened partitions are not very interesting: the counting sequences are (|F(n; 123)|)_{n≥1} = (1, 1, 1, 0, 0, …) and (|F(n; 132)|)_{n≥1} = (1, 1, 1, 1, 1, …) respectively.

2.1 213-avoiding

Lemma 2. For any positive integer n ≥ 1, a 213-avoiding flattened partition over [n] has the integer n at the end of its first run.

Proof. Let σ ∈ F(n; 213). Suppose n is not in the first run of σ. Then n would be the last element in of any of the remaining runs of σ. For some j > 2, let σ(j) be the starting point of the second run. Then we would have a 213-occurrence σ(j − 1)σ(j)n, a contradiction.

Proposition 3. Let p_{1}, p_{2}, …, p_{r}, q_{r−1}, …, q_{1} be non-empty words such that the concatenation

p_{1}p_{2} ⋯ p_{r}q_{r−1}q_{r−2} ⋯ q_{1} = 123 ⋯ n.  (1)

Then π = p_{1}q_{1}|p_{2}q_{2}| ⋯ |p_{r−1}q_{r−1}|p_{r} is an element in F(n; 213) and all elements in F(n; 213) are of this form.

Proof. It is obvious from Equation (1) that p_{1}q_{1}, p_{2}q_{2}, …, p_{r−1}q_{r−1}, p_{r} are runs. The permutation π is flattened because the starting points of the runs from Equation (1) appear in increasing order. If we had a 213-occurrence, then there would exist integers m < j < k such that π(j) < π(m) < π(k). Then π(m) and π(j) can not be in the same run. Let π(m) ∈ p_{i}q_{i} and π(j) ∈ p_{i+s}q_{i+s}. Then π(m) belongs to q_{i} (because by Equation (1) if it belonged to p_{i}, we would have an increasing sequence). Moreover, π(k) can belong to p_{i+t} or q_{i+t} for some t ≥ s. Using Equation (1), we would have π(k) appearing to the left of π(m) in the identity permutation i.e., π(k) < π(m), which is against the assumptions. Thus indeed π ∈ F(n; 213).

Next we prove that all F(n; 213) have the form p_{1}q_{1}p_{2}q_{2} ⋯ p_{r−1}q_{r−1}p_{r} where the subwords p_{i} and q_{i} are non-empty and have consecutive elements and satisfy Equation (1). Suppose σ ∈ F(n; 213) and consider its first run R_{1}. From Lemma 2, R_{1} ends with the integer n. Since σ is flattened, then it is obvious that R_{1} starts with 1. If σ is the identity permutation, id, then id = p_{1}. If σ ≠ id, let R_{1} = c_{1}c_{2} ⋯ c_{l} where l ≥ 2 and each c_{i} consists of consecutive numbers which are grouped in non-empty maximal words of R_{1}. In particular, c_{1} = 123 ⋯ k, and c_{l} = m(m + 1) ⋯ n for some 1 ≤ k < m ≤ n. We note that k + 1 is the first element of R_{2} (the second run of σ). Now suppose l ≥ 3 and let k′ be the last element of c_{2}. Then k′ + 1 is not in R_{1}. Thus we have

σ = 12 ⋯ k ⋯ k′ ⋯ n|(k + 1) ⋯ (k′ + 1),

where k + 1 < k′. Then k′(k + 1)(k′ + 1) would be a 213-occurrence, a contradiction. Hence l = 2 and R_{1} = c_{1}c_{2} where c_{1} = 12 ⋯ k and c_{2} = m(m + 1) ⋯ n. Let the remaining runs be denoted as R_{2}R_{3} ⋯ R_{r} = σ′. Then σ′ is a permutation of the elements {k+1, …, m−1}. We note that the permutation σ′ − k is 213-avoiding and flattened. By an inductive argument, the claim is indeed true.

Theorem 4. For any integer n ≥ 2, we have

∑_{π∈F(n;213)} q^{runs(π)} = ∑_{r≥1} q^{r}\binom{n − 1}{2r − 2}.

Consequently, |F(n; 213)| = 2^{n−2} with |F(1; 213)| = 1.

Proof. Let us construct a flattened partition π over [n] having r runs, and with 2r − 1 subwords p_{1}, …, p_{r}, q_{r−1}, …, q_{1} such that p_{1}p_{2} ⋯ p_{r}q_{r−1} ⋯ q_{1} = 123 ⋯ n, as in Equation (1). Then π is constructed uniquely from 123 ⋯ n by choosing 2r−2 spaces from the n−1 spaces between the numbers, and then use them as demarcations between the 2r − 1 sub-words. There are \binom{n − 1}{2r−2} such choices. Summing over r ≥ 1 gives the desired result.

Example 5. Let us construct a flattened partition π ∈ F(9; 213) having 3 runs. Consider the sequence 1⌞⌟2⌞⌟3⌞⌟4⌞⌟5⌞⌟6⌞⌟7⌞⌟8⌞⌟9, which has 8 spaces. Then π is determined from this sequence by choosing 4 of them as demarcations. We may for instance choose 12⌞⌟3⌞⌟45⌞⌟67⌞⌟89. Since there are three runs, we then label the first three blocks as p_{1} = 12, p_{2} = 3, and p_{3} = 45. Then the remaining blocks are q_{2} = 6 and q_{1} = 78. Thus we have π = p_{1}q_{1}p_{2}q_{2}p_{3} = 12783645 ∈ F(9, 213).

Theorem 6. For any integer n ≥ 3,

∑_{π∈F(n;312)} x_{1}^{α_{1}(π)} · x_{2}^{α_{2}(π)} ⋯ x_{r}^{α_{r}(π)} = ∑_{π′∈F(n;213)} x_{1}^{α_{1}(π′)} · x_{2}^{α_{2}(π′)} ⋯ x_{r}^{α_{r}(π′)},

where α_{i}(π) is the length of the i^{th} run of π. Consequently, putting x_{i} = 1, we have |F(n; 213)| = |F(n; 312)|.

Remark 7. Note that in each π or π′, the number of factors corresponds to the number of runs r in π.

Proof. We shall define a mapping f(π) = π′ ∈ F(n; 213) which associates to each first run R_{1} of π ∈ F(n; 312) a corresponding first run R′_{1} of π′ of the same length as described below. We shall also provide an inverse g to f. If π is the identity permutation, then f(π) = π = π′, else by the same arguments as in Proposition 3, we have that R_{1} consists of two non-empty sub-words: p_{1} = 123 ⋯ k and q_{1} = m(m + 1) ⋯ t, with one gap between them, for some t ≤ n and k < m. Hence m ≥ k + 2. Suppose m > k + 2, then k + 1 would be the starting point of the second run and k + 2 would be anywhere on the right of k + 1 in π. Hence we would have a 312 occurrence m(k + 1)(k + 2), a contradiction. Hence m = k + 2. By Proposition 3, R′_{1} should consist of two non-empty sub-words p′_{1} and q′_{1} of consecutive elements. We put p′_{1} : = p_{1}, and the sub-word q′_{1} of π′ is got by adding a term (n−t) to each element of q_{1} i.e., q′_{1} = q_{1} + (n − t) = (m + n − t)(m + n + 1 − t) ⋯ n. Let σ be the resulting sub-word obtained from π after removing R_{1} and then writing the remaining elements of π in standard form. Applying the mapping f on σ we obtain σ′, for which adding k to each element of its elements gives π′ = R′_{1}(σ′ + k) which indeed is 213-avoiding.

The inverse mapping g could be constructed recursively in an analogous manner as for f. Note that p_{1} = p′_{1} and that q_{1} and q′_{1} have the same length. It suffices to note that R_{1} and R′_{1} have the same lengths and hence the mapping f preserves the lengths and the number of the runs in π and π′ and is a bijection.

Example 8. Consider π = 13|246|5 ∈ F(6; 312). Applying the mapping f on the first run R_{1} = 13 gives R′_{1} = 16 with k = 1. The resulting sub-word 246|5 when standardized gives σ = 124|3 ∈ F(4; 312). Again applying f on 124|3 gives σ′ = 124|3 and σ′ + 1 = 235|4. Thus π′ = R′_{1}(σ′ + 1) = 16|235|4.

Proposition 9. A π ∈ F(n; 213) contains at least one 312 occurrence if and only if f(π) ∈ F(n; 312) contains at least one 213 occurrence.

Proof. Let F(n; 213, 312) be the set consisting of all σ which do not contain any 312 and 213 occurrences. Then under the mapping f, we have that f(σ) = σ. From Theorem 6, the sets F(n; 213) and F(n; 312) have the same sizes. Thus the sizes of the sets A = F(n; 213) \ F(n; 213, 312) and B = F(n; 312) \ F(n; 213, 312) are also the same. This proves the claim.

2.2 312-avoiding

Proposition 10. A 312-avoiding flattened partition starts with either 12 or 13.

Proof. Let π be a 312-avoiding flattened partition. Suppose that π starts with 1i where i ≥ 4. Then 2 is the starting point of the second run. The integer 3 appears on the right of 2. Hence π would contain a 312 occurrence i23. Hence i ≤ 3.

Proposition 11. Interchanging the 2 and 3 in a 312-avoiding flattened partition preserves the avoidance property.

Corollary 12. For any integer n ≥ 3, the number of 312-avoiding flattened partitions over [n] starting with 12 is equal to the number of 312-avoiding flattened partitions over [n] starting with 13.

This is because in each 312-avoiding flattened partitions over [n] starting with 12, interchanging 2 and 3 gives a 312-avoiding flattened partitions over [n] starting with 13, and vice versa.

Theorem 13. For all n ≥ 1,

∑_{π∈F(n;312)} q^{inv(π)} = (1 + q)^{n−2}.

Proof. It suffices to prove that

∑_{π∈F(n;312)} q^{inv(π)} = ∑_{π∈F(n−1;312)} q^{inv(π)}(1 + q).

For n = 1, 2, the identity is the only 312- avoiding flattened partition. From Proposition 10 and Corollary 12, there are only two classes of 312-avoiding flattened partitions: one class starting with 12 and another one starting with 13 and their sizes are equal. To create the first class, we consider a 312-avoiding flattened partition π of length n − 1 and insert the integer 1 at the beginning of π. We then increase by 1 the remaining terms to get a 312-avoiding flattened partition σ of length n. Let P_{n}(q) = ∑_{π∈F(n;312)} q^{inv(π)}. Then the first class contributes 1 · P_{n−1}(q) inversions. To create the second class, we interchange the integers 2 and 3 of the first class. Hence the second class contributes q · P_{n}(q) inversions. Summing the inversions proves the theorem.

2.3 321-avoiding

Theorem 14. For any integer n ≥ 1, we have |F(n; 321)| = C_{n−1}, where C_{n} = \frac{1}{n+1} \binom{2n}{n} is the n^{th} Catalan number with C_{0} = 1.

Proof. As shown by Knuth in [10], we have that |S(n − 1; 321)| = C_{n−1}. Thus the proof of Theorem 14 follows from Lemma 15.

Lemma 15. For n ≥ 1, there exists a bijection h : F(n; 321) → S(n − 1; 321) defined by removing integer 1 from π ∈ F(n; 321) and reducing the remaining π elements by 1.

It is easy to see how to construct the inverse mapping h′ : S(n − 1; 321) → F(n; 321), and that both h and h′ preserve 321 avoidance. One observation worth noting is that h′(σ) is a flattened partition even if σ ∈ S(n − 1; 321) is not. The only obstruction to this would be if the first entries of the runs (except the first run) of σ are not in increasing order. In this case, it would imply that there exists integers b and a both starting points of such runs such that b > a, although a occurs later. Then there would exist an integer c > b > a in the first run such that cba is a 321 occurrence.

2.4 231-avoiding

Lemma 16. Let n be a positive integer and π be a 231-avoiding flattened partition of length n. There exists an integer 2 ≤ k ≤ n such that:

(i) π(i) < k if i < k,

(ii) π(k) = n,

(iii) π(i) ≥ k if i > k.

Proof. Let k = π(n)^{−1} and π = 1π(2) ⋯ π(k − 1)nπ(k + 1) ⋯ π(n). Let m = max{π(j) : 1 ≤ j ≤ k − 1}. Necessarily, π(l) > m for all k + 1 ≤ l ≤ n since else there would be a 231 occurrence mna where a = π(l) < m. Hence k = m + 1.

Theorem 17. For any positive integer n ≥ 3, we have

|F(n; 231)| = |F(n − 1; 231)| + ∑_{k=2}^{n−1} |F(k − 1; 231)||F(n − k; 231)|  (2)

with initial values |F(1; 231)| = 1, |F(2; 231)| = 1.

Thus |F(n; 231)| = M_{n−1}, where M_{n} is the n^{th} Motzkin number (\underline{A001006}) with M_{0} = 1 as given by Aigner [1].

Proof. We consider two cases depending on k: one case when k < n and another case when k = n. In the latter case, inserting n at the end of each π′ ∈ F(n−1; 231) gives π ∈ F(n; 231). Hence we have |F(n − 1; 231)| unique flattened partitions having n at the end of each π.

In the case k < n, there are two subsequences on the left and right of n for each π ∈ F(n; 231) i.e., 1π(2) ⋯ π(k − 1) and π(k + 1) ⋯ π(n) of lengths k − 1 and n − k respectively. Let π_{1} = 1π(2) ⋯ π(k − 1) and π_{2} = π(k + 1) ⋯ π(n). We note that subtracting integer k − 1 from each element of π_{2} gives π ∈ F(n − k; 231). By Lemma 16, we have that each π_{1} ∈ F(k−1; 231). Multiplying and summing over k indeed gives ∑_{k=2}^{n−1} |F(k−1; 231)||F(n− k; 231)|.

Summing the two cases together proves the claim.

Alternatively, we also give a bijection between 231-avoiding flattened partitions and the well known Motzkin paths which are also counted by Motzkin numbers. First, we introduce the so called Motzkin permutations because they are in bijection with Motzkin paths. This was proved by Mansour et al. [6]. A permutation σ is said to be Motzkin if it avoids pattern 132 and there are no integers i < j for which π(i) < π(j) < π(j + 1). The latter condition corresponds to avoidance of a kind of generalized patterns introduced by Babson and Steingrímsson [2]. There is a bijection α : M_{n−1} → F(n; 231) between the set of Motzkin permutations over [n − 1] and 231-avoiding flattened partitions over [n] defined by the following: For each σ ∈ M_{n−1}, increase by 1 all elements of σ and reverse their order to obtain π′. Then insert integer 1 at the beginning of π′ to obtain α(σ) = π ∈ F(n; 231). We remark that avoidance of pattern 132 in σ ∈ M_{n−1} corresponds to avoidance of pattern 231 in π. On the other hand, avoidance of the generalized pattern corresponds to π ∈ F(n).

3 Avoidance of pairs of three letter patterns in flattened partitions

We shall consider avoidance of a pair of patterns (τ_{1}, τ_{2}) of length three. The cases of (123, 132)-avoiding and ((123, 213)-, (123, 231)-, (123, 312)-, (123, 321))-avoiding flattened partitions are not very interesting: the counting sequences for n ≥ 1 are (1, 1, 0, 0, 0, …) and (1, 1, 1, 0, 0, …) for the latter cases respectively. Similarly, the pairs ((132, 213), (132, 231), (132, 312), (132, 321)) all have a trivial counting sequence (1, 1, 1, 1, 1, …)_{n≥1}. In the subsections that follow, we consider avoidance of the remaining pairs of patterns.

3.1 (213, 231)-avoiding

Here, we consider the problem of avoiding both 213 and 231 patterns.

Proposition 18. Let n ≥ 1 be a positive integer. If π is a (213, 231)-avoiding flattened partition, then there exists an integer 2 ≤ k ≤ n such that

(i) π(i) = i for 1 ≤ i ≤ k − 1, (ii) π(k) = n,

(iii) π(i) ≥ k for k + 1 ≤ i ≤ n.

Proof. Let π = 1π(2) ⋯ π(k − 1)nπ(k + 1) ⋯ π(n), x = max{π(j) : 1 ≤ j ≤ k − 1}. By Proposition 2, the integer n must be at the end of the first run. By Theorem 16, the integers 1, 2, …, k − 1 are also elements of the first run. Hence conditions (i) and (ii) are satisfied. Necessarily, π(y) > x for all k + 1 ≤ y ≤ n, π(y) ≥ x since else there would be a 231 occurrence xny . Hence k = x + 1.

Lemma 19. For any integer n ≥ 1, all elements of F(n; 213, 231) start with either 12 or 1n.

The proof is similar to that of Proposition 10, just that in this case, we suppose that π ∈ F(n; 213, 231) starts with 1i where 3 ≤ i ≤ n − 1 and then prove by contradiction that this is not possible.

Proposition 20. For any integer n ≥ 1, we have |F(n; 213, 231)| = F_{n} where F_{n} is the Fibonacci number with initial conditions F_{1} = F_{2} = 1.

Proof. We prove this claim by induction. For n = 1, 2, the identity is the only (213, 231)- avoiding flattened partition.

For n ≥ 3, from Lemma 19, there are two classes of (213, 231)-avoiding flattened partition: one class starting with 12 and another class starting with 1n. To create the first class, for each π′ ∈ F(n − 1; 213, 231), inserting 1 at the beginning of π′ and then increasing by 1 the remaining terms gives |F(n − 1; 213, 231)| unique flattened partitions. To create the second class, for each π′ ∈ F(n − 2; 213, 231), inserting the subsequence 1n at the beginning of π′, and then increasing the remaining elements by 1 gives |F(n − 2; 213, 231)| unique flattened partitions. It is clear that removing 1 or the subsequence 1n from each π ∈ F(n; 213, 231) that starts with 12 or 1n respectively gives the elements in the sets F(n − 1; 213, 231) or F(n − 2; 213, 231). Thus inductively,

|F(n; 213, 231)| = |F(n − 1; 213, 231)| + |F(n − 2; 213, 231)| = F_{n−1} + F_{n−2} = F_{n}.

Example 21. Let us construct flattened partitions π ∈ F(6; 213, 231). Inserting 1 at the beginning of each elements in F(5; 213, 231) = {15234, 15243, 12345, 12354, 12534}, and then increasing the remaining elements by 1 gives π in the class starting with 12. On the other hand, inserting the subsequence 16 at the beginning of each element in the set F(4; 213, 231) = {1234, 1243, 1423}, and then increasing the remaining elements by 1 gives π in the second class.

Let us denote by F (n, k) the number of (213, 231)-avoiding flattened partitions with r runs, in which the first run R_{1} has length k.

Proposition 22. For all integers k, n such that 1 ≤ k < n, we have F (n, k) = F_{n−k}, where F_{n−k} is the (n − k)^{th} Fibonacci number.

Proof. By Proposition 18, R_{1} is unique since given its length k, then R_{1} = 12 ⋯ (k − 2)(k − 1)n. The remaining runs denoted as R_{2}R_{3} ⋯ R_{r} thus have length n−k. Let R_{2}R_{3} ⋯ R_{r} = σ′. We note that removing integer k − 1 from each element of σ′ gives π ∈ F(n − k; 213, 231) and vice versa. Thus,

F (n, k) = |F(n − k; 213, 231)| = F_{n−k}

Proposition 23. The ordinary generating function F (u, x) for the number of (213, 231)- avoiding flattened partitions is given by

F (u, x) = \frac{1 − u − u^{2} + u^{3}x^{2}}{(1 − ux)(1 − u − u^{2})}.

Proof. Letting

F (u, x) = ∑_{n≥0} ∑_{k≥0} F (n, k)x^{k}u^{n}

and using Proposition 22 gives the required result.

3.2 (312, 231)-avoiding

Proposition 24. For any integer n ≥ 1, we have |F(n; 312, 231)| = F_{n} where F_{n} is the Fibonacci number with initial conditions F_{1} = F_{2} = 1.

Proof. We prove the claim by induction. For n = 1, 2, the identity permutation is the only (312, 231)-avoiding flattened partition.

For n ≥ 3, from Proposition 10, there are two classes of (312, 231)-avoiding flattened partition: one class starting with 12 and another class starting with 13. To create the first class, for each π′ ∈ F(n − 1, 312, 231), inserting 1 at the beginning of π′ and then increasing by 1 the remaining terms gives |F(n−1, 312, 231)| unique flattened partitions. To create the second class, for each π′ ∈ F(n − 2, 312, 231), inserting the subsequence 13 at the beginning of π′, and then increasing the first element of π′ by 1, and the remaining elements by 2 gives |F(n−2, 312, 231)| unique flattened partitions. It is clear that removing 1 or the subsequence 13 from each π ∈ F(n, 312, 231) that starts with 12 or 13 respectively gives elements in the sets F(n − 1, 312, 231) or F(n − 2, 312, 231). Thus inductively,

|F(n, 312, 231)| = |F(n − 1, 312, 231)| + |F(n − 2, 312, 231)| = F_{n−1} + F_{n−2} = F_{n}.

Example 25. Let us construct flattened partitions π ∈ F(6, 312, 231). Inserting 1 at the beginning of each elements in F(5, 312, 231) = {13245, 13254, 12345, 12354, 12435}, and then increasing the remaining elements by 1 gives π in the class starting with 12. On the other hand, inserting the subsequence 13 at the beginning of each element in the set F(4, 312, 231) = {1234, 1243, 1324}, and then increasing the first element in this set by 1 and the remaining elements by 2 gives π in the second class.

3.3 (213, 312)-avoiding

From Proposition 10, we have already seen that 312-avoiding flattened partitions either start with 12 or 13. Hence (213, 312)-avoiding flattened partitions also have the same classes. However, there is only one flattened partition in this class that starts with 13.

Lemma 26. For n ≥ 3, the only π ∈ F(n; 213, 312) that starts with 13 has 2 as a singleton second run.

Proof. Since π starts with 13, then 2 is the starting point of the second run and 3 ∈ R_{1}. Suppose π has at least two runs and that the second run is not singleton. Then there would exist an integer c > 3 > 2 to the right of 2 such that we have a 213 occurrence 32c. Since the position of 1, 2 and 3 are are known, then the remaining n − 3 elements can be arranged in R_{1} as an increasing sequence in R_{1} after 3 and there is only one way this can be done.

Proposition 27. For any integer n ≥ 3, the number of (213, 312)-avoiding flattened partitions satisfies the recurrence relation |F(n; 213, 312)| = |F(n − 1; 213, 312)| + 1 with initial condition |F(2; 213, 312)| = 1.

Proof. From Lemma 26, there is exactly one π′ ∈ F(n − 1; 213, 312) that starts with 13. Inserting n at the end of the first run of π′ gives 1 unique flattened partition π ∈ F(n; 213, 312) that starts with 13. By Proposition 10, the second class of (213, 312)-avoiding flattened partitions starts with 12. To create this class, we insert 1 at the beginning of each π′ ∈ F(n − 1; 213, 312), and then increase the remaining elements of π′ by 1. This gives |F(n − 1; 213, 312)| unique flattened partitions. It is clear that removing 1 or n from each π ∈ F(n; 213, 312) that starts with 12 or 13 respectively gives the elements in the set F(n − 1; 213, 312) or the only element in F(n − 1; 213, 312) that starts with 13.

3.4 (213, 321)-avoiding

Proposition 28. For any positive integer n ≥ 2,

|F(n; 213, 321)| = |F(n − 1; 213, 321)| + n − 2  (3)

with initial conditions |F(1; 213, 321)| = 1. Consequently,

|F(n; 213, 321)| = \binom{n − 1}{2} + 1.  (4)

Proof. For each σ ∈ F(n−1; 213, 321) and using Lemma 2, inserting n at the end of the first run preserves the number of runs and gives π ∈ F(n; 213, 321) with the subsequence (n−1)n at the end of the first run. This gives |F(n−1; 213, 321)| unique flattened partitions. For the identity flattened partition id ∈ F(n−1; 213, 321), there are (n−2) more choices of inserting n into positions n − 1, n − 2, …, 2 respectively in id to create an element π ∈ F(n; 213, 321). If σ ∈ F(n − 1; 213, 321) is not the identity and we suppose that n appears in the first run before n − 1, then there exists an integer a < n − 1, a starting point of the second run such that n(n-1)a is a 321 occurrence. Thus such cases can not exist. Summing up gives Equation (3), and solving this easy recursion gives Equation (4).

3.5 (231, 321)-avoiding

Proposition 29. For any n ≥ 2, |F(n; 231, 321)| = 2^{n−2}.

Proof. For n ≥ 3, there are two classes of (231, 321)-avoiding flattened partitions: one class that starts with 12 and another class that starts with 1i for 3 ≤ i ≤ n. Necessarily, in the latter class, 2 is the starting point of the second run, and the first run has exactly two elements. Otherwise there exists integers i, j in the first run, for 1 < i < j, for which we would have a 231-occurrence ij2.

To create the first class, we insert 1 at the beginning of each π′ ∈ F(n − 1; 231, 321) and then increase the remaining elements of π′ by 1. This gives |F(n − 1; 231, 321)| unique flattened partitions. To create the second class, we increase all elements in π′ ∈ F(n − 1; 231, 321) that start with 1i except the first element by 1 and then insert 2 in the third position. This gives |F(n − 1; 231, 321)| unique flattened partitions. It is clear how to invert these constructions. Thus we have

|F(n; 231, 321)| = 2|F(n − 1; 231, 321)|,

with initial condition |F(2; 231, 321)| = 1. Solving this recursion proves the claim.

Remark 30. All (312, 321)-avoiding flattened partitions have similar properties and structure as 312-avoiding flattened partitions studied in Subsection 2.2. Remark 31. There are many subsequent follow-up questions one can ask about flattened partitions avoiding some patterns, but these will be addressed separately.

4 Acknowledgment

The first author acknowledges the financial support extended by the Swedish Sida Phase-IV bilateral program with Makerere University. Special thanks go to Prof. Jörgen Backelin, Prof. Paul Vaderlind, and Dr. Per Alexandersson of Stockholm University, Department of Mathematics, and Dr. Alex Samuel Bamunoba of Makerere University, Department of Mathematics, for their valuable input and suggestions. Many thanks to my colleagues from CoRS—Combinatorial Research Studio, for lively discussions and comments.

References

[1] M. Aigner, Motzkin numbers, European J. Combin. 19 (1998), 663—675.

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

[3] M. Bóna, Combinatorics of Permutations, CRC Press, 2016.

[4] D. Callan, Pattern avoidance in “flattened” partitions, Discrete Math. 309 (2009), 4187– 4191.

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

[6] S. Elizalde and T. Mansour, Restricted Motzkin permutations, Motzkin paths, continued fractions, and Chebyshev polynomials, Discrete Math. 305 (2005), 170–189.

[7] S. Elizalde and M. Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (2003), 110–125.

[8] S. Kitaev, Patterns in Permutations and Words, Springer Science & Business Media, 2011.

[9] D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, Addison-Wesley Professional, 1998.

[10] D. E. Knuth, Art of Computer Programming, Volume 2: Seminumerical Algorithms, Addison-Wesley Professional, 2014.

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

[12] T. Y. H. Liu and A. Zhang, On pattern avoiding flattened set partitions, Acta Math. Sin. (Engl. Ser.) 31 (2015), 1923–1928.

[13] T. Mansour, Combinatorics of Set Partitions, CRC Press, 2012.

[14] T. Mansour and M. Shattuck, Pattern avoidance in flattened permutations, Pure Math. Appl. (PU.M.A.) 22 (2011), 75–86.

[15] T. Mansour, M. Shattuck, and S. Wagner, Counting subwords in flattened partitions of sets, Discrete Math. 338 (2015), 1989–2005.

[16] T. Mansour, M. Shattuck, and D. G. L. Wang, Recurrence relations for patterns of type (2, 1) in flattened permutations, J. Difference Equ. Appl. 20 (2014), 58–83.

[17] O. Nabawanda, F. Rakotondrajao, and A. S. Bamunoba, Run distribution over flattened partitions, J. Integer Sequences 23 (2020), Article 20.9.6.

[18] G. Rota, The number of partitions of a set, Amer. Math. Monthly 71 (1964), 498–504.

[19] H.S. Wilf, The patterns of permutations, Discrete Math. 257 (2002), 575–583.

[20] S. Wolfram, The Mathematica Book, Cambridge University Press, 2000.

2010 Mathematics Subject Classification: Primary 05A05; Secondary 05A10, 05A15, 05A18. Keywords: Catalan number, Fibonacci number, flattened partition, Motzkin number, pattern, run, inversion.

(Concerned with sequences \underline{A000012}, \underline{A000045}, \underline{A000108}, \underline{A001006}, \underline{A011782}, and \underline{A028310}.)

Received December 5 2020; revised version received January 1 2021. Published in Journal of Integer Sequences, January 2 2021.

Return to Journal of Integer Sequences home page.