(
:title "What the Hell are Permutation Patterns?"
:snip "A short introduction."
:date "2015-12-10T19:55:00Z"
:draft nil
:mathjax t
)
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][book] by Miklós Bóna
(and many other places).
[book]: http://www.amazon.com/dp/1439850518/?tag=stelos-20
<div id="toc"></div>
## 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:
<div>$$
(n)(n - 1)(n - 2)...(1)
$$</div>
Which is just the [factorial][] of \\(n\\). For our three cats we have:
<div>$$
(3)(3 - 1)(3 - 2) = 3 \cdot 2 \cdot 1 = 6
$$</div>
So now we know that:
<div>$$
\operatorname{number-of-permutations}(\mathit{items}) =
\mathit{items}!
$$</div>
[factorial]: https://en.wikipedia.org/wiki/Factorial
### 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:
<div>$$
\operatorname{number-of-permutations}(\mathit{items}, \mathit{slots}) =
\frac
{\mathit{items}!}
{(\mathit{items} - \mathit{slots})!}
$$</div>
So in this example we have:
<div>$$
\frac
{\mathit{items}!}
{(\mathit{items} - \mathit{slots})!}
=
\frac{5!}{(5 - 3)!} =
\frac{5!}{2!} =
\frac{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{2 \cdot 1} =
\frac{120}{2} =
60
$$</div>
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:
<div>$$
\frac
{\mathit{items}!}
{(\mathit{items} - \mathit{slots})!}
=
\frac
{\mathit{n}!}
{(\mathit{n} - \mathit{n})!}
=
\frac
{\mathit{n}!}
{0!}
=
\frac
{\mathit{n}!}
{1}
=
\mathit{n}!
$$</div>
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][paper] coincidentally by my professor, or even Knuth's [book][taocp]
itself.
[paper]: http://www.dmtcs.org/pdfpapers/dmAR0153.pdf
[taocp]: http://www.amazon.com/dp/0201896834/?tag=stelos-20
## 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:
* [Permutations](https://en.wikipedia.org/wiki/Permutation)
* [Permutation Patterns](https://en.wikipedia.org/wiki/Permutation_pattern)
Or go all-in and grab a copy of [Combinatorics of Permutations][book].
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.