In the young but flourishing subject of *permutation patterns*, it is usual to regard a permutation of {1,…,*n*} as simply a sequence containing each of these numbers just once. So 31542 is a permutation of {1,…,5}. This is in agreement with the nineteenth-century usage, and indeed with the non-mathematical usage, of the term, reserving the word “substitution” for the corresponding bijective mapping (in this case, taking 1 to 3, 2 to 1, etc.)

A permutation *p* of {1,…,*m*} *occurs* in a permutation *q* of {1,…,*n*} if there are *m* symbols in *q* which occur in the same order as the symbols in *p*. Thus for example, the permutation 132 occurs in the permutation 31542 since the red symbols have the same order as 132: smallest first, largest second, intermediate third.

I have explained here my slightly different view: a permutation is a set carrying two total orders; “occurs in” means “is an induced substructure of”. But for now we will follow the usual view.

One of the concerns of the theory of permutation patterns is: given a permutation *p* of {1,…,*m*}, how many permutations of {1,…,*n*} avoid it (in the sense that it does not occur)? The problem is trivial for *m*=1 and *m*=2. For *m*=3, something remarkable happens: the number is always the same, no matter what *p* is; in fact, the number is the famous *Catalan number*.

What about *m*=4? The function giving the number of avoiding permutations is one of three possibilities for any choice of *p*; they are realised by the three permutations 1234, 1342 and 1324. For the first two the function is known; for the third, it is still a mystery, and even its rate of growth is not known very precisely.

At the BCC, Einar Steingrímsson talked about permutation patterns, and revealed that he has a bet with Doron Zeilberger about this. If someone comes up with the answer this year, Doron will pay Einar 170 euros. The amount paid out will decrease by ten euros with every year that passes before the solution is found, and if it is not found by the year 2030 then Doron wins the bet and Einar will pay him 170 euros. In his paper he summarises the situation thus:

… Doron Zeilberger is claimed to have said that “Not even God knows the number of 1324-avoiders of length 1000.” I’m not sure how good Zeilberger’s God is at math, but I believe that some humans will find this number in the not so distant future.

### Like this:

Like Loading...

*Related*

##
About Peter Cameron

I count all the things that need to be counted.