The Infinite Limit of Separable Permutations

Abstract

Let $P_n^{\text{sep}}$ denote the uniform probability measure on the set of separable permutations in $S_n$. Let ${\mathbb{N}}^{\ast }=\mathbb{N}\cup \{\infty \}$ with an appropriate metric and denote by $S(\mathbb{N},{\mathbb{N}}^{\ast })$ the compact metric space consisting of functions $\sigma =\{{\sigma }_i{\}}_{i=1}^{\infty }$ from $\mathbb{N}$ to ${\mathbb{N}}^{\ast }$ which are injections when restricted to ${\sigma }^{-1}(\mathbb{N})$\rm; that is, if ${\sigma }_i={\sigma }_j$, $i\ne j$, then ${\sigma }_i=\infty$. Extending permutations $\sigma \in S_n$ by defining ${\sigma }_j=j$, for $j>n$, we have $S_n\subset S(\mathbb{N},{\mathbb{N}}^{\ast })$. We show that $\{P_n^{\text{sep}}{\}}_{n=1}^{\infty }$ converges weakly on $S(\mathbb{N},{\mathbb{N}}^{\ast })$ to a limiting distribution of regenerative type, which we calculate explicitly.

A remark has been added that discusses the results of the paper in the context of the four natural symmetries that exist in a uniformly random separable permutation