Motif (permutations)

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.

Définitions

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.