What the Hell are Permutation Patterns?
Posted on December 10th, 2015.
I'm currently in the Mathematical Programming class at Reykjavík University and we're working with permutations and patterns. They're really simple to understand once they're explained to you, but after searching around online I haven't found a nice explanation for humans, so here you go.
None of this is new research, I just want to summarize things so other people can understand it without having to shovel through the internet trying to piece together a bunch of terse definitions. All of this is covered in more detail on Wikipedia, as well as in Combinatorics of Permutations by Miklós Bóna (and many other places).
Permutations (Non-Mathy)
If you've used permutations in a programming language you can probably skip this section.
If you're interested in programming and/or math you've probably heard the term "permutations" before. It's typically explained to be something like "different ways to order a collection of objects".
The key word here is "order" — permutations are all about ordering.
Basics
Let's look at an example. If you have a list of three cats:
- Scruffy
- Boots
- Patches
How many different ways can you list them out? Order matters, and you're also not allowed to repeat a cat (no cloning here).
1 2 3 4 5 6
Scruffy Scruffy Patches Patches Boots Boots
Boots Patches Scruffy Boots Scruffy Patches
Patches Boots Boots Scruffy Patches Scruffy
So there are six permutations. Simple enough. Let's think about the edge cases. How many ways can you permute one cat? Just one:
1
Scruffy
Something a bit tougher: how many ways can you permute zero cats? This seems a bit weird, but if you phrase it as "how many ways can you order a list of zero objects" you can convince yourself the answer is one as well (the single permutation is "the empty list").
We don't want to have to count out the number of permutations by hand every time, so it would be nice to have a formula. If we have a list of n things, how many different permutations can we come up with?
We can start by filling the first slot with any item we want, so we have \(n\) options. Then for each of those choices we pick something to go in the next slot from the \(n - 1\) things that are left. We can keep going all the way down until we're at the last slot, by which point we've only got one thing left, so we get:
Which is just the factorial of \(n\). For our three cats we have:
So now we know that:
Restricting Slots
Things start to get more interesting when we start to restrict the number of slots. For example, we can ask "how many different lists of three items can we take from a group of five items?"
I'm going to stop using cat names now because it's getting painful to type, so let's just use letters. Our five items will be:
a, b, c, d, e
How many different three-length lists can we produce?
(a, b, c) (a, b, d) (a, b, e) (a, c, b) (a, c, d) (a, c, e)
(a, d, b) (a, d, c) (a, d, e) (a, e, b) (a, e, c) (a, e, d)
(b, a, c) (b, a, d) (b, a, e) (b, c, a) (b, c, d) (b, c, e)
(b, d, a) (b, d, c) (b, d, e) (b, e, a) (b, e, c) (b, e, d)
(c, a, b) (c, a, d) (c, a, e) (c, b, a) (c, b, d) (c, b, e)
(c, d, a) (c, d, b) (c, d, e) (c, e, a) (c, e, b) (c, e, d)
(d, a, b) (d, a, c) (d, a, e) (d, b, a) (d, b, c) (d, b, e)
(d, c, a) (d, c, b) (d, c, e) (d, e, a) (d, e, b) (d, e, c)
(e, a, b) (e, a, c) (e, a, d) (e, b, a) (e, b, c) (e, b, d)
(e, c, a) (e, c, b) (e, c, d) (e, d, a) (e, d, b) (e, d, c)
You can see how working with numerical formulas would be a lot nicer than listing all those out by hand and counting them. The formula to tell us the number is:
So in this example we have:
Which is correct (feel free to count them by hand if you're skeptical).
This formula continues to work when the number slots is equal to the number of elements (like in our cat example). If \(n = slots = items\) then:
Remember that \(0!\) is 1, not 0 as you might first expect. Feel free to plug in the edge cases we talked about before (zero- and one-length permutations) and make sure they work.
Permutations (Mathy)
That was a pretty standard introduction to permutations, and it's about as far as most basic programming/math books go at first (they'll also talk about "combinations", which are something else that we don't care about right now). But if we want to start looking at permutations more closely we need to add a few additional rules.
So far we've been talking about permutations of arbitrary objects, like cats, letters, or playing cards. From here on out we're going to restrict ourselves a bit more: we'll only consider lists of positive integers. This is important because integers can be compared. We can't say that Scruffy is "less than" or "greater than" Boots, but we can say that 15 is less than 16.
Notice that we're not including the number zero. When we say "show me all standard permutations of length 3" we mean:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 1
3 2 1
Sorry programmers, permutation people like to count from one.
You'll notice that I wrote out the permutations above each on their own line,
with the numbers just listed out. This is called "one-line notation".
Sometimes people drop the spaces in between the numbers (e.g. 1 2 3 becomes
123) if all the numbers are single digits and they feel like being annoying.
There's also a "two-line notation" that we won't use here, check out the Wikipedia page at the end of the post for more.
Standard/Classical Permutations
Another term we'll use is "standard permutations" or "classical patterns" (don't
worry about the word "patterns" too much yet). This just means they contain all
the numbers 1 to \(n\) with no missing numbers. So 3 2 4 1 is a standard
permutation (of length 4), but 1 902 23232 5 is not.
Subwords/Subsequences
One more bit of terminology before we get to the meat of the post. A "subword"
of a permutation is all the different lists we can get by dropping none, some,
or all of the items, without changing the order. For example, the sublists of
9 3 1 4 are:
dropping no items
(9 3 1 4)
dropping one item
( 3 1 4)
(9 1 4)
(9 3 4)
(9 3 1 )
dropping two items
( 1 4)
(9 4)
(9 3 )
( 3 4)
(9 1 )
( 3 1 )
dropping three items
(9 )
( 3 )
( 1 )
( 4)
dropping four items
( )
You will also hear these called "subsequences", but this is way too confusing
because subsequence in a programming language almost always means
a consecutive portion of a list, so I'm going to stick with "subwords".
Permutation Patterns
Hold onto your hats, things are about to get intense.
We say that one permutation X contains another permutation Y if one of the subwords of X has the same length and relative order as Y. I know that's confusing and not at all clear, so let's take an example.
Let X be the permutation 1 4 3 2. Let Y be 1 2. Does X contain Y?
If we look at Y's elements, we see that it starts with the lowest element and
then goes to the highest element. Is there some subword of X, of length 2, that
does the same thing? Sure: 1 4 is a subword of X, has length 2, and starts at
the lowest element then goes to the highest.
Note that our subword has a 4 in it, but Y only has 1 and 2. This is the
most confusing part about permutation patterns: we don't care about the actual
numbers themselves — we only care about the relationships between the numbers.
Another example. Let X be 1 4 3 2. Let Y be 2 1. Does X contain Y? Try
this one on your own before reading on.
Y is still two elements long, but now it starts at the highest element and goes
the lowest. The subword we used in the last example (1 4) doesn't work here,
because it starts low and goes high (the opposite of what we want). But 4 3
is another subword of X, and that does match, so X does contain Y. Note that
4 2 would also fit here (remember: subwords don't have to be consecutive!).
Let's try something more interesting. Let X still be 1 4 3 2, but let's make
Y 1 2 3. Does X contain Y?
This one is a little trickier. The order of Y is that it starts at the lowest element, then it goes to the middle one, then finally it goes to the highest element. Let's look at the subwords of X that are length 3:
1 4 3
1 4 2
1 3 2
4 3 2
Do any of those have the same relative ordering as Y? No! None of them start at the lowest, go to the middle, then go to the highest. So this time X does not contain Y, so we say that X avoids Y.
So What?
So now that we know what "X contains Y" and "X avoids Y" mean, what can we use this stuff for? I'm not an expert, but I can give you a few examples to whet your apetite.
Consider a permutation X that avoids 2 1. What might X look like?
Well the empty permutation and any permutation with only one element certainly
avoid 2 1 (they don't have any subwords of the correct length at all). What
about longer ones?
If X avoids 2 1, then for any two elements in it, the leftmost element must be
smaller than the rightmost one (otherwise it would contain 2 1). This means
that all the elements must be getting bigger as you go to the right, or to put
it another way: the permutation must be in sorted order!
Similarly, if X avoids 1 2 then it must be in reverse sorted order. Poke at
this for a minute and convince yourself it must be true. Make sure to consider
edge cases like the empty permutation and single-element permutations.
Another example comes from Knuth: if a permutation contains 2 3 1 it cannot be
sorted by a stack in a single pass. Remember: the numbers in the matching
subword don't have to be consecutive, and they don't have to match the exact
numerals, only the relative order matters. 66 1 99 2 33 contains 2 3 1
because the subword 66 99 33 has the same relative order (and so 66 1 99
2 33 cannot be sorted by a stack in a single pass). This is probably not
intuitively obvious, so for further explanation check out Wikipedia, or this
paper coincidentally by my professor, or even Knuth's book
itself.
Further Information
This was a really quick introduction. I glossed over a bunch of things (like defining a permutation as a mapping of elements of a set to themselves, the identity permutation, etc). If you want to dive in more, you can check out Wikipedia:
Or go all-in and grab a copy of Combinatorics of Permutations.
I'm also planning on doing another post like this about mesh patterns, which are a slightly more general/powerful version of these basic patterns.