Numb3rs 503: Blowback

In this episode, the LAPD is investigating the murder of 8 people in a diner, with the help of Charlie. One of the victims was an off-duty cop, and another was undercover. The team begins to look into the daily routines of the cops on duty: where they were, what calls they answered. They bring up the idea of a 3-D stereogram, a picture within a picture. Applying this model, they see that while it appeared that all the 911 calls answered by the cop were random, in fact there was a call from the same house every week at the same time, and even though it wasn’t in the cop’s district, he was always the closest at the time of the call and thus always answered it.

What the FBI agents were looking for was a pattern within a pattern, looking at a seemingly random distribution of calls that were answered by the cop over the course of months, and finding that a subset of them in fact were quite predictable. Mathematicians often look for patterns hidden in things that appear random. We want to look at one example of this.

Pick a whole number, call it n. Then we can consider a list of the numbers 1, 2, … , n. If we write the numbers in a different order, we call this a permutation. We can think of this as picking a number from the list and writing it down, then picking a second from those that are left, then a third, and so on. For easier reading, we write 12 to mean “the permutation 1,2,” not twelve. This is fine since all the numbers we will use are less than ten.

• Make a list of all the permutations of 3. How many are there?

Given a permutation, we can pick out some of the terms, called a subsequence, and describe their behavior. Let’s look at a random permutation and see if we can find a specific pattern embedded into it. Say we had the permutation 7 2 5 4 3 1 6 8.

• Let’s pick out just the even terms: 2 4 6 8. What do you notice?

• Let’s now pick out just the odd terms. What subsequence do you get? Do you see a pattern?

Just by looking at the permutation, you might not have noticed that there was a structure hidden inside it. Now, we want to look at subsequences and describe their behavior. We usually do not get subsequences that are just increasing or decreasing, so we say a subsequence has a pattern where we label the lowest value in the pattern by 1, the second lowest by 2, and so on.

• Can you find more 312 patterns in 654123?

• Can you find a 1234 pattern in 654123?

We say that 654123 contains the pattern 312, but avoids the pattern 1234.

• Make a list of all the permutations of 3 that contain the pattern 12.

• What permutations are left? These are the permutations that avoid 12.

Now let’s consider the pattern 123.

• Look at your list of all the permutations of 3. How many of these are 123-avoiding? How many are 321-avoiding?

• Here is a list of all the permutations of 4. How many of these are 123-avoiding?

• How many are 321-avoiding?

• Can you guess how many 321-avoiding permutations of 5 there are?

It turns out that there are 42 of them! Mathematicians have studied much bigger permutations, and what is amazing is that there is a formula that tells you how many 321-avoiding permutations of n there are, for any n. In fact, this is the same number of 123- avoiding, and the same number as any π-avoiding permutations of n, for π equal to any permutation of 3. This is called the n^th Catalan number, and for any n it is given by the formula

where n!=(n)(n-1)(n-2)…(2)(1) is called n factorial.

• Check that for n=3 and n=4, this formula matches the numbers you got before.