The infinite limit of separable permutations. Issue 4 (20th May 2021)

• Record Type: Journal Article
• Authors: Pinsky, Ross G.
• Is Part Of: Random structures & algorithms. Volume 59:Issue 4(2021)
• Page Start: 622
• Page End: 639
• Publication Date: 2021-05-20
• Subjects: random permutation -- Schröder numbers -- separable permutations; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21014
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: Let P n sep denote the uniform probability measure on the set of separable permutations in S n . Let ℕ ∗ = ℕ ∪ { ∞ } with an appropriate metric and denote by S ( ℕ, ℕ ∗ ) the compact metric space consisting of functions σ = { σ i } i = 1 ∞ from ℕ to ℕ ∗ which are injections when restricted to σ − 1 ( ℕ ) ; that is, if σ i = σ j, i ≠ j, then σ i = ∞ . Extending permutations σ ∈ S n by defining σ j = j, for j > n, we have S n ⊂ S ( ℕ, ℕ ∗ ) . We show that { P n sep } n = 1 ∞ converges weakly on S ( ℕ, ℕ ∗ ) to a limiting distribution of regenerative type, which we calculate explicitly.