Permutation class

Key takeaways

Permutation class belongs to science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Permutation class to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Permutation class from memory before moving on to harder problems.

Reference excerpt

In the study of permutations and permutation patterns, a permutation class is a set C {\displaystyle C} of permutations for which every pattern within a permutation in C {\displaystyle C} is also in C {\displaystyle C} . In other words, a permutation class is a hereditary property of permutations, or a downset in the permutation pattern order. A permutation class may also be known as a pattern class, closed class, or simply class of permutations. Every permutation class can be defined by the minimal permutations which do not lie inside it, its basis. A principal permutation class is a class whose basis consists of only a single permutation. Thus, for instance, the stack-sortable permutations form a principal permutation class, defined by the forbidden pattern 231. However, some other permutation classes have bases with more than one pattern or even with infinitely many patterns. A permutation class that does not include all permutations is called proper. In the late 1980s, Richard Stanley and Herbert Wilf conjectured that for every proper permutation class C {\displaystyle C} , there is some constant K {\displaystyle K} such that the number | C n | {\displaystyle |C_{n}|} of length- n {\displaystyle n} permutations in the class is upper bounded by K n {\displaystyle K^{n}} . This was known as the Stanley–Wilf conjecture until it was proved by Adam Marcus and Gábor Tardos. However although the limit

lim n → ∞ | C n | 1 / n {\displaystyle \lim _{n\to \infty }|C_{n}|^{1/n}}

(a tight bound on the base of the exponential growth rate) exists for all principal permutation classes, it is open whether it exists for all other permutation classes. Two permutation classes are called Wilf equivalent if, for every n {\displaystyle n} , both have the same number of permutations of length n {\displaystyle n} . Wilf equivalence is an equivalence relation and its equivalence classes are called Wilf classes. They are the combinatorial classes of permutation classes. The counting functions and Wilf equivalences among many specific permutation classes are known.

References

Worked examples

Example 1 — a first encounter with Permutation class

Start with the simplest possible case. Write down what Permutation class claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Permutation class before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Permutation class ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Permutation class

In research: Permutation class appears in science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Permutation class in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Permutation class is common in secondary-school and first-year university syllabi. It links to neighbouring topics Permutation patterns, so understanding it makes those chapters shorter.
In everyday life: Look for Permutation class outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Permutation class in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Permutation class means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Permutation class out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Permutation class in simple terms?

In the study of permutations and permutation patterns, a permutation class is a set C {\displaystyle C} of permutations for which every pattern within a permutation in C {\displaystyle C} is also in C {\displaystyle C} . In other words, a permutation class is a hereditary property of permutations…

Why does Permutation class matter?

Because it connects several science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Permutation class?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Permutation class.