Partition non croisée

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

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