Motif (permutations)

Pour les articles homonymes, voir Motif.

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

En combinatoire et en informatique théorique, un motif dans une permutation, aussi appelé sous-permutation, est une notion permettant de restreindre une permutation pour obtenir une permutation plus petite.

Toute permutation de longueur n peut être écrite en notation à une ligne comme une suite de chiffres représentant le résultat de l'application de la permutation aux entiers 1,...,n. Par exemple, la suite d'entiers 213 représente la transposition de longueur 3 qui échange 1 et 2. Si σ et π sont deux permutations représentées de cette manière, alors σ est dit contenir π comme un motif si une sous-suite quelconque des chiffres de σ a le même ordre relatif que tous les chiffres de π.

Par exemple, la permutation σ contient le motif 213 s'il existe trois chiffres x, y, et z qui apparaissent dans σ dans l'ordre x...y...z , mais tels que leurs valeurs suivent l'ordre y < x < z, le même ordre que pour la permutation 213. La permutation 32415 contient 213 comme motif de plusieurs façons différentes: 3··15, 32··5, 324··, et ·2·15, toutes ces suites d'entiers étant ordonnées comme 213. Chacune des sous-suites 315, 325, 324, et 215 est appelée une copie, instance, ou occurrence du motif. Le fait que σ contient π s'écrit de façon plus concise comme π ≤ σ. Cette relation fournit un ordre partiel sur l'ensemble des permutations. Si une permutation σ ne contient pas le motif π, alors on dit qu'elle évite π. La permutation 51342 évite 213; parmi toutes ses sous-suites de longueur 3, aucune n'est ordonnée comme 213.

• Portail des mathématiques
• Portail de l’informatique