Partition non croisée

Crédit image:

Watchduck

licence CC BY 3.0 🛈

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

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

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

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

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

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

Crédit image:

Watchduck

licence CC BY 3.0 🛈

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

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 ${\displaystyle P,Q}$ sont deux partitions non croisées alors ${\displaystyle P\vee Q}$ n'est pas forcément une partition non croisée. En revanche ${\displaystyle P\wedge Q}$ est bien une partition non croisée.

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

on définit un graphe ${\displaystyle 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 ${\displaystyle B_{i}}$ et ${\displaystyle B_{j}}$ sont croisés. Si on appelle ${\displaystyle c_{1},\dots ,c_{m}}$ les composantes connexes du graphe ${\displaystyle G(P)}$ alors les blocs de ${\displaystyle {\overline {P}}}$ sont les ${\displaystyle C_{i}:=\cup _{x\in c_{i}}B_{x}}$. La fermeture non croisée^[1] ${\displaystyle {\overline {P}}}$ d'une partition ${\displaystyle P}$ est donc une partition non croisée qui est moins fine que ${\displaystyle P}$ et elle est la plus fine parmi toutes les partitions non croisées moins fine que ${\displaystyle P}$. Si ${\displaystyle P,Q}$ sont deux partitions non croisées alors la fermeture non croisée de ${\displaystyle P\vee Q}$ est la plus fine des partitions non croisées moins fine que ${\displaystyle P}$ et ${\displaystyle Q}$.

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

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

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

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

• Portail des mathématiques