Partition non croisée

Cet article ne cite pas suffisamment ses sources (septembre 2021).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

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

Définition

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.

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 ${\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.

Représentation dans le cercle

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 enveloppe convexes dessinées sont disjointes.

Propriétés

Structure de treillis

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}$.

Propriétés combinatoires

• 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)!}}}$.

Complémentaire de Kreweras

Notes et références

Voir aussi

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

• Portail des mathématiques