A Note on a Permutation Statistic

Tamás Lengyel Occidental College 1600 Campus Road Los Angeles, CA 90041 USA

                        lengyel@oxy.edu

Abstract We study the length of the initial up-down alternating segment of a permutation of [n] selected uniformly at random. It turns out that as n tends to infinity, the expected value and the standard deviation of this statistic converge to small constants.

1 Introduction

Analyzing properties of permutation statistics is a popular subject in combinatorics, cf. Bóna [1]. There has been much recent work on determining and statistically analyzing the length of the longest increasing and alternating subsequences of random permutations, cf. Stanley [4]. A permutation a_{1}a_{2} ⋯ a_{n} of [n] is up-down alternating if a_{1} < a_{2} > a_{3} < a_{4} > ⋯ a_{n}. Let A_{n} denote the number of up-down alternating permutations of [n] = {1, 2, …, n}. André studied these numbers and established their relations to Euler and tangent numbers, cf. Comtet [3, pp. 258–259]. It is well known that 2A_{n+1} = ∑_{k=0}^{n} \binom{n}{k}A_{k}A_{n−k} for n ≥ 1 with A_{0} = A_{1} = 1. The first few terms of this sequence are

1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, 353792, 2702765, …,

cf. \underline{A000111} in the On-Line Encyclopedia of Integer Sequences. For their exponential generating function we have the remarkable exponential generating function identity

A(x) = ∑_{k=0}^{∞} \frac{A_{k}}{k!} x^{k} = sec(x) + tan(x),  (1)

cf. Comtet [3]. The convergence radius easily follows as well as

A_{n}/n! ∼ 2 (\frac{2}{π} )^{n+1}  (2)

as n → ∞, cf. Borwein et al. [2].

We are interested in the initial up-down alternating segments of the permutations. Let X_{n} denote the length of the initial up-down alternating sequence of a permutation of [n] selected uniformly at random, i.e., we set X_{n} = n for an up-down alternating permutation, and otherwise, X_{n} = 2k or X_{n} = 2k + 1 if a_{1} < a_{2} > a_{3} < ⋯ > a_{2k−1} < a_{2k} < a_{2k+1} or a_{1} < a_{2} > a_{3} < ⋯ < a_{2k} > a_{2k+1} > a_{2k+2}, respectively. Clearly, 1 ≤ X_{n} ≤ n and X_{n} = n exactly if the permutation is up-down alternating. The random variable X_{n} has some surprising properties. We will see in Theorems 1 and 3 that the expected value and standard deviation of X_{n} depends only very slightly on n and the limits of these moments are small constants. Theorem 4 shows that for a large n the probability P (X_{n} = k) decreases exponentially as k grows while Corollary 2 confirms that P (X_{n} = k) becomes constant for n > k.

2 Main results

Theorem 1. For 1 ≤ k ≤ n − 1 we have that

P (X_{n} = k) = P (X_{n} ≥ k) − P (X_{n} ≥ k + 1) = \frac{A_{k}}{k!} − \frac{A_{k+1}}{(k + 1)!},  (3)

EX_{n} = ∑_{k=1}^{n} \frac{A_{k}}{k!} ,

and lim_{n→∞} EX_{n} = sec(1) + tan(1) − 1 ≈ 2.40822.

Proof. We use the fact that for any positive integer valued random variable X_{n}

EX_{n} = ∑_{k=1}^{∞} P (X_{n} ≥ k).  (4)

We observe that P (X_{n} = n) = A_{n}/n!. On the other hand, determining P (X_{n} = k) for other values of k seems complicated, however, as it turns out, calculating P (X_{n} ≥ k) for 1 ≤ k ≤ n − 1 is fairly simple:

P (X_{n} ≥ k) = \frac{\binom{n}{k}A_{k}(n − k)!}{n!} = \frac{A_{k}}{k!} ,  (5)

since we can pick k elements for the initial segment in \binom{n}{k} ways and place them in up-down alternating order in A_{k} ways, while the other n − k elements can be put in arbitrary order. Identity (5) also holds for k = n. Now (5) and (4) imply identities (3) and

EX_{n} = ∑_{k=1}^{n} \frac{A_{k}}{k!} .

The limit follows by the exponential generating function (1).

Theorem 1 implies the somewhat surprising

Corollary 2. The probability P (X_{n} = k) does not depend on n as long as n > k.

The following theorem is straightforward.

Theorem 3. We set B(x) = (A(x) − 1)/x. For the standard deviation of X_{n} we have

σ(X_{n}) = (∑_{k=1}^{n−1} k^{2} (\frac{A_{k}}{k!} − \frac{A_{k+1}}{(k + 1)!}) + n^{2} \frac{A_{n}}{n!} − (EX_{n})^{2})^{1/2} ,

and

lim_{n→∞} σ(X_{n}) = ((A”(x) + A′(x)) − (B”(x) + B′(x)) |_{x=1} −(EX_{n})^{2})^{1/2}
≈ 2.09958.

The next theorem quantifies P (X_{n} = k) for any k ≥ 4 and sufficiently large n.

Theorem 4. For a large n and k < n, the probability P (X_{n} = k) decreases exponentially as k grows. More precisely, for k ≥ 4 and a large enough n, we have that

P (X_{n} = k) ≈ 2 (\frac{2}{π} )^{k+1} (1 − \frac{2}{π} ) .

Proof. By the asymptotic result (2), the exact distribution (3) and some numerical calculation show that the absolute difference between P (X_{n} = k) and its approximated value is less than 10^{−3} for k ≥ 4.

References

[1] M. Bóna, Combinatorics of Permutations, Chapman & Hall/CRC, 2004.

[2] J. M. Borwein, P. B. Borwein, and K. Dilcher, Pi, Euler Numbers, and Asymptotic Expansions, Amer. Math. Monthly 96 (1989), 681–687.

[3] L. Comtet, Advanced Combinatorics, D. Reidel Publishing Co., 1974.

[4] R. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999.

2010 Mathematics Subject Classification: Primary 05A05; Secondary 05A15, 60C05. Keywords: alternating permutation, generating function, combinatorial probability.

(Concerned with sequence \underline{A000111}.)

Received July 28 2019; revised versions received August 16 2019; August 19 2019. Published in Journal of Integer Sequences, August 19 2019.

Return to Journal of Integer Sequences home page.