Generalized Patterns in Permutation Theory: Joshua Cooper, Brendan Nagle, and I recently showed that the number of occurrences of a given generalized pattern within a large random permutation is exponentially concentrated about its mean (preprint).

In particular, this gives an upper bound on the number of permutations avoiding a given generalized pattern (viewing avoidance as a large deviation from the mean). By the well-known Marcus Tardos proof of the Stanley-Wilf conjecture this is not the sharp estimate on avoidance in the case of classical pattern. However, it is the sharp estimate for consecutive patterns, and it is sharp in some of the intermediate cases.

It is an interesting question, directly related to a question already asked by Elizalde, for which generalized patterns does the probabilistic estimate give the sharp estimate on total avoidance.

We were able to answer a question of S. Elizalde on avoidance of 12-34, where the probabilistic estimate turns out to be sharp. I believe a more complete understanding of other intermediate examples between consecutive patterns and classical patterns requires generating function methods (as used in Elizalde's study). I'd like to learn Flajolet's book "Analytic Combinatorics" in order to attack some of these remaining questions using exponential generating functions.

Open Problem: For classical patterns, the radius of convergence of the generating function for avoidance is always infinity. For consecutive patterns, the radius of convergence is always finite. Some intermediate cases have been classified, but it is an open problem to give a complete classification. (One need only consider generalized patterns with at least one block of size two, and not blocks larger than size 2). For 12-34 the radius of convergence is finite. For 1-23-4 the radius of convergence is infinity.

For a more detailed discussion on this problem, see the paper of S. Elizalde and also the above preprint.

Back to my home page.