Lesson plan
Permutation pattern
In combinatorial mathematics and theoretical computer science, a (classical) permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation as a sequence of entries representing the result of applying the permutation to the sequence 123...; for instance the 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 entries of π has the same relative order as all of the entries of σ. For instance, permutation π contains the pattern 213 whenever π has three entries 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 entries with the same ordering as 213. Note that the entries do not need to be consecutive. 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 σ ≤ π.…
Article summary
In combinatorial mathematics and theoretical computer science, a (classical) permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation as a sequence of entries representing the result of applying the permutation to the sequence 123...; for instance the 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 entries of π has the same relative order as all of the entries of σ. For instance, permutation π contains the pattern 213 whenever π has three entries 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 entries with the same ordering as 213. Note that the entries do not need to be consecutive. 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 σ ≤ π.…
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.