Partition non croisée

Un article de Wikipédia, l'encyclopédie libre.
Au dessus, les 42 partitions non croisées d'un ensemble à 5 éléments. En dessous, les 10 partitions restantes.

En mathématiques, une partition non croisée est une partition d'un ensemble fini en blocs qui ne se croisent pas.

Définition[modifier | modifier le code]

Soit un entier naturel et une partition de l'ensemble . Cette partition est dite non croisée[1] si pour tout , les blocs et ne sont pas croisés, c'est-à-dire que pour tout il n'est pas vrai que .

Par exemple est une partition non croisée pour mais n'en est pas une.

Représentations visuelles[modifier | modifier le code]

Il existe deux manières simples de se représenter une partition non croisée dans l'espace.

Représentation par des ponts[modifier | modifier le code]

La première représentation consiste à placer points numérotés de 1 à sur une ligne. Si avec alors on représente en traçant un pont reliant les points numérotés et puis et , ..., puis et . Si est une partition de alors on la représente en traçant les représentations de tous ses blocs comme décrit précédemment. Cette partition est non croisée si et seulement si les ponts dessinés ne se croisent pas.

Représentation dans le cercle[modifier | modifier le code]

La deuxième représentation consiste à placer points numérotés de 1 à sur un cercle. Si alors on représente en traçant l'enveloppe convexe des points dans le cercle. Si est une partition de alors on la représente en traçant les représentations de tous ses blocs comme décrit précédemment. Cette partition est non croisée si et seulement si les enveloppe convexes dessinées sont disjointes.

Propriétés[modifier | modifier le code]

Structure de treillis[modifier | modifier le code]

Les 14 partitions non croisées d'un ensemble à 4 éléments représentées dans un diagramme de Hasse.

On peut définir une relation d'ordre partiel dans l'ensemble des partitions (quelconques) de de la manière suivante : pour deux partitions et , on a si et seulement si pour tout bloc il existe un bloc tel que . On dit alors que est plus fine que . L'ensemble des partitions muni de cette relation d'ordre est un treillis[2] dont les opérations sont notées ici et .

L'ensemble des partitions non croisées muni de ce même ordre est également un treillis[1]. Cependant ce treillis n'est pas un sous-treillis des partitions quelconques. En effet, si sont deux partitions non croisées alors n'est pas forcément une partition non croisée. En revanche est bien une partition non croisée.

Si est une partition (quelconque) on construit sa fermeture non croisée de la manière suivante :

on définit un graphe à k sommets numérotés de 1 à k où les sommets i et j sont reliés si et seulement si les blocs et sont croisés. Si on appelle les composantes connexes du graphe alors les blocs de sont les . La fermeture non croisée[1] d'une partition est donc une partition non croisée qui est moins fine que et elle est la plus fine parmi toutes les partitions non croisées moins fine que . Si sont deux partitions non croisées alors la fermeture non croisée de est la plus fine des partitions non croisées moins fine que et .

Propriétés combinatoires[modifier | modifier le code]

  • Le nombre de partitions non croisées de avec blocs de taille 1, blocs de taille 2, blocs de taille 3, etc vaut[1] et .
  • Le nombre de partitions non croisées à blocs de correspond[1] au nombre de Narayana .
  • Le nombre de partitions non croisées de correspond[1] au nombre de Catalan .

Complémentaire de Kreweras[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. a b c d e et f G Kreweras, « Sur les partitions non croisees d'un cycle », Discrete Mathematics, vol. 1, no 4,‎ , p. 333-350 (lire en ligne)
  2. T Juillard, « Partitions d'un n-gone », , p. 3

Voir aussi[modifier | modifier le code]