A record in a permutation is a maximum or a minimum, from the left or from the right. The entries of a permutation can be partitioned into two types: the ones that are records are called external points, the others are called internal points. Permutations without internal points have been studied under
the name of square permutations. Here, we explore permutations with a fixed number of internals points, called almost square permutations. Unlike with
square permutations, a precise enumeration for the total number of almost square permutations of size \(n+k\) with exactly \(k\) internal points is not
known.
However, using a probabilistic approach, we are able to determine the asymptotic enumeration. We denote with \(Asq(n,k)\) the set of almost square permutations of size \(n+k\) with exactly \(k\) internal points
Theorem. For \(k=o(\sqrt n),\) as \(n\to \infty,\)
\(|Asq(n,k)| \sim \frac{k!2^{k+1}n^{2k+1}4^{n-3}}{(2k+1)!}\sim \frac{k!2^{k}n^{2k}}{(2k+1)!}|Asq(n,0)|.\)When \(k\) grows at least as fast as \(\sqrt n\) the above result fails. Nevertheless, when \(k=o(n)\), we can still obtain the following weaker asymptotic expansion that determines the behavior of the exponential growth.
Theorem. For \(k=o(n)\), as \(n\to \infty,\)
\(\log\left(|Asq(n,k)|\right)=\log\left(\frac{k!}{(2k+1)!}2^{k+1}n^{2k+1}4^{n-3}\right)+o(k).\)These two theorems allows us to describe the permuton limit of almost square permutations with \(k\) internal points, both when \(k\) is fixed and when \(k\) tends to infinity along a negligible sequence with respect to the size of the permutation. Specifically, we have the following results.
Given \(z\in(0,1)\) we denote with \(\mu^{z}\) the permuton corresponding to a rectangle in \([0,1]^2\) with corners at \((z,0), (0,z),(1-z,1)\) and \((1,1-z).\)
Theorem. Fix \(k>0\). Let \(\textbf{z}^{(k)}\) denote the random variable in \((0,1)\) with density
\(f_{\mathbf{z}^{(k)}}(t) = (2k+1){2k \choose k} (t(1-t))^k,\)i.e., \(\textbf{z}^{(k)}\) is beta distributed with parameters \((k+1,k+1)\). If \(\sigma_n\) is uniform in \(Asq(n,k)\), then as \(n\to \infty,\)
\(\mu_{\sigma_n} \stackrel{d}{\longrightarrow} \mu^{\mathbf{z}^{(k)}},\)where \(\mu_{\sigma_n} \) denotes the permuton corresponding to \(\sigma_n.\)
The distribution of \(\textbf{z}^{(k)}\), when \(k\) increases, gives more weight around the value \(1/2\) as can be seen from the following picture (the chart displays the density of the distribution of \(\textbf{z}^{(k)}\) for different values of \(k\)).
We therefore expect that, in the regime when \(k\to\infty\) together with \(n\) and \(k=o(n)\), a uniform random permutation with \(k\) internal points tends to \(\mu^{1/2}\). The following theorem shows exactly this concentration result.
Theorem. Let \(k\) and \(n\) both tend to infinity with \(k=o(n)\). If \(\sigma_n\) is uniform in \(Asq(n,k)\) then
\(\mu_{\sigma_n} \stackrel{d}{\longrightarrow} \mu^{1/2}.\)
Finally, we show that our techniques are quite general by studying the set of 321-avoiding permutations of size \(n+k\) with exactly \(k\) internal points. In this case we obtain an interesting asymptotic enumeration in terms of the Brownian excursion area. As a consequence, we show that the points of a uniform permutation in this set concentrate on the diagonal and the fluctuations of these points converge in distribution to a biased Brownian excursion.