## Blitvić, Natasha - SIF Permutations and Chord-Connected Permutations

dmtcs:2443 - Discrete Mathematics & Theoretical Computer Science, January 1, 2014, DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014)
SIF Permutations and Chord-Connected Permutations

Authors: Blitvić, Natasha

A <i>stabilized-interval-free </i> (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 <i>moment-cumulant formula </i>of Speicher, in the context of the <i>free probability theory </i>of Voiculescu. The probability distributions that appear are the exponential and the complex Gaussian.

Source : oai:HAL:hal-01207573v1
Volume: DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014)
Section: Proceedings
Published on: January 1, 2014
Submitted on: November 21, 2016
Keywords: stabilized-interval-free permutations,chord-connected permutations,non-crossing partitions,complex Gaussian,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]