What are Permutation Patterns?

Today we examine a topic known as combinatorial pattern avoidance. There has been an explosion of interest in this field of late; see, for instance, the international permutation patterns conference, or any recent issues of your favorite discrete mathematics journal. I was first introduced to this field by Bruce Sagan at Michigan State’s SURIEM, an outstanding research program for undergraduate mathematicians.

We start from the ground up. For a positive integer n, let [n]=\{1,2,3\dots, n\}. A permutation \pi is a bijection from {}[n] to itself. So, for instance, we could have \pi: [4]\to[4] with \pi(1)=2, \pi(2)=1,\pi(3)=4,\pi(4)=3. Writing a permutation in this form is incredibly unwieldy, and hence we will use the one line notation \pi=\pi_1\pi_2\dots\pi_n, where \pi_i=\pi(i). Continuing our example from above, we would have \pi=2143. (Those familiar with these constructs may ask why we are not using the cycle notation; we will be using permutations purely as combinatorial strings and disregarding their group structure, hence the form). Given a permutation \pi=\pi_1\dots\pi_n, we say that \pi has length n.

Now given any string of positive integers w=w_1\dots w_k, we may standardize w to create st(w) by replacing the smallest letter in w with a 1, the second smallest letter in w with a 2, and in general the ith smallest letter with i. For instance, w=3581 standardizes to st(w)=2341. Two words which have the same standardization are said to be order isomorphic or in the same relative ordering, for reasons which become clear upon some thought. (Really what we are doing here is choosing a standard representative for strings based on their relative ordering; for instance, we want all three letter strings which go Small, Big, Medium to be considered the same, as they all standardize to 132.

We may now define containment and avoidance. Given a permutation \pi of length n and a permutation \sigma of length k, with k\leq n, we say that \pi contains \sigma if there exist indices i_1<i_2<\dots<i_k such that \pi_{i_1}\pi_{i_2}\dots\pi_{i_k} standardizes to \sigma. If this is not the case, then we say \pi avoids \sigma. When we ask questions such as “does \pi contain \sigma?” we will refer to \sigma as the pattern, hence the name of the field.  

Let’s have a few examples. Let \pi=43521, \tau=123, and \sigma = 231. Then I claim \pi contains \sigma but avoids \tau. I would encourage you to try and verify this for yourself before reading on. For verification, note that \pi contains the  subsequence 452, which standardizes to \sigma = 231. However, \pi does not contain any increasing subsequence of length 3, and hence \pi cannot contain \tau = 123. There are a couple remarks to be made following this example. First, note that \pi contains several subsequences which standardize to \sigma, namely 452, 451, 352, and 351. For now, we won’t worry too much about counting how many subsequences standardize to our pattern, and just focus on whether or not the pattern is contained at all. The second pedagogical remark is simply to reinforce that the subsequences taken above need not be adjacent in the original permutation, they just need to be taken in their original ordering. The subject of vincular pattern avoidance deals with placing additional restrictions on the containment, such as forcing the subsequence to be consecutive. But that is a topic for another day.

Now that we have defined the notion of permutation patterns and their containment, I would like to briefly end by listing some questions that are studied in this field, and some reasons for why this field is of interest in the first place. The list is in no particular order. I have denoted reasons of interest by “ROI” and questions by “Q”

  •  ROI: A stack is a data storage unit studied and used frequently in computer science. One operation you can try to use them for is to sort a string into increasing order; it turns out that the stack sortable permutations are exactly those which avoid the pattern 231. This is a result due to Knuth, and this result is largely credited for the explosion of interest in this area.
  • Q: Fix a permutation \sigma of length k. As an explicit function of n, how many permutations of length n avoid sigma? Remarkably, if \sigma is any permutation of length 3, then the answer is given by the Catalan numbers.
  • Q: If we cannot give an explicit formula to the question above, can we give asymptotics? One of the biggest open problems in the field currently is to find a tight growth rate for the number of permutations avoiding the pattern 1324.
  • ROI: Permutation patterns are beginning to be used in dynamical modeling. See, for instance, “The Frequence of Pattern Occurrence in Random Walks” by S. Elizalde and M. Martinez.
  • Q: What is the computational complexity of determining whether or not a given permutation contains another permutation? What if we restrict the class of permutations we examine?
  • Q: Let \Pi denote the set of all permutations of any arbitrary (finite) length, and put an ordering on \Pi by \sigma\leq \pi if and only if \pi contains \sigma as a pattern. Then this can readily be checked to be a partially ordered set (poset) known as the permutation pattern poset. This has been an object of intense study recently; a large open problem is finding the Mobius function of this poset.

I think that this is a good list for now. If you are interested in more, here is a decent place to start. Alternatively, come back to my blog in a week or so! I will plan on proving some more results from this area, starting with the Catalan result in the second bullet point above.

As always, thanks for reading!

Posted in Combinatorics, Patterns | Tagged | Leave a comment

On the geometric mean of the binomial coefficients

Today we prove a remarkable asymptotic result regarding the binomial coefficients. Namely, let G_n=\left(\prod_{k=1}^n\binom{n}{k}\right)^{\tfrac{1}{n+1}}. We will show

\displaystyle \lim_{n\to\infty}G_n^{\frac{1}{n}}=\sqrt{e}.

Before getting to the proof, I should say that this is most definitely not my creation; I believe the first publication of this proof may be credited to Polya (but I am not sure). In any case, I was shown this proof at MSU in my Putnam training seminar. It was presented by Dr. Ignacio Uriarte-Tuero. Any unintended errors introduced are mine alone.

To start, we use the definition of \binom{n}{k} to write

\begin{aligned} G_n^{n+1}&=\prod_{k=1}^n\binom{n}{k}\\&=\frac{(n!)^{n+1}}{\prod_{k=1}^n(k!)^2}\end{aligned}

Now for 1\leq j\leq n, we want to examine the power of j which appears in the fraction. So, for instance, n appears n+1 times in the numerator and twice in the denominator from (n!)^2, n-1 appears n+1 times in the numerator and four times in the denominator from (n!)^2 and ((n-1)!)^2, etc. We get the formula


We now multiply by 1 in a clever way. Noting that \sum_{k=1}^n(n+1-2k)=0 we obtain


as the denominator has total exponent 0. We can now write


We want to examine G_n^{\frac{1}{n}}. Taking logarithms, we get

\frac{1}{n}\ln(G_n)=\frac{1}{n} \sum_{k=1}^n(1-\frac{2k}{n+1})\ln(1-\frac{k}{n+1})

We now recognize this expression as a Riemann sum of the function g(x)=(1-2x)\ln(1-x) on the interval {}[0,1]. (Ok, it is not exactly a Riemann sum; we should be dividing by n+1, not n. But in the limit this will not matter.) Taking limits, it follows that

\lim_{n\to\infty}\frac{\ln(G_n)}{n}=\lim_{n\to\infty}\frac{1}{n} \sum_{k=1}^n(1-\frac{2k}{n+1})\ln(1-\frac{k}{n+1})=\int_0^1(1-2x)\ln(1-x)dx

Evaluating the integral is now easy via integration by parts; it turns out that


and thus \lim_{n\to\infty}\ln(G_n^{\frac{1}{n}})=\frac{1}{2} and \lim_{n\to\infty} G_n^{\frac{1}{n}}=\sqrt{e}.

And we’re done! As always, thanks for reading!

Posted in Asymptotics, Combinatorics, Contest Math | Leave a comment