Research / Analytic Combinatorics
Permutation Statistics:
Sample a permutation p uniformly at random from the symmetric group on {1,2,..,n},
two of the classic statistics that have been studied are descents
and excedances.
A descent is a position i whose image p(i) is larger than p(i+1),
and an excedance is a position whose image is larger than itself.
A classical result of MacMahon (with modern proofs using Foata's bijection)
shows that the descent and excedance statistics are "equidistributed",
meaning that the histogram based on putting permutations into bins determined by the number of descents looks identical to the one for excedances.
Interestingly, this breaks down at a more refined level.
Namely, the descent set statistic and the excedance set statistic are not equidistributed.
In fact, the notions of "excedance" and "descent" appear to be much different at the level of substructures.
For instance the extremal descent set is realized by the alternating permutations whose asymptotics are classical:
\begin{equation}
\frac{D_n}{n!} \sim \frac{4}{\pi} \left( \frac{2}{\pi} \right)^n, \quad D_n := | \{ p \in S_n : \text{Des}(p) \text{ is extremal} \} |.
\end{equation}
whereas the asymptotics of the excedance set analog (the number of permutations realizing the extremal excedance set) is:
\begin{equation}
\frac{E_n}{n!} \sim \frac{1}{(2 \log 2)\sqrt{1 - \log 2}} \left( \frac{1}{2 \log 2} \right)^n , \quad E_n := | \{ p \in S_n : \text{Exc}(p) \text{ is extremal} \} |.
\end{equation}
For details on the latter result, see my paper with R. Ferraz de Andrade and Brendan Nagle.
This answered a question posed by R. Ehrenborg and E. Clark.
We used the methods of R. Pemantle and M. Wilson
(singularity analysis in several complex variables)
which provided a more general bivariate asymptotic
(from which one may derive asymptotic limit laws).
Pattern avoidance in permutations: Computer scientist Donald Knuth is usually credited with launching the study of pattern avoidance in permutations, one of the most active recent developments in permutation theory. A pattern refers to a small permutation showing up (in terms of order isomorphism) as a substring of a larger permutation. Vincular patterns generalize this notion by allowing the requirment that certain terms in the string must be consecutive.
Joshua Cooper, Brendan Nagle, and I recently showed that the number of occurrences of a given vincular pattern within a large random permutation is exponentially concentrated about its mean (paper).
In particular, this gives an upper bound on the number of permutations avoiding a given vincular pattern (viewing avoidance as a large deviation from the mean). Related to this, we answered a question of S. Elizalde on avoidance of 12-34, where the large deviation estimate turns out to be sharp (up to the constant in the exponent).
By the well-known Marcus-Tardos proof of the Stanley-Wilf conjecture, the avoidance of classical patterns grows much more slowly. In particular, its exponential generating function is entire. On the other hand, for consecutive patterns, the avoidance is always as slow as a decaying exponential times n!, the same form given by a large deviation estimate. In particular, its exponential generating function has a finite radius of convergence. It is an interesting question asked by Elizalde to classify the asymptotic avoidance of all vincular patterns at least in terms of the dichotomy concerning whether the radius of convergence of the exponential generating function is finite.
Open Problem: Given a vincular pattern, consider the radius of convergence of its exponential generating function. For classical patterns, the radius of convergence is always infinite. For consecutive patterns, the radius of convergence is always finite. It is an open problem to determine for intermediate cases whether the radius of convergence is finite. All open cases are of the form: vincular patterns with at least one block of size two, and no blocks of size larger than 2. Known example: For 12-34 the radius of convergence is finite (see our paper). Another known example: For 1-23-4 the radius of convergence is infinite (see Elizalde's paper).
For a more detailed discussion on this problem, see the paper of S. Elizalde and our paper.