An Asymptotic Formula for the Number of Stabilized-Interval-Free Permutations

Hyungju Park Department of Mathematical Sciences Seoul National University 08826 Seoul Republic of Korea

                    parkhyoungju@snu.ac.kr

Abstract Callan introduced stabilized-interval-free (SIF) permutations, and Ardila, Rincón, and Williams showed that connected positroids bijectively correspond to SIF permutations unless the underlying set is a singleton. In this paper, we derive an approximate formula for the number of SIF permutations on the set {1, …, N} that refines the previous result conjectured by Callan and proved by Salvatore and Tauraso.

1 Introduction

Let [N] denote the set {1, …, N} for a positive integer N. A derangement of the set [N] is a permutation of the set without any fixed point. Let d_{N} denote the number of derangements on the set [N]. The following classical formula for the number d_{N}

d_{N} = N! ∑_{i=0}^{N} \frac{(−1)^{i}}{i!} ,

which is the sequence \underline{A000166} in the On-Line Encyclopedia of Integer Sequences (OEIS) [3], is well known. Hassani [4, Thm. 1.1] proved that d_{N} = ⌊\frac{N!}{e} + α⌋ for every real number α ∈ [\frac{1}{3}, \frac{1}{2}]. This implies that the following approximate equality

d_{N} = \frac{N!}{e} + O(1)

holds. Moreover, Hassani [5] showed that the coefficients of the lower degree terms of this approximation are alternating Bell numbers B_{k}

d_{N} = \frac{N!}{e} + ∑_{k=1}^{r}(−1)^{N+k+1} \frac{B_{k}}{N^{k}} + O(N^{−r−1}).

These results all imply that the proportion of derangements among all permutations of the set [N] is given by the following expression

\frac{d_{N}}{N!} = \frac{1}{e} + O(N^{−k})

where k is any positive integer.

Callan [2] introduced a subclass of derangements known as stabilized-interval-free (SIF) permutations, which satisfy a stronger condition than ordinary derangements. Callan proposed a conjectural asymptotic proportion of SIF permutations among all permutations of the set [N]. Specifically, it is conjectured that the proportion of SIF permutations among all permutations of [N] is

\frac{1}{e}(1 − \frac{1}{N} − \frac{5}{2N^{2}} + O(N^{−3})).

Salvatore and Tauraso [8] proved this conjecture using the recursive formula for the number of SIF permutations.

SIF permutations are related to mathematical objects called positroids. Postnikov [7] introduced positroids, which are matroids represented by a real matrix with nonnegative maximal minors, and showed that positroids bijectively correspond to various combinatorial objects such as decorated permutations, Grassmann necklaces, Γ -diagrams, and moveequivalence classes of reduced plabic graphs. Ardila, Rincón, and Williams [1] showed that connected components of positroids form a noncrossing partition of the underlying set. Moreover, they showed that a positroid on a set of cardinality at least 2 is connected if and only if it corresponds to a stabilized-interval-free (SIF) permutation. This result implies that the proportion of connected positroids among all positroids on the set [N] approaches \frac{1}{e^{2}} as N → ∞. As pointed out in [1], this result stands in stark contrast to the fact, proven by Lowrance, Oxley, Semple, and Welsh in [6], that asymptotically almost all matroids are connected.

We present an alternative method for obtaining an asymptotic formula for the proportion of SIF permutations among all permutations, based on combinatorial arguments. Using our method, we may further compute lower degree terms of the asymptotic formula for the proportion of SIF permutations as follows:

\frac{1}{e}(1 − \frac{1}{N} − \frac{5}{2N^{2}} − \frac{32}{3N^{3}} − \frac{1643}{24N^{4}} − \frac{23017}{40N^{5}} + O(N^{−6})).

2 The number of λ-cyclic intervals

A cyclic interval of [N] is a subset of consecutive numbers modulo N. More generally, we define the notion of λ-cyclic interval associated with a partition λ.

Definition 1. For a partition λ = (λ_{1}, …, λ_{l}) ⊢ n, a collection of disjoint cyclic intervals is called a λ-cyclic interval if the partition obtained by sizes of cyclic intervals is λ.

The following proposition provides a formula for the number of λ-cyclic intervals in the set [N].

Proposition 2. Let λ = (λ_{1}, ..., λ_{l}) ⊢ n be a partition that is not the partition (N) with only one part. The number of λ-cyclic intervals in the set [N] is expressed as follows:

N · \binom{N − n + l − 1}{l − 1}\frac{(l − 1)!}{∏_{i} m_{i}(λ)!}

where m_{i}(λ) is the number of indices j such that λ_{j} = i.

Proof. Let α = (α_{1}, …, α_{l}) ⊨ n be a composition whose weakly decreasing rearrangement is λ. There are \frac{l!}{∏_{i} m_{i}(λ)!} possible number of such compositions α. The number of ways to choose the first cyclic interval of length α_{1} is N, and the number of ways to choose other intervals of length α_{2}, …, α_{l} according to this order is \binom{N−n+l−1}{l−1}. Multiplying the number of choices in each step, the total number of choices is

N · \binom{N − n + l − 1}{l − 1}\frac{l!}{∏_{i} m_{i}(λ)!}

Since each λ-cyclic interval is counted exactly l times, dividing the total count by l gives us the desired result.

3 The number of SIF permutations stabilizing a λcyclic interval

Callan [2] introduced a subclass of derangements known as stabilized-interval-free permutations, which satisfy a stronger condition than ordinary derangements.

Definition 3. A permutation π of the set [N] is stabilized-interval-free (SIF) if for every proper interval I ⊂ [N], π(I) ≠ I.

We define sif_{N} to be the number of SIF permutations of the set [N]. For each permutation π of the set [N], we let I_{π} denote the collection of all minimal nonempty cyclic intervals stabilized by π. The collection of lengths of cyclic intervals in I_{π}, arranged in weakly decreasing order, forms a partition of the integer N. By definition, a permutation π is a SIF permutation if and only if the partition obtained from the collection of lengths of cyclic intervals in I_{π} is (N). A direct consequence of Proposition 2 is a formula for the number of pairs (π, J), where π is a derangement on the set [N], and J is a λ-cyclic interval contained in the collection of cyclic intervals I_{π}.

Corollary 4. Let λ = (λ_{1}, …, λ_{l}) ⊢ n be a partition that is not (N) and let sif_{λ} denote ∏_{i=1}^{l} sif_{λ_{i}}. Let D_{λ}(N) be the collection of all pairs (π, J) of a derangement π of the set [N] and a λ-cyclic interval J contained in the collection I_{π}. The number of pairs (π, J) ∈ D_{λ}(N) is obtained by the following formula:

|D_{λ}(N)| = sif_{λ} ·d_{N−n} · N · \binom{N − n + l − 1}{l − 1}\frac{(l − 1)!}{∏_{i} m_{i}(λ)!}.

This formula can be used to derive an asymptotic formula for the number |D_{λ}(N)| as follows:

|D_{λ}(N)| = \frac{N!}{e} · (\frac{sif_{λ}}{∏_{i} m_{i}(λ)!} · \frac{1}{(N − 1)(N − 2) ⋯ (N − n + l)} + O(N^{−k}))  (1)

where k is an arbitrary positive integer.

Proof. Since every cyclic intervals in I_{π} is minimal stabilized cyclic intervals of π, a pair (π, J) satisfying the relation J ⊆ I_{π} is determined by a λ-cyclic interval J, SIF permutations of each cyclic intervals in J, and a derangement of the set [N] \ (⋃ J). Therefore the first statement is immediate from Proposition 2. The second statement is obtained by substituting the formula d_{N−n} = \frac{(N−n)!}{e}(1 + O(N^{−k})) for the number of derangements where k is an arbitrary positive integer.

4 Asymptotic formula for the number of SIF permutations

We prove the main result of this paper in this section. Using the result, we derive a more precise asymptotic formula for the number of SIF permutations. For a partition λ, let |λ| denote the sum of all parts of λ and let l(λ) denote the number of parts of λ.

Theorem 5. For a given positive integer k, the number of SIF permutations of the set [N] is expressed by the following formula:

sif_{N} = \frac{N!}{e}( ∑_{λ} \frac{sif_{λ}(−1)^{l(λ)}}{(∏_{i} m_{i}(λ)!)(N − 1)(N − 2) ⋯ (N − |λ| + l)} + O(N^{−k−1}))

where the sum runs over all partitions λ = (λ_{1}, …, λ_{l(λ)}) such that |λ| − l(λ) ≤ k and 1 < λ_{l(λ)}. If the partition λ is the empty partition of the integer 0, we treat the term

\frac{sif_{λ}(−1)^{l}}{(∏_{i} m_{i}(λ)!)(N − 1)(N − 2) ⋯ (N − |λ| + l)}

as a vacuous product with a value of 1.

Proof. By the inclusion-exclusion principle, the number of SIF permutations on the set [N] is given by the sum ∑_{λ}(−1)^{l(λ)}|D_{λ}(N)| for all partitions λ such that |λ| ≤ N, λ ≠ (N). Corollary 4 implies that |D_{λ}(N)| = \frac{N!}{e} · O(N^{−k−1}) unless |λ| − l(λ) ≤ k. Therefore, the sum can be expressed by using the big O notation

sif_{N} = ∑_{|λ|−l(λ)≤k}(−1)^{l(λ)}|D_{λ}(N)| + \frac{N!}{e} · O(N^{−k−1}).

Substituting the asymptotic formula (1) for the number |D_{λ}(N)|, the result follows.

To obtain an explicit formula for the asymptotic number of SIF permutations, we make use of a well-known partial fraction decomposition formula for the inverse of the falling factorial (x)_{n} := x(x − 1) ⋯ (x − n + 1). This formula is given by:

\frac{(n − 1)!}{(x)_{n}} = \frac{(n − 1)!}{x(x − 1) ⋯ (x − n + 1)} = ∑_{i=0}^{n−1} \frac{(−1)^{n−1+i}\binom{n−1}{i}}{x − i},  (2)

which can be derived by induction.

To compute the asymptotic formula up to the error term O(N^{−k−1}), it suffices to consider partitions λ for which |λ| − l(λ) ≤ k by Theorem 5. We will do this for k = 5. The condition |λ| − l(λ) = 1, 2, 3, 4, 5 is satisfied by the following collections of partitions:

|λ| − l(λ) = 1 : {(2)}
|λ| − l(λ) = 2 : {(3), (2, 2)}
|λ| − l(λ) = 3 : {(4), (3, 2), (2, 2, 2)}
|λ| − l(λ) = 4 : {(5), (4, 2), (3, 3), (3, 2, 2), (2, 2, 2, 2)}
|λ| − l(λ) = 5 : {(6), (5, 2), (4, 3), (4, 2, 2), (3, 3, 2), (3, 2, 2, 2), (2, 2, 2, 2, 2)}.

Notice that each partition λ satisfying |λ| − l(λ) = k corresponds to a partition of k, obtained by subtracting 1 from each part of the partition. For each of these collections of partitions, we can compute the sum

∑_{λ} \frac{sif_{λ}(−1)^{l(λ)}}{∏_{i} m_{i}(λ)!}

using the sequence sif_{N} listed as entry \underline{A075834} in Sloane’s OEIS [3] as follows:

|λ| − l(λ) = 1 : ∑_{λ} \frac{sif_{λ}(−1)^{l(λ)}}{∏_{i} m_{i}(λ)!} = 1

|λ| − l(λ) = 2 : ∑_{λ} \frac{sif_{λ}(−1)^{l(λ)}}{∏_{i} m_{i}(λ)!} = −2 + \frac{1^{2}}{2!} = −\frac{3}{2}

|λ| − l(λ) = 3 : ∑_{λ} \frac{sif_{λ}(−1)^{l(λ)}}{∏_{i} m_{i}(λ)!} = −7 + 2 · 1 − \frac{1^{3}}{3!} = −\frac{31}{6}

|λ| − l(λ) = 4 : ∑_{λ} \frac{sif_{λ}(−1)^{l(λ)}}{∏_{i} m_{i}(λ)!} = −34 + 7 + \frac{2^{2}}{2!} − \frac{2 · 1^{2}}{2!} + \frac{1^{4}}{4!} = −\frac{623}{24}

|λ| − l(λ) = 5 : ∑_{λ} \frac{sif_{λ}(−1)^{l(λ)}}{∏_{i} m_{i}(λ)!} = −206 + 34 + 7 · 2 − \frac{7 · 1^{2}}{2!} − \frac{2^{2} · 1}{2!} + \frac{2 · 1^{3}}{3!} − \frac{1^{5}}{5!}

= −\frac{6527}{40}.

Here we used the values of sif_{N} for N = 1, …, 6, which are 1, 1, 2, 7, 34, 206. Therefore, we have the following asymptotic formula for the number sif_{N} up to the error term O(N^{−6}):

sif_{N} = \frac{N!}{e}(1 − \frac{1}{N − 1}

− \frac{3}{2} \frac{1}{(N − 1)(N − 2)}

− \frac{31}{6} \frac{1}{(N − 1)(N − 2)(N − 3)}

− \frac{623}{24} \frac{1}{(N − 1)(N − 2)(N − 3)(N − 4)}

− \frac{6527}{40} \frac{1}{(N − 1)(N − 2)(N − 3)(N − 4)(N − 5)} + O(N^{−6}))

We can expand the above formula using the partial fraction decomposition formula 2 for the inverse of the falling factorial and the series expansion

\frac{1}{N − m} = ∑_{i=1}^{∞} \frac{m^{i−1}}{N^{i}} .

sif_{N} = \frac{N!}{e}(1 − (\frac{1}{N} + \frac{1}{N^{2}} + \frac{1}{N^{3}} + ⋯)

− \frac{3}{2}((\frac{1}{N} + \frac{2}{N^{2}} + \frac{2^{2}}{N^{3}} + ⋯) − (\frac{1}{N} + \frac{1}{N^{2}} + \frac{1}{N^{3}} + ⋯))

− \frac{31}{6} \frac{1}{2!}((\frac{1}{N} + \frac{3}{N^{2}} + \frac{3^{2}}{N^{3}} + ⋯) − \binom{2}{1}(\frac{1}{N} + \frac{2}{N^{2}} + \frac{2^{2}}{N^{3}} + ⋯)

+ (\frac{1}{N} + \frac{1}{N^{2}} + \frac{1}{N^{3}} + ⋯))

− \frac{623}{24} \frac{1}{3!}((\frac{1}{N} + \frac{4}{N^{2}} + \frac{4^{2}}{N^{3}} + ⋯) − \binom{3}{2}(\frac{1}{N} + \frac{3}{N^{2}} + \frac{3^{2}}{N^{3}} + ⋯)

+ \binom{3}{1}(\frac{1}{N} + \frac{2}{N^{2}} + \frac{2^{2}}{N^{3}} + ⋯) − (\frac{1}{N} + \frac{1}{N^{2}} + \frac{1}{N^{3}} + ⋯))

− \frac{6527}{40} \frac{1}{4!}((\frac{1}{N} + \frac{5}{N^{2}} + \frac{5^{2}}{N^{3}} + ⋯) − \binom{4}{3}(\frac{1}{N} + \frac{4}{N^{2}} + \frac{4^{2}}{N^{3}} + ⋯)

+ \binom{4}{2}(\frac{1}{N} + \frac{3}{N^{2}} + \frac{3^{2}}{N^{3}} + ⋯) − \binom{4}{1}(\frac{1}{N} + \frac{2}{N^{2}} + \frac{2^{2}}{N^{3}} + ⋯)

+ (\frac{1}{N} + \frac{1}{N^{2}} + \frac{1}{N^{3}} + ⋯)) + O(N^{−6}))

Therefore, the coefficients of the terms \frac{1}{N^{k}} for k = 1, 2, 3, 4, 5 are given by:

k = 1 : 1
k = 2 : − 1 − \frac{3}{2}(2 − 1) = −\frac{5}{2}
k = 3 : − 1 − \frac{3}{2}(2^{2} − 1) − \frac{31}{6 · 2!}(3^{2} − \binom{2}{1}2^{2} + 1) = −\frac{32}{3}
k = 4 : − 1 − \frac{3}{2}(2^{3} − 1) − \frac{31}{6 · 2!}(3^{3} − \binom{2}{1}2^{3} + 1) − \frac{623}{24 · 3!}(4^{3} − \binom{3}{2}3^{3} + \binom{3}{1}2^{3} − 1)

= −\frac{1643}{24}

k = 5 : − 1 − \frac{3}{2}(2^{4} − 1) − \frac{31}{6 · 2!}(3^{4} − \binom{2}{1}2^{4} + 1) − \frac{623}{24 · 3!}(4^{4} − \binom{3}{2}3^{4} + \binom{3}{1}2^{4} − 1)

− \frac{6527}{40 · 4!}(5^{4} − \binom{4}{3}4^{4} + \binom{4}{2}3^{4} − \binom{4}{1}2^{4} + 1) = −\frac{23017}{40}.

This gives the following asymptotic formula for sif_{N}:

sif_{N} = \frac{N!}{e}(1 − \frac{1}{N} − \frac{5}{2N^{2}} − \frac{32}{3N^{3}} − \frac{1643}{24N^{4}} − \frac{23017}{40N^{5}} + O(N^{−6})).

5 Acknowledgment

We thank an anonymous referee for several helpful comments and suggestions.

References

[1] Federico Ardila, Felipe Rincón, and Lauren Williams, Positroids and non-crossing partitions, Trans. Amer. Math. Soc. 368 (2016), 337–363.

[2] David Callan, Counting stabilized-interval-free permutations, J. Integer Sequences 7 (2004), Article 04.1.8.

[3] N. J. A. Sloane et. al., The On-Line Encyclopedia of Integer Sequences, 2023. Available

   at https://oeis.org.

[4] Mehdi Hassani, Derangements and applications, J. Integer Sequences 6 (2003), Article 03.1.2.

[5] Mehdi Hassani, Derangements and alternating sum of permutations by integration, J. Integer Sequences 23 (2020), Art. 20.7.8.

[6] Lisa Lowrance, James Oxley, Charles Semple, and Dominic Welsh, On properties of almost all matroids, Adv. in Appl. Math. 50 (2013), 115–124.

[7] Alexander Postnikov, Total positivity, Grassmannians, and networks, preprint, 2006.

   Available at http://www-math.mit.edu/~apost/papers/tpgrass.pdf.

[8] Paolo Salvatore and Roberto Tauraso, The operad Lie is free, J. Pure Appl. Algebra 213 (2009), 224–230.

2020 Mathematics Subject Classification: Primary 05A16; Secondary 05A05. Keywords: derangement, stabilized-interval-free permutation, positroid.

(Concerned with sequences \underline{A000166} and \underline{A075834}.)

Received May 4 2023; revised versions received October 27 2023; November 14 2023. Published in Journal of Integer Sequences, November 15 2023.

Return to Journal of Integer Sequences home page.