| dbo:abstract
|
- 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. (fr)
- In combinatorial mathematics and theoretical computer science, a permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation as a sequence of digits representing the result of applying the permutation to the digit sequence 123...; for instance the digit sequence 213 represents the permutation on three elements that swaps elements 1 and 2. If π and σ are two permutations represented in this way (these variable names are standard for permutations and are unrelated to the number pi), then π is said to contain σ as a pattern if some subsequence of the digits of π has the same relative order as all of the digits of σ. For instance, permutation π contains the pattern 213 whenever π has three digits x, y, and z that appear within π in the order x...y...z but whose values are ordered as y < x < z, the same as the ordering of the values in the permutation 213. The permutation 32415 on five elements contains 213 as a pattern in several different ways: 3··15, ··415, 32··5, 324··, and ·2·15 all form triples of digits with the same ordering as 213. Each of the subsequences 315, 415, 325, 324, and 215 is called a copy, instance, or occurrence of the pattern. The fact that π contains σ is written more concisely as σ ≤ π. If a permutation π does not contain a pattern σ, then π is said to avoid σ. The permutation 51342 avoids 213; it has 10 subsequences of three digits, but none of these 10 subsequences has the same ordering as 213. (en)
|
