Partition non croisée

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

Au dessus, les 42 partitions non croisées d'un ensemble à 5 éléments. En dessous, les 10 partitions restantes.

Définition

Soit $n$ un entier naturel et $P=\{B_{1},\dots ,B_{k}\}$ une partition de l'ensemble $\{1,\dots ,n\}$. Cette partition est dite non croisée si pour tout $i\neq j$, les blocs $B_{i}$ et $B_{j}$ ne sont pas croisés, c'est-à-dire que pour tout $a,b\in B_{i},\,c,d\in B_{j}$ il n'est pas vrai que $a<c<b<d$.

Par exemple $\{\{1,2\},\{3,4\}\}$ est une partition non croisée pour $n=4$ mais $\{\{1,3\},\{2,4\}\}$ n'en est pas une.

Représentations visuelles

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

Représentation par des ponts

La première représentation consiste à placer $n$ points numérotés de 1 à $n$ sur une ligne. Si $B=\{b_{1},\dots ,b_{k}\}\subset \{1,\dots ,n\}$ avec $b_{1}<\dots <b_{k}$ alors on représente $B$ en traçant un pont reliant les points numérotés $b_{1}$ et $b_{2}$ puis $b_{2}$ et $b_{3}$, ..., puis $b_{k-1}$ et $b_{k}$. Si $P=\{B_{1},\dots ,B_{k}\}$ est une partition de $\{1,\dots ,n\}$ 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

La deuxième représentation consiste à placer $n$ points numérotés de 1 à $n$ sur un cercle. Si $B=\{b_{1},\dots ,b_{k}\}\subset \{1,\dots ,n\}$ alors on représente $B$ en traçant l'enveloppe convexe des points $b_{1},\dots ,b_{k}$ dans le cercle. Si $P=\{B_{1},\dots ,B_{k}\}$ est une partition de $\{1,\dots ,n\}$ 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 enveloppes convexes dessinées sont disjointes.

Propriétés

Structure de treillis

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 $\preceq$ dans l'ensemble des partitions (quelconques) de $\{1,\dots ,n\}$ de la manière suivante : pour deux partitions $P$ et $Q$, on a $Q\preceq P$ si et seulement si pour tout bloc $B\in P$ il existe un bloc $C\in Q$ tel que $B\subset C$. On dit alors que $P$ est plus fine que $Q$. L'ensemble des partitions muni de cette relation d'ordre est un treillis dont les opérations sont notées ici $\vee$ et $\wedge$.

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

Si $P=\{B_{1},\dots ,B_{k}\}\subset \{1,\dots ,n\}$ est une partition (quelconque) on construit sa fermeture non croisée ${\overline {P}}$ de la manière suivante :

on définit un graphe $G(P)$ à k sommets numérotés de 1 à k où les sommets i et j sont reliés si et seulement si les blocs $B_{i}$ et $B_{j}$ sont croisés. Si on appelle $c_{1},\dots ,c_{m}$ les composantes connexes du graphe $G(P)$ alors les blocs de ${\overline {P}}$ sont les $C_{i}:=\cup _{x\in c_{i}}B_{x}$. La fermeture non croisée ${\overline {P}}$ d'une partition $P$ est donc une partition non croisée qui est moins fine que $P$ et elle est la plus fine parmi toutes les partitions non croisées moins fine que $P$. Si $P,Q$ sont deux partitions non croisées alors la fermeture non croisée de $P\vee Q$ est la plus fine des partitions non croisées moins fine que $P$ et $Q$.

Propriétés combinatoires

• Le nombre de partitions non croisées de $\{1,\dots ,n\}$ avec $s_{1}$ blocs de taille 1, $s_{2}$ blocs de taille 2, $s_{3}$ blocs de taille 3, etc vaut ${\frac {n(n-1)\dots (n-k+2)}{s_{1}!s_{2}!s_{3}!\cdots }}$ où $k:=s_{1}+s_{2}+s_{3}+\cdots$ et $n=s_{1}+2s_{2}+3s_{3}+\cdots$.

• Le nombre de partitions non croisées à $k$ blocs de $\{1,\dots ,n\}$ correspond au nombre de Narayana $N(n,k)={\frac {(n-1)!n!}{(k-1)!k!(n-k)!(n-k+1)!}}$.

• Le nombre de partitions non croisées de $\{1,\dots ,n\}$ correspond au nombre de Catalan $C_{n}={\frac {(2n)!}{n!(n+1)!}}$.

Voir aussi

• Nombre de Catalan
• Nombre de Narayana
• Treillis (ensemble ordonné)