Partition and composition matrices: two matrix analogues of set partitions

Résumé : Ce papier introduit deux analogues matriciels des partitions d'ensembles: les matrices de composition et de partition. Ces deux analogues sont le produit naturel du relèvement de l'application entre suites de montées et matrices d'entiers introduite dans Dukes & Parviainen (2010). Nous démontrons que les matrices de partition sont en bijection avec les tables d'inversion, les tables d'inversion croissantes correspondant aux matrices de partition avec une relation d'ordre sur les lignes. Les matrices de partition s-diagonales sont classées en fonction de leurs tables d'inversion. Les matrices de partition bidiagonales sont énumérées par la méthode de matrices de transfert et ont même cardinalité que les permutations triables par deux piles en parallèle. Nous montrons que les matrices de composition sur l'ensemble $X$ sont en bijection avec les ensembles ordonnés (2+2)-libres sur $X$. Nous prouvons que les paires de suites de montées et de permutations sont en bijection avec les ensembles ordonnés (2+2)-libres dont les éléments sont les cycles d'une permutation, et nous utilisons cette relation pour exprimer le nombre d'ensembles ordonnés (2+2)-libres sur $\{1,\ldots,n\}$.
Type de document :
Communication dans un congrès
Bousquet-Mélou, Mireille and Wachs, Michelle and Hultman, Axel. 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), pp.221-232, 2011, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01215096
Contributeur : Coordination Episciences Iam <>
Soumis le : mardi 13 octobre 2015 - 15:06:42
Dernière modification le : mardi 7 mars 2017 - 15:14:43
Document(s) archivé(s) le : jeudi 27 avril 2017 - 00:08:52

Fichier

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

Identifiants

  • HAL Id : hal-01215096, version 1

Collections

Citation

Anders Claesson, Mark Dukes, Martina Kubitzke. Partition and composition matrices: two matrix analogues of set partitions. Bousquet-Mélou, Mireille and Wachs, Michelle and Hultman, Axel. 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), pp.221-232, 2011, DMTCS Proceedings. 〈hal-01215096〉

Partager

Métriques

Consultations de la notice

137

Téléchargements de fichiers

97