Skip to Main content Skip to Navigation
Conference papers

SIF Permutations and Chord-Connected Permutations

Abstract : A stabilized-interval-free (SIF) permutation on [n], introduced by Callan, is a permutation that does not stabilize any proper interval of [n]. Such permutations are known to be the irreducibles in the decomposition of permutations along non-crossing partitions. That is, if $s_n$ denotes the number of SIF permutations on [n], $S(z)=1+\sum_{n\geq1} s_n z^n$, and $F(z)=1+\sum_{n\geq1} n! z^n$, then $F(z)= S(zF(z))$. This article presents, in turn, a decomposition of SIF permutations along non-crossing partitions. Specifically, by working with a convenient diagrammatic representation, given in terms of perfect matchings on alternating binary strings, we arrive at the \emphchord-connected permutations on [n], counted by $\{c_n\}_{n\geq1}$, whose generating function satisfies $S(z)= C(zS(z))$. The expressions at hand have immediate probabilistic interpretations, via the celebrated moment-cumulant formula of Speicher, in the context of the free probability theory of Voiculescu. The probability distributions that appear are the exponential and the complex Gaussian.
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Thursday, October 1, 2015 - 9:28:38 AM
Last modification on : Wednesday, August 7, 2019 - 12:19:22 PM
Long-term archiving on: : Saturday, January 2, 2016 - 10:49:48 AM


Publisher files allowed on an open archive




Natasha Blitvić. SIF Permutations and Chord-Connected Permutations. 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), 2014, Chicago, United States. pp.801-814, ⟨10.46298/dmtcs.2443⟩. ⟨hal-01207573⟩



Record views


Files downloads