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.


The permutations of n=2 are 12 and 12.

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.

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.


In the permutation 654123, let us pick out subsequence 654. Then this is a 321 pattern. Note that the numbers do not have to be sequential: the subsequence 642 also is a 321 pattern. The subsequence 613 is a 312 pattern.

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

Now let’s consider the pattern 123.

























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 nth 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.


For n= 3, 4, 5,…, we get that

Cn= 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, …

Calculating these from a formula is much easier than working them all out by hand!