Enumeration of Two Particular Sets of Minimal Permutations

Stefano Bilotta, Elisabetta Grazzini,^{1} and Elisa Pergola Dipartimento di Matematica e Informatica “Ulisse Dini” Università di Firenze Viale G. B. Morgagni 65 50134 Firenze Italy

                  egrazzini@unifi.it

Abstract

Minimal permutations with d descents and size d + 2 have a unique ascent between two sequences of descents. Our aim is the enumeration of two particular sets of these permutations. The first set contains the permutations having d + 2 as the top element of the ascent. The permutations in the latter set have 1 as the last element of the first sequence of descents and are the reverse-complement of those in the other set. The main result is that these sets are enumerated by the second-order Eulerian numbers.

1 Introduction

1.1 Preliminary definitions

A permutation of size n is a bijective map from {1..n} to itself. We denote by S_{n} the set of permutations of size n. We consider a permutation σ ∈ S_{n} as the word σ_{1}σ_{2} ⋯ σ_{n} of n letters on the alphabet {1, 2, …, n}, containing each letter exactly once (we often use the word element or entry instead of letter). For example, 6 2 4 3 5 1 represents the permutation σ ∈ S_{6} such that σ_{1} = 6, σ_{2} = 2, …, σ_{6} = 1.

1 Corresponding author.

Definition 1. Let σ be a permutation in S_{n}. We say that σ has a descent in position i whenever σ_{i} > σ_{i+1}. In the same way, we say that σ has an ascent in position i whenever σ_{i} < σ_{i+1}.

Example 2. The permutation σ = 6 9 8 4 1 3 7 2 5 ∈ S_{9} has 4 descents, namely in positions 2, 3, 4, 7, and 4 ascents in positions 1, 5, 6 and 8.

Definition 3. Let σ be a permutation in S_{n}. The reverse of σ is the permutation σ^{r} = σ_{n}σ_{n−1} ⋯ σ_{1}. The complement of σ is the permutation σ^{c} = (n + 1 − σ_{1})(n + 1 − σ_{2}) ⋯ (n + 1 − σ_{n}).

Example 4. If σ = 4 2 6 5 3 1, then σ^{r} = 1 3 5 6 2 4, σ^{c} = 3 5 1 2 4 6 and σ^{rc} = σ^{cr} = 6 4 2 1 5 3.

Definition 5. A permutation π ∈ S_{k} is a pattern of a permutation σ ∈ S_{n} if there is a subsequence of σ which is order-isomorphic to π, i.e., if there is a subsequence σ_{i_{1}}σ_{i_{2}} ⋯ σ_{i_{k}} of σ, 1 ≤ i_{1} < i_{2} < ⋯ < i_{k} ≤ n, such that σ_{i_{ℓ}} < σ_{i_{m}} whenever π_{ℓ} < π_{m}. We also say that π is contained in σ and call σ_{i_{1}}σ_{i_{2}} ⋯ σ_{i_{k}} an occurrence of π in σ.

Example 6. The permutation σ = 3 1 2 8 5 4 7 9 6 contains the pattern 1 2 3 4 since σ_{2} σ_{3} σ_{5} σ_{7} is an increasing subsequence of size 4.

We write π ≺ σ to denote that π is a pattern of σ. A permutation σ that does not contain π as a pattern is said to avoid π. The class of all permutations avoiding the patterns π1, π2, …, πk is denoted S(π1, π2, …, πk). We say that S(π1, π2, …, πk) is a class of pattern-avoiding permutations of basis {π1, π2, …, πk}.

1.2 Minimal permutations with d descents

Minimal permutations with d descents arise from biological motivations [1, 3, 4]. Among the many models for genome evolution, the whole genome duplication - random loss model represents genomes with permutations, that can evolve through duplication-loss steps representing the biological phenomenon that duplicates fragments of genomes, and then loses one copy of every duplicated gene [2]. Bouvel and Rossin [3] showed that the class of permutations obtained in this model after a given number p of steps is a class of pattern-avoiding permutations of finite basis, and proved the following theorem.

Theorem 7. The class of permutations obtainable by at most p steps in the whole genome duplication - random loss model is a class of pattern-avoiding permutations whose basis B_{d} is finite and is composed of the minimal permutations with d = 2^{p} descents, minimal being intended in the sense of ≺.

In this paper, we focus on the basis B_{d} of excluded patterns appearing in Theorem 7. More generally, we do not assume that d is a power of 2. From here on, by minimal permutation with d descents, we mean a permutation that is minimal with respect to the pattern-involvement relation ≺ for the property of having d descents.

Example 8. Let σ = 7 4 1 3 2 5 8 6 9 be a permutation with 4 descents; σ is not minimal with 4 descents. Indeed, the elements 1 and 5 can be removed from σ without changing the number of descents. Doing this, we obtain permutation π = 5 3 2 1 6 4 7 which is minimal with 4 descents: it is impossible to remove an element from it while preserving the number of descents equal to 4. However, π is not of minimal size among the permutation with 4 descents: π has size 7 whereas permutation 5 4 3 1 2 has 4 descents but size 5.

A characterization of minimal permutations with d descents is given in Proposition 9, whose proof is given in [2].

Proposition 9. Let σ be a minimal permutation with d descents. Then every ascent of σ is immediately preceded and immediately followed by a descent, and the size n of σ satisfies d + 1 ≤ n ≤ 2d.

The condition provided by Proposition 9 is not sufficient to give a characterization of minimal permutations with d descents.

Example 10. The permutation σ = 7 5 1 3 2 10 8 4 9 6, with 6 descents, does not contain consecutive ascents. However, σ is not minimal as it contains the pattern π = 6 4 2 1 9 7 3 8 5, which is minimal with 6 descents.

An exhaustive characterization of minimal permutations, as given in [2], can be summarized in the following theorem, giving a local characterization of minimal permutations with d descents.

Theorem 11. A permutation σ of size n is minimal with d descents if and only if it has exactly d descents and its ascents σ_{i}σ_{i+1} are such that 2 ≤ i ≤ n − 2 and σ_{i−1}σ_{i}σ_{i+1}σ_{i+2} forms an occurrence of either the pattern 2143 or the pattern 3142.

The characterization of minimal permutations with d descents in Theorem 11 directly leads to a partially ordered set (or poset) representation of permutations.

Consider the set of all minimal permutations of size n with d descents, and having their descents and ascents in the same positions. In all these permutations, the elements are locally ordered in the same way, even around the ascents, because of Theorem 11. This whole set of permutations can be represented by a partially ordered set indicating the necessary conditions on the relative order of the elements between them. For a descent, there is a link from the first and greatest element to the second and smallest one. For any ascent σ_{i}σ_{i+1}, the elements σ_{i−1}σ_{i}σ_{i+1}σ_{i+2} form a diamond-shaped structure with σ_{i+1} at the top, σ_{i} at the bottom, σ_{i−1} on the left and σ_{i+2} on the right. By Theorem 11, any labelling of the elements of the poset respecting its ordering constraints is a minimal permutation with d descents. See Figure 1 for an example.

We will say that a permutation σ satisfies the diamond property when each of its ascents σ_{i}σ_{i+1} is such that σ_{i−1}σ_{i}σ_{i+1}σ_{i+2} forms a diamond, that is to say is an occurrence of either 2143 or 3142.

Figure 1: Permutations and authorized labelling of the posets

1.3 Outline of the paper

As claimed in Proposition 9, the size of minimal permutations with d descents is at least d + 1 and at most 2d. Obviously there is only one minimal permutation with d descents and size d + 1, that is the reverse identity permutation (d + 1)d(d − 1) ⋯ 321.

Bouvel and Pergola [2] found that the number of minimal permutations with d descents and maximal size 2d is given by the d-th Catalan number c_{d} = \frac{1}{d+1} \binom{2d}{d}.

Mansour and Yan [5] showed that the number of minimal permutations with d descents and size 2d−1 is 2^{d−3}(d−1)c_{d}. They also obtained (i) a recurrence relation on the multivariate generating function for the minimal permutations of length n, for fixed n, counted by the number of descents, and the values of the first and second elements of the permutation, (ii) a recurrence relation on the multivariate generating function for the minimal permutations of length n with n − d descents, for fixed d, counted by the length, and the values of the first and second elements of the permutation.

In this paper we are interested in minimal permutations with d descents and size d + 2 (minimal non trivial case). Let us recall that a minimal permutation with d descents and size d + 2 has a unique ascent, between two sequences of descents, and that the elements surrounding the ascent are organized in a diamond in the poset representation of the permutation. Therefore, the greatest element d + 2 is either the first entry of the permutation or the top element of the diamond.

Our aim is the enumeration of two particular sets of minimal permutations with d descents and size d + 2. The first set M_{1} we deal with contains the permutations such that d + 2 is the top element of the diamond. The other set M_{2} contains the permutations in which the first sequence of descents ends with the entry 1.

The main result is that both these sets are enumerated by the second-order Eulerian numbers.

Bouvel and Pergola [2] obtained a closed formula for the enumeration of minimal permutations with d descents and size d + 2 as reported in the following theorem.

Theorem 12. The minimal permutations with d descents and size d + 2 are enumerated by the sequence (s_{d}) defined as follows: s_{d} = 2^{d+2} − (d + 1)(d + 2) − 2.

In particular, they give a proof of Theorem 12 defining two bijections Φ^{1} and Φ^{2} between the set of minimal permutations with d descents and size d + 2 and the non-interval subsets of {1, 2, …, d + 1}.

We will use these bijections to enumerate the sets M_{1} and M_{2}. Therefore, in Section 2 we recall the definition of the bijections Φ^{1} and Φ^{2}.

The enumeration of the sets M_{1} and M_{2} is obtained in Sections 3 and 4, respectively. As corollaries of this main result, we obtain the enumeration of other subsets of minimal permutations with d descents and size d + 2. See table 2 at the end of the paper, where we list the counting sequences connected to our results.

2 The bijections Φ^{1} and Φ^{2}

We need to recall the bijections between the non-interval subsets of {1, 2, …, d + 1} and the set of minimal permutation with d descents and size d + 2 to proceed.

A non-interval subset of {1, 2, …, d + 1} is a non-empty subset of {1, 2, …, d + 1} that is not an interval. The number of non-interval subsets of \{1, 2, …, d+1\} is 2^{d+1} − \frac{(d+1)(d+2)}{2} −1 [2]. To prove Theorem 12 Bouvel and Pergola [2] showed that there are twice as many permutations with d descents and size d + 2 as non-interval subsets of {1, 2, …, d + 1} . For this purpose they partitioned the set of minimal permutations with d descents and size d + 2 into two subset S^{1} and S^{2}, and defined two bijections between S^{1} and S^{2}, respectively, and the set of non-interval subsets of {1, 2, …, d + 1} , denoted as N ℓ.

The set S^{1} contains the minimal permutations with d descents and size d + 2 such that (i) d + 2 is the top element of the diamond and (ii) the elements in the first sequence of descents are not consecutive. The set S^{2} contains all the other minimal permutations with d descents and size d + 2.

Let s be a non-interval subset of {1, 2, …, d + 1}, and let w = {1, 2, …, d + 1} \ s be the set of “wholes” associated with s.

The bijection Φ^{1} between N ℓ and S^{1} is defined as follows: the permutation Φ^{1}(s) consists of the elements of s in decreasing order, followed by d + 2 and then by the elements of w in decreasing order.

Example 13. In this example and in the following ones we consider d = 5. Given s = {3, 5, 6}, and w = {1, 2, 4}, Φ^{1}(s) is the minimal permutation 6 5 3 7 4 2 1 with 5 descents and size 7.

In order to define the bijection between N ℓ and S^{2}, Bouvel and Pergola [2] divided the permutations in S^{2} into five types, from A to E in the following way.

Let σ be a permutation of S^{2}. Then σ is of one of the five types:

A) (i) d + 2 is the top element of the diamond, (ii) the first sequence of descents contains only two consecutive elements;

B) (i) d + 2 is the top element of the diamond, (ii) the first sequence of descents contains at least three consecutive elements, (iii) the second sequence of descents has the form (d + 2)(d + 1)r, where r = ∅ or r = k(k − 1)(k − 2) … 1, for some k ≥ 1;

C) (i) d + 2 is the top element of the diamond, (ii) the first sequence of descents contains at least three consecutive elements, (iii) the second sequence of descents of has the form (d + 2)(d + 1)r_{1}r_{2}, were r_{1} = d … (d − ℓ), for some ℓ ≥ 0, r_{2} = ∅ or r_{2} = k(k − 1)(k − 2) … 1, for some k ≥ 1. Notice that r_{1} cannot be empty;

D) (i) d + 2 is the first element, (ii) the second sequence of descents contains consecutive elements;

E) (i) d+2 is the first element, (ii) the second sequence of descents contains not consecutive elements.

Now we can describe the application Φ^{2} from N ℓ to S^{2}. Let s be a non-interval subset of {1, 2, …, d + 1}, and let w be the associate set of wholes.

A) If w contains only one element x, then necessarily x ≠ 1 and x ≠ d + 1. In this case, Φ^{2}(s) is the permutation of type A whose first sequence of descents is x(x − 1).

Example 14. Given s = {1, 2, 3, 5, 6}, and w = {4}, Φ^{2}(s) is the permutation 4 3 7 6 5 2 1 of type A.

If w contains at least two elements, let n be the cardinality of the non-interval subset s, and let m be the cardinality of the associated set w increased by 1. Moreover, let w_{1} and w_{2} be the smallest and the second-smallest elements of w, and let s_{n−1} and s_{n} be the greatest and the second-greatest elements of s. The permutation Φ^{2}(s) will contain m elements on its first sequence of descents and n on its second, according to the relative order of w_{1}, w_{2}, s_{n−1}, and s_{n}. Notice that m ≥ 3, n ≥ 2, and w_{1} < s_{n}.

B) If s_{n−1} < w_{1} < s_{n} < w_{2} , then s = {1, …, n − 1, n + 1} and consequently w = {n, n + 2, …, d + 1}. The permutation Φ^{2}(s) is of type B and it is such that (i) the second sequence of descents starts with (d + 2)(d + 1) and then contains n − 2 consecutive elements from n − 2 to 1, (ii) the first sequence of descents contains m consecutive elements starting with d.

Example 15. Given s = {1, 2, 4}, and w = {3, 5, 6}, Φ^{2}(s) is the permutation 5 4 3 2 7 6 1 of type B.

C) If w_{1} < s_{n−1} < s_{n} < w_{2}, then s = {1, …, w_{1} − 1, w_{1} + 1, …, n + 1} and w = {w_{1}, n + 2, …, d + 1}, i.e., w_{2} = n + 2. To determine the non-interval set s it is sufficient to know its cardinality n and the number p = n + 1 − w_{1} of elements between w_{1} and w_{2}. Since s_{n−1} and s_{n} are between w_{1} and w_{2} and s is non-interval, p satisfies the conditions 2 ≤ p ≤ n − 1. The permutation Φ^{2}(s) of type C is obtained as follows. The second sequence of descents splits into two parts (the second one possibly empty). The first part contains p + 1 consecutive elements in decreasing order starting with d + 2; the second part is composed of n − p − 1 consecutive elements from n − p − 1 to 1. The remaining m elements, written in decreasing order, constitute the first sequence of descents.

Example 16. Given s = {1, 2, 4, 5}, w = {3, 6}, then p = 2 and the type C permutation Φ^{2}(s) is 5 4 3 2 7 6 1.

D) If s_{n−1} < w_{1} < w_{2} < s_{n}, then s = {1, 2, …, n − 1, s_{n}}. The permutation Φ^{2}(s) is of type D and its is such that (i) the second sequence of descents contains n consecutive elements in decreasing order starting with s_{n}, (ii) the first sequence of descents starts with d + 2 and then contains the remaining m elements in decreasing order.

Example 17. Given s = {1, 2, 6}, w = {3, 4, 5}, the type D permutation Φ^{2}(s) is 7 3 2 1 6 5 4.

E) If w_{1} < w_{2} < s_{n−1} < s_{n} or w_{1} < s_{n−1} < w_{2} < s_{n}, then Φ^{2}(s) is the permutation of type E obtained as follows. The first sequence of descents of Φ^{2}(s) starts with d + 2 and then contains the elements of w in decreasing order; the second sequence of descents contains the element of s in decreasing order.

Example 18. Given s = {3, 5, 6}, w = {1, 2, 4}, the type E permutation Φ^{2}(s) is 7 4 2 1 6 5 3.

The 32 minimal permutations with 4 descents and size 6 (d = 4) associated with the 16 non-interval subsets of {1, 2, 3, 4, 5} by the bijections Φ^{1} and Φ^{2}, respectively, are shown in table 1.

3 The enumeration of M_{1}

In this section we will count the permutations in the set M_{1}, that is, the minimal permutations with d descents and size d + 2 which have d + 2 as the second element of the unique ascent.

Referring to the definitions given in Section 2, the set M_{1} contains all the permutations in S^{1} and the permutations of type A, B, and C.

s  w  Φ^{1}(s) Φ^{2}(s) Type
{1, 2, 4, 5} {3}  542163 326541 A
{1, 2, 3, 5} {4}  532164 436521 A
{1, 3, 4, 5} {2}  543162 216543 A
{1, 2, 4} {3, 5} 421653 432651 B
{1, 2, 5} {3, 4} 521643 621543 D
{1, 3, 4} {2, 5} 431652 321654 C
{1, 3, 5} {2, 4} 531642 642531 E
{1, 4, 5} {2, 3} 541632 632541 E
{2, 4, 5} {1, 3} 542631 631542 E
{2, 3, 5} {1, 4} 532641 641532 E
{1, 3}  {2, 4, 5} 316542 432165 B
{1, 4}  {2, 3, 5} 416532 652143 D
{1, 5}  {2, 3, 4} 516432 632154 D
{2, 4}  {1, 3, 5} 426531 653142 E
{2, 5}  {1, 3, 4} 526431 643152 E
{3, 5}  {1, 2, 4} 536421 642153 E

Table 1: Minimal permutations with 4 descents and size 6 (d = 4)

Owing to the bijection Φ^{1} between the set S^{1} and the set N ℓ, the number N_{S^{1}} of minimal permutations with d descents and size d + 2 in S^{1} is

N_{S^{1}} = 2^{d+1} − \frac{(d + 1)(d + 2)}{2} − 1.  (1)

The minimal permutations with d descents and size d + 2 of type A are associated by the bijection Φ^{2} with the sets s such that the corresponding sets w contain only one element x with x ≠ 1 and x ≠ d+1. Therefore, there exists one permutation of type A for each possible value of x. Consequently, the number N_{A} of permutations of type A is

N_{A} = d − 1.  (2)

If σ = Φ^{2}(s) is a permutation of type B, then s is completely determined by its cardinality n. Thus, there exists only one permutation of type B for each possible value of n. Since n ranges from 2 to d − 1, the number N_{B} of permutations of type B is

N_{B} = d − 2.  (3)

Because of the definition of Φ^{2}, the permutations of type C depend on the cardinality n of s and on the smallest element w_{1} of w. Since w_{1} satisfies the conditions 2 ≤ w_{1} ≤ n − 1, there are n − 2 possible values of w_{1} for each value of n. Moreover, for the permutations of type C, n satisfies the conditions 3 ≤ n ≤ d − 1. Therefore, the number N_{C} of permutations of type C is

N_{C} = ∑_{n=3}^{d−1}(n − 2) = ∑_{n=1}^{d−3} n
= \frac{(d − 3)(d − 2)}{2}.  (4)

Theorem 19. The minimal permutations with d descents and size d + 2 having d + 2 as the top element of the diamond are enumerated by the sequence (m_{1})_{d} defined as follows:

(m_{1})_{d} = 2^{d+1} − 2(d + 1).  (5)

Proof. The total number of minimal permutations with d descents and size d + 2 in M_{1} is given by N_{S^{1}} + N_{A} + N_{B} + N_{C}, that is

N_{S^{1}} + N_{A} + N_{B} + N_{C} = 2^{d+1} − \frac{(d + 1)(d + 2)}{2} − 1 + (d − 1) + (d − 2) + \frac{(d − 3)(d − 2)}{2}
= 2^{d+1} − 2(d + 1).

The first terms of the sequence (5) are 2, 8, 22, 52, 114, 240, 494 …, for d ≥ 2. They are the second-order Eulerian numbers and correspond to the sequence \underline{A005803} in the On-line Encyclopedia of Integer Sequence [6].

Corollary 20. The minimal permutations with d descents and size d + 2 whose first entry is d + 2 are enumerated by the sequence (f)_{d} defined as follows:

(f)_{d} = 2^{d+1} − d(d + 1) − 2.  (6)

Proof. Since minimal permutations with d descents and size d + 2 start with d + 2 or have d + 2 as the second element of the unique ascent, the number of minimal permutations with d descents and size d + 2 whose first entry is d + 2 is given by the difference between the total number of these permutations (see Theorem 12) and (m_{1})_{d}. This number is

2^{d+2} − (d + 1)(d + 2) − 2 − [2^{d+1} − 2(d + 1)] = 2^{d+1} − d(d + 1) − 2.

The first terms of the sequence (6) are 0, 2, 10, 32, 84, 198, 438, …, for d ≥ 2. This sequence does not appear in [6].

4 The enumeration of M_{2}

The set M_{2} contains the minimal permutations with d descents and size d + 2 whose first sequence of descents ends with 1, that is having 1 as the bottom element of the diamond.

Let σ be a permutation in M_{1} with the ascent in position i and σ_{i+1} = d + 2. By Definition 3, σ_{1}^{rc} = d + 3 − σ_{d+2}, σ_{2}^{rc} = d + 3 − σ_{d+1}, …, σ_{d+2−i−1}^{rc} = d + 3 − σ_{i+2}, σ_{d+2−i}^{rc} = d + 3 − σ_{i+1}, σ_{d+2−i+1}^{rc} = d + 3 − σ_{i}, σ_{d+2−i+2}^{rc} = d + 3 − σ_{i−1}, …, σ_{d+2}^{rc} = d + 3 − σ_{1}, (see Example 4).

Since

σ_{1}^{rc} > σ_{2}^{rc} > ⋯ > σ_{d+2−i−1}^{rc} > σ_{d+2−i}^{rc} = 1 < σ_{d+2−i+1}^{rc} < σ_{d+2−i+2}^{rc} < ⋯ < σ_{d+2}^{rc}

σ^{rc} is a permutation of size (d+2) with d descents where the unique ascent is in position d+2− i and the first sequence of descents ends with 1. Moreover, since σ_{d+2−i−1}^{rc}σ_{d+2−i}^{rc}σ_{d+2−i+1}^{rc}σ_{d+2−i+2}^{rc} forms an occurrence of either the pattern 2143 or the pattern 3142, (depending on σ), σ^{rc} is a minimal permutation of size d + 2 with d descents, (see Theorem 11).

Therefore the permutations in M_{2} are the reverse-complement of those in M_{1} and the following theorem holds.

Theorem 21. The minimal permutations with d descents and size d + 2 having 1 as the bottom element of the diamond are enumerated by the sequence (m_{2})_{d} defined as follows:

(m_{2})_{d} = 2^{d+1} − 2(d + 1).  (7)

Since in a minimal permutation σ with d descents and size d + 2 the entry 1 is at the end of the first sequence of descents or it is the last element of σ, the proof of the following corollary is straightforward.

Corollary 22. The minimal permutations with d descents and size d + 2 whose last entry is 1 are enumerated by the sequence (f)_{d} defined in Corollary 20.

Corollary 23. The minimal permutations with d descents and size d+2 whose unique ascent is 1 (d + 2) are enumerated by the sequence (g)_{d} defined as follows:

(g)_{d} = 2^{d} − 2.  (8)

Proof. By the definition of the bijection Φ^{2}, the unique minimal permutation with d descents and size d+2 of type A in which the bottom element of the diamond is 1 is the the permutation 2 1 (d + 2) (d + 1) d ⋯ 3.

Similarly, if a permutation of type B has 1 as the bottom element of the diamond then the associated non-interval subset has cardinality 2. Therefore, there is an unique minimal permutation with d descents and size d + 2 of type B whose first sequence of descents ends with 1, and it is the permutation Φ^{2}(s) where s = {1, 3} and w = {2, 4, …, d + 1}, that is the permutation d (d − 1) ⋯ 2 1 (d + 2) (d + 1).

The minimal permutations with d descents and size d + 2 of type C in M_{2} are those in which the segment r_{2} of the second sequence of descent is empty. Recall that the first sequence of descent contains at least three elements. By the definition of Φ^{2}(s) for permutations of typeC, r_{2} is empty if n − p − 1 = 0, that is w_{1} = 2, as p = n + 1 − w_{1}. Therefore, for each value of the cardinality n of s there is only one permutation of type C in which 1 is the bottom element of the diamond. Since n ranges from 3 to d − 1, the number of minimal permutations with d descents and size d + 2 of type C in M_{2} is d − 3.

To sum up, the total number M_{ABC} of minimal permutations with d descents and size d + 2 of type A, B, and C with unique ascent 1 (d + 2) is

M_{ABC} = 1 + 1 + (d − 3) = d − 1.  (9)

Now we have just to count the permutations in S^{1} having 1 at the end of the first sequence of descents. The first sequence of descents in a permutations Φ^{1}(s) contains the elements of s in descending order. Therefore, it is sufficient to count the non-interval sets s containing the entry 1. Given the cardinality n, if s contains 1 then the other n − 1 elements are

• a non-interval set of cardinality n − 1. As we have seen before, the intervals of length n − 1 are d + 1 − (n − 1), so the non-interval sets of cardinality n − 1 are \binom{d}{n−1} − (d + 1) + (n − 1),

• or an interval of length n − 1 without the entry 2. As before, it is simple to see that the intervals of length n − 1 starting with 3 are d + 1 − n.

Thus, the non-interval sets s of cardinality n containing the entry 1 are

\binom{d}{n − 1} − (d + 1) + (n − 1) + d + 1 − n = \binom{d}{n − 1} − 1.  (10)

Hence, the permutations in S^{1} having 1 at the end of the first sequence of descents are

M_{S^{1}} = ∑_{n=2}^{d}[\binom{d}{n − 1} − 1]

= ∑_{n=2}^{d} \binom{d}{n − 1} − ∑_{n=2}^{d} 1

= 2^{d} − \binom{d}{0} − \binom{d}{d} − (d − 1)
= 2^{d} − d − 1.  (11)

The number of minimal permutations with d descents and size d+2 having the pair 1 (d+2) as unique ascent is

M_{S^{1}} + M_{ABC} = 2^{d} − d − 1 + d − 1 = 2^{d} − 2.

The first terms of the sequence (8) are 2, 6, 14, 30, 62, 126, 254 …, for d ≥ 2. They correspond to the sequence \underline{A000918} in the On-line Encyclopedia of Integer Sequence [6]. This sequence is the first differences of \underline{A005803}, as noted in [6]. Then the minimal permutations with d descents and size d + 2 whose unique ascent is 1 (d + 2) are a combinatorial interpretation of the first differences of \underline{A005803}.

Corollary 24. The minimal permutations with d descents and size d + 2 having the first or the second sequence of descents starting with d + 2 and ending with 1 are enumerated by the sequence (h)_{d} defined as follows:

(h)_{d} = 2^{d} − 2d.  (12)

Proof. The number of minimal permutations with d descents and size d + 2 whose first sequence of descents is (d + 2) ⋯ 1 is given by the difference between the number of minimal permutations with d descents and size d + 2 having 1 as the bottom element of the diamond (see Theorem 21) and the number of those having the pair 1 (d + 2) as unique ascent (see Corollary 23), that is

2^{d+1} − 2(d + 1) − (2^{d} − 2) = 2^{d} − 2d.

The number of minimal permutations with d descents and size d + 2 whose second sequence of descents is (d+2) ⋯ 1 is obtained in a similar way from Theorem 19 and Corollary 23.

Corollary 25. The minimal permutations with d descents and size d + 2 having d + 2 as the first entry and 1 as the last one are enumerated by the sequence (k)_{d} defined as follows:

(k)_{d} = 2^{d} − d(d − 1) − 2.  (13)

Proof. The number of minimal permutations with d descents and size d + 2 having 1 as the last entry is 2^{d+1} − d(d + 1) − 2 (see Corollary 22). If from this set we cancel those permutation having d + 2 as the top element of the diamond (see Corollary 24) we obtain the set of minimal permutations with d descents and size d + 2 having d + 2 as the first entry and 1 as the last one, whose cardinality is given by

2^{d+1} − d(d + 1) − 2 − (2^{d} − 2d) = 2^{d} − d(d − 1) − 2.

The first terms of the sequence (13) are 0, 0, 2, 10, 32, 84, 198 …, for d ≥ 2.

Shape of the permutation  Number of  Formula  OEIS  Reference

permutations

2, 8, 22, 52, 2^{d+1} − 2(d + 1) \underline{A005803} Theorems 19, 21

114, 240, 494, …

0, 2, 10, 32,  2^{d+1} − d(d + 1) − 2  Corollaries 20, 22

84, 198, 438, …

2, 6, 14, 30,  2^{d} − 2  \underline{A000918} Corollary 23

62, 126, 254, …

0, 2, 8, 22,  2^{d} − 2d  \underline{A005803} Corollary 24

52, 114, 240, …

0, 0, 2, 10,  2^{d} − d(d − 1) − 2  Corollary 25

32, 84, 198, …

Table 2: Number sequences for some subsets of minimal permutations with d descents and size d + 2, d ≥ 2. OEIS refers to entry in [6].

References

[1] J.-L. Baril and R. Vernay, Whole mirror duplication-random loss model and pattern avoiding permutations, Inform. Process. Lett. 110 (2010), 474–480.

[2] M. Bouvel and E. Pergola, Posets and permutations in the duplication-loss model: Minimal permutations with d descents, Theoret. Comput. Sci. 411 (2010), 2487–2501.

[3] M. Bouvel and D. Rossin, A variant of the tandem duplication-random loss model of genome rearrangement, Theoret. Comput. Sci., 410 (2009), 847–858.

[4] K. Chaudhuri, K. Chen, R. Mihaescu, and S. Rao, On the tandem duplication-random loss model of genome rearrangement, in Proc. 17th Ann. ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM, 2006, pp. 564–570.

[5] T. Mansour and S. H. F. Yan, Minimal permutations with d descents, European J. Combin. 31 (2010), 1445–1460.

[6] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 05A05. Keywords: minimal permutation, enumeration.

(Concerned with sequences \underline{A000918} and \underline{A005803}.)

Received April 29 2015; revised version received August 25 2015. Published in Journal of Integer Sequences, September 8 2015.

Return to Journal of Integer Sequences home page.