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.
Keywords :
Type de document :
Communication dans un congrès
Louis J. Billera and Isabella Novik. 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), 2014, Chicago, United States. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), pp.801-814, 2014, DMTCS Proceedings
Domaine :

Littérature citée [21 références]

https://hal.inria.fr/hal-01207573
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 1 octobre 2015 - 09:28:38
Dernière modification le : mardi 7 mars 2017 - 15:25:38
Document(s) archivé(s) le : samedi 2 janvier 2016 - 10:49:48

Fichier

dmAT0169.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

• HAL Id : hal-01207573, version 1

Citation

Natasha Blitvić. SIF Permutations and Chord-Connected Permutations. Louis J. Billera and Isabella Novik. 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), 2014, Chicago, United States. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), pp.801-814, 2014, DMTCS Proceedings. 〈hal-01207573〉

Métriques

Consultations de la notice

63

Téléchargements de fichiers