Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Partition non croisée
Résumé
vignette|Au dessus, les 42 partitions non croisées d'un ensemble à 5 éléments. En dessous, les 10 partitions restantes.
En mathématiques, une partition non croisée est une partition d'un ensemble fini en blocs qui ne se croisent pas.
Soit un entier naturel et une partition de l'ensemble . Cette partition est dite non croisée si pour tout , les blocs et ne sont pas croisés, c'est-à-dire que pour tout il n'est pas vrai que .
Par exemple est une partition non croisée pour mais 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 points numérotés de 1 à sur une ligne. Si avec alors on représente en traçant un pont reliant les points numérotés et puis et , ..., puis et . Si est une partition de 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 points numérotés de 1 à sur un cercle. Si alors on représente en traçant l'enveloppe convexe des points dans le cercle. Si est une partition de 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.
vignette|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 dans l'ensemble des partitions (quelconques) de de la manière suivante : pour deux partitions et , on a si et seulement si pour tout bloc il existe un bloc tel que . On dit alors que est plus fine que . L'ensemble des partitions muni de cette relation d'ordre est un treillis dont les opérations sont notées ici et .
L'ensemble des partitions non croisées muni de ce même ordre est également un treillis. Cependant ce treillis n'est pas un sous-treillis des partitions quelconques.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.