# On square permutations

Abstract : Severini and Mansour introduced $\textit{square polygons}$, as graphical representations of $\textit{square permutations}$, that is, permutations such that all entries are records (left or right, minimum or maximum), and they obtained a nice formula for their number. In this paper we give a recursive construction for this class of permutations, that allows to simplify the derivation of their formula and to enumerate the subclass of square permutations with a simple record polygon. We also show that the generating function of these permutations with respect to the number of records of each type is algebraic, answering a question of Wilf in a particular case.
Keywords :
Type de document :
Communication dans un congrès
Roesler, Uwe. Fifth Colloquium on Mathematics and Computer Science, 2008, Kiel, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science, pp.207-222, 2008, DMTCS Proceedings
Domaine :
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01194689
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 7 septembre 2015 - 12:51:12
Dernière modification le : jeudi 11 janvier 2018 - 06:17:42
Document(s) archivé(s) le : mardi 8 décembre 2015 - 13:03:05

### Fichier

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

### Identifiants

• HAL Id : hal-01194689, version 1

### Citation

Enrica Duchi, Dominique Poulalhon. On square permutations. Roesler, Uwe. Fifth Colloquium on Mathematics and Computer Science, 2008, Kiel, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science, pp.207-222, 2008, DMTCS Proceedings. 〈hal-01194689〉

### Métriques

Consultations de la notice

## 195

Téléchargements de fichiers