Partition d'un ensemble - Partition of a set

Un ensemble de timbres divisé en lots : aucun timbre n'est dans deux lots, aucun lot n'est vide et chaque timbre est dans un lot.
Les 52 partitions d'un ensemble à 5 éléments. Une région colorée indique un sous-ensemble de X, formant un membre de la partition englobante. Les points non colorés indiquent des sous-ensembles à un seul élément. La première partition illustrée contient cinq sous-ensembles à un seul élément ; la dernière partition contient un sous-ensemble comportant cinq éléments.
Les symboles japonais traditionnels pour les 54 chapitres du Dit du Genji sont basés sur les 52 façons de partitionner cinq éléments (les deux symboles rouges représentent la même partition, et le symbole vert est ajouté pour atteindre 54).

En mathématiques , une partition d'un ensemble est un regroupement de ses éléments en sous- ensembles non vides , de telle sorte que chaque élément est inclus dans exactement un sous-ensemble.

Chaque relation d'équivalence sur un ensemble définit une partition de cet ensemble, et chaque partition définit une relation d'équivalence. Un ensemble équipé d'une relation d'équivalence ou d'une partition est parfois appelé un setoïde , typiquement en théorie des types et en théorie de la preuve .

Définition et notation

Une partition d'un ensemble X est un ensemble de sous-ensembles non vides de X tel que chaque élément x de X se trouve exactement dans l'un de ces sous-ensembles (c'est-à-dire que X est une union disjointe des sous-ensembles).

De manière équivalente, une famille d'ensembles P est une partition de X si et seulement si toutes les conditions suivantes sont vérifiées :

  • La famille P ne contient pas l' ensemble vide (c'est-à-dire ).
  • L' union des ensembles dans P est égale à X (c'est-à-dire ). Les ensembles de P sont dits gaz d' échappement ou de couverture X . Voir aussi les événements collectivement exhaustifs et la couverture (topologie) .
  • L' intersection de deux ensembles distincts dans P est vide (c'est-à-dire ). Les éléments de P sont dits deux à deux disjoints .

Les ensembles de P sont appelés blocs , parties , ou cellules , de la partition. Si alors nous représentons la cellule contenant un par . C'est-à-dire, est la notation pour la cellule de P qui contient un .

Chaque partition, P , peut être identifiée à une relation d'équivalence sur X , à savoir la relation telle que pour tout on a si et seulement si (équivalent, si et seulement si ). La notation évoque l'idée que la relation d'équivalence peut être construite à partir de la partition. Inversement, toute relation d'équivalence peut être identifiée à une partition. C'est pourquoi il est parfois dit de manière informelle qu'« une relation d'équivalence équivaut à une partition ». Si P est la partition identifiée avec une relation d'équivalence donnée , alors certains auteurs écrivent . Cette notation suggère l'idée que la partition est l'ensemble X divisé en cellules. La notation évoque aussi l'idée qu'à partir de la relation d'équivalence on peut construire la partition.

Le rang de P est | X | − | P | , si X est fini .

Exemples

  • L'ensemble vide a exactement une partition, à savoir . (Remarque : il s'agit de la partition, pas d'un membre de la partition.)
  • Pour tout ensemble non vide X , P = { X } est une partition de X , appelée partition triviale .
  • Pour tout non vide sous - ensemble A d'un ensemble U , l'ensemble A avec son complément forment une partition de U , à savoir, { A , UA }.
  • L'ensemble {1, 2, 3} a ces cinq partitions (une partition par élément) :
    • { {1}, {2}, {3} }, parfois écrit 1 | 2 | 3.
    • { {1, 2}, {3} } ou 1 2 | 3.
    • { {1, 3}, {2} } ou 1 3 | 2.
    • { {1}, {2, 3} } ou 1 | 2 3.
    • { {1, 2, 3} } ou 123 (dans des contextes où il n'y aura pas de confusion avec le nombre).
  • Les éléments suivants ne sont pas des partitions de {1, 2, 3} :
    • { {}, {1, 3}, {2} } n'est pas une partition (d'aucun ensemble) car l'un de ses éléments est l' ensemble vide .
    • { {1, 2}, {2, 3} } n'est pas une partition (d'aucun ensemble) car l'élément 2 est contenu dans plus d'un bloc.
    • { {1}, {2} } n'est pas une partition de {1, 2, 3} car aucun de ses blocs n'en contient 3 ; cependant, c'est une partition de {1, 2}.

Partitions et relations d'équivalence

Pour toute relation d'équivalence sur un ensemble X , l'ensemble de ses classes d'équivalence est une partition de X . Inversement, à partir de n'importe quelle partition P de X , on peut définir une relation d'équivalence sur X en fixant x ~ y précisément lorsque x et y sont dans la même partie de P . Ainsi les notions de relation d'équivalence et de partition sont essentiellement équivalentes.

L' axiome du choix garantit pour toute partition d'un ensemble X l'existence d'un sous-ensemble de X contenant exactement un élément de chaque partie de la partition. Cela implique qu'étant donné une relation d'équivalence sur un ensemble, on peut sélectionner un élément représentatif canonique de chaque classe d'équivalence.

Raffinement des cloisons

Partitions d'un ensemble de 4 ordonnées par raffinement

Une partition α d'un ensemble X est un raffinement d'une partition ρ de X — et on dit que α est plus fin que ρ et que ρ est plus grossière que α — si tout élément de α est un sous-ensemble d'un élément de ρ . De manière informelle, cela signifie que α est une fragmentation supplémentaire de ρ . Dans ce cas, il est écrit que αρ .

Cette relation plus fine que sur l'ensemble des partitions de X est un ordre partiel (donc la notation "≤" est appropriée). Chaque ensemble d'éléments a une borne supérieure et une borne inférieure , de sorte qu'il forme un treillis , et plus précisément (pour les partitions d'un ensemble fini) il s'agit d'un treillis géométrique . Le treillis de partition d'un ensemble de 4 éléments a 15 éléments et est représenté dans le diagramme de Hasse sur la gauche.

Basé sur le cryptomorphisme entre réseaux géométriques et matroïdes , ce réseau de partitions d'un ensemble fini correspond à un matroïde dans lequel l'ensemble de base du matroïde est constitué des atomes du réseau, à savoir, les partitions avec des ensembles singletons et un à deux éléments ensemble. Ces partitions atomiques correspondent un pour un aux arêtes d'un graphe complet . La fermeture matroïde d'un ensemble de partitions atomiques est le plus fin grossissement commun de tous ; en termes de théorie des graphes, c'est la partition des sommets du graphe complet en les composantes connexes du sous-graphe formé par l'ensemble donné d'arêtes. Ainsi, le réseau de partitions correspond au réseau de méplats du matroïde graphique du graphe complet.

Un autre exemple illustre le raffinement des partitions du point de vue des relations d'équivalence. Si D est l'ensemble de cartes d'un jeu standard de 52 cartes, la relation de même couleur que sur D – qui peut être notée ~ C – a deux classes d'équivalence : les ensembles {cartes rouges} et {cartes noires}. La partition en 2 parties correspondant à ~ C a un raffinement qui donne la relation de même couleur que ~ S , qui a les quatre classes d'équivalence {pique}, {diamants}, {cœurs} et {trèfles}.

Cloisons non-croisées

Une partition de l'ensemble N = {1, 2, ..., n } avec la relation d'équivalence correspondante ~ est non - croisée si elle a la propriété suivante : Si quatre éléments a , b , c et d de N ayant a < b < c < d satisfait a ~ c et b ~ d , alors a ~ b ~ c ~ d . Le nom vient de la définition équivalente suivante : Imaginez les éléments 1, 2, ..., n de N dessinés comme les n sommets d'un n -gon régulier (dans le sens inverse des aiguilles d'une montre). Une partition peut alors être visualisée en traçant chaque bloc sous la forme d'un polygone (dont les sommets sont les éléments du bloc). La partition est alors non traversante si et seulement si ces polygones ne se coupent pas.

Le réseau des partitions non croisées d'un ensemble fini a récemment pris de l'importance en raison de son rôle dans la théorie des probabilités libres . Ceux-ci forment un sous-ensemble du réseau de toutes les partitions, mais pas un sous-réseau, car les opérations de jointure des deux réseaux ne concordent pas.

Compter les partitions

Le nombre total de partitions d'un ensemble de n éléments est le nombre de cloche B n . Les premiers numéros de Bell sont B 0 = 1, B 1 = 1, B 2 = 2, B 3 = 5, B 4 = 15, B 5 = 52 et B 6 = 203 (séquence A000110 dans l' OEIS ). Les numéros de cloche satisfont à la récursivité

et ont la fonction génératrice exponentielle

Construction du triangle de la cloche

Les nombres Bell peuvent également être calculés à l'aide du triangle Bell dans lequel la première valeur de chaque ligne est copiée à partir de la fin de la ligne précédente, et les valeurs suivantes sont calculées en ajoutant deux nombres, le nombre à gauche et le nombre au-dessus à gauche du poste. Les numéros de Bell sont répétés le long des deux côtés de ce triangle. Les nombres dans le triangle comptent les partitions dans lesquelles un élément donné est le plus grand singleton .

Le nombre de partitions d'un n- élément défini en exactement k parties non vides est le nombre de Stirling du second type S ( n , k ).

Le nombre de partitions non croisées d'un ensemble de n éléments est le nombre de Catalan C n , donné par

Voir également

Remarques

Les références

  • Brualdi, Richard A. (2004). Combinatoire d'introduction (4e éd.). Pearson Prentice Hall. ISBN 0-13-00119-1.
  • Schechter, Éric (1997). Manuel d'analyse et ses fondements . Presse académique. ISBN 0-12-622760-8.