Partition d'un ensemble

Fichier:Set partitions 5; circles.svg

Les 52 partitions d'un ensemble à 5 éléments. Les points noirs représentent les éléments de l'ensemble. Une région colorée correspond à un bloc de la partition qui regroupe plusieurs points noirs. Un point noir isolé signifie que cet élément appartient à un bloc qui est un singleton.

En mathématiques, une partition d'un ensemble Modèle:Mvar est un ensemble de parties non vides de Modèle:Mvar deux à deux disjointes et dont l'union est Modèle:Mvar.

Définition

Soit un ensemble Modèle:Mvar. Un ensemble <math>\mathcal{P}</math> de parties de Modèle:Mvar est une partition de Modèle:Mvar si :

• aucune de ces parties n'est vide (<math>\forall Y \in \mathcal P, Y\ne\emptyset</math>) ;
• leur union est égale à Modèle:Mvar ;
• elles sont deux à deux disjointes (<math>\forall Y_1, Y_2 \in \mathcal P, Y_1\ne Y_2\Rightarrow Y_1\cap Y_2=\emptyset</math>) .

Les éléments d'une partition sont parfois appelés des classes ou des blocs.

Dans le cas fini, on définit aussi des partitions ordonnées comme des Modèle:Mvar-uplets <math>(X_1,X_2,\ldots,X_m)</math> tels que l'ensemble<math>\{X_1,X_2,\ldots,X_m\}</math> est une partition de Modèle:Mvar.

Exemples

L'ensemble {1, 2, 3} a les partitions suivantes :

• { {1}, {2}, {3} } ;
• { {1, 2}, {3} } ;
• { {1, 3}, {2} } ;
• { {1}, {2, 3} } ;
• et { {1, 2, 3} }.

Remarquons que :

• { ∅, {1, 3}, {2} } n'est pas une partition parce qu'elle contient l'ensemble vide ∅ ;
• { {1, 2}, {2, 3} } n'est pas une partition parce que l'élément 2 appartient à plus d'une partie ;
• { {1}, {2} } n'est pas une partition de {1, 2, 3} car l'union de tous les éléments est {1, 2} ; c'est une partition de {1, 2}.

Dans le cas où tous les éléments de la partition ont même cardinal, on retrouve le cas du lemme des bergers.

La partition vide est une partition de l'ensemble vide (c'est d'ailleurs la seule) puisque tous ses éléments (il n'y en a aucun) ont toutes les propriétés souhaitables (ici : être non vides et disjoints) et que leur union est vide (par définition).

Partitions et relations d'équivalence

Si une relation d'équivalence est donnée sur l'ensemble Modèle:Mvar, alors l'ensemble de toutes les classes d'équivalence forme une partition de Modèle:Mvar. Inversement, si une partition <math>\mathcal{P}</math> de Modèle:Mvar est donnée, alors nous pouvons définir une relation d'équivalence sur Modèle:Mvar notée ~, par Modèle:Mvar ~ Modèle:Mvar si et seulement s’il existe, parmi les éléments de <math>\mathcal{P}</math>, une partie de Modèle:Mvar qui contient à la fois Modèle:Mvar et Modèle:Mvar. Les notions de relation d'équivalence et de partition sont donc fondamentalement équivalentes.

Ordre partiel sur les partitions

L'ensemble de toutes les partitions d'un ensemble non vide Modèle:Mvar est partiellement ordonné : par définition, une partition est plus fine qu'une autre si elle fractionne les éléments de l'autre en de plus petites parties. Cet ordre partiel forme un treillis complet dont le plus petit élément (la partition la moins fine) est la partition grossière en une seule partie (Modèle:Mvar) et le plus grand (la partition la plus fine) est la partition en singletons.

Dénombrements dans le cas fini

• Le nombre de partitions d'un ensemble à Modèle:Mvar éléments en exactement Modèle:Mvar sous-ensembles est le nombre de Stirling de seconde espèce S(n, k) ; le nombre total de partitions est alors <math>B_n=\sum_{k=0}^n S (n, k)</math>, appelé nombre de Bell.
• Le nombre de partitions ordonnées d'un ensemble à Modèle:Mvar éléments (des familles de parties ayant les trois propriétés ci-dessus, au lieu d'ensembles de parties) est <math>F_n=\sum_{k=0}^n k!S (n, k)</math>, appelé nombre de Fubini.

• Si un ensemble Modèle:Mvar possède <math>n\times m</math> éléments, le nombre de partitions ordonnées de Modèle:Mvar en Modèle:Mvar parties à Modèle:Mvar éléments chacune est le coefficient multinomial <math>\underbrace {{n\times m \choose {m, m, \ldots, m}}}_n = \frac{(nm)!}{(m!)^n} </math> ; le nombre de partitions (non ordonnées) en Modèle:Mvar parties à Modèle:Mvar éléments est donc <math> \frac{(nm)!}{(m!)^nn!} </math> ; voir la Modèle:OEIS. Dans le cas où <math>m=2 </math>, une telle partition s'appelle une partition par paires.

• Le nombre de partitions différentes d'un ensemble à Modèle:Mvar éléments indiscernables est le nombre <math>p(n)</math>de partitions d'un entier.

Partitions par paires

Modèle:Refnec).

Voir aussi

• Partition non croisée