How rare are unholey permutations?

Question

For $S\subset [n]:=\{1,2,\dotsc,n\}$, define $\delta(S)$ to be the number of $m\in S$ such that $m+1\notin S$.

Given a permutation $\pi$ of $[n]$, we define the holeyness $D(\pi)$ of $\pi$ as being $$\max_{S\subset [n]} (\delta(\pi(S))-\delta(S)).$$ It is clear that $D(\pi)\geq 0$.

What is (roughly or exactly) the number of permutations $\pi$ of $[n]$ such that $D(\pi)\leq k$? What if you restrict $\pi$ to be an $n$-cycle?

Answer 1

This is just a long comment. I computed $P_{n}(q)=\sum_{\pi \in S_n} q^{D(\pi)}$, and got the following polynomials: \begin{array}{l} 1 \\ 2 \\ 4 q+2 \\ 22 q+2 \\ 36 q^2+82 q+2 \\ 478 q^2+240 q+2 \\ 576 q^3+3942 q^2+520 q+2 \\ 14840 q^3+24518 q^2+960 q+2 \\ \end{array} It seems that for odd $n$, $P_{n}(q)$ has degree $d=(n-1)/2$, and the leading coefficient is $((d+1)!)^2$.

Similarly, $\sum_{\pi \in S_n, type(pi)=(n)} q^{D(\pi)}$ gave me \begin{array}{l} 1 \\ 1 \\ 2 q \\ 6 q \\ 8 q^2+16 q \\ 85 q^2+35 q \\ 96 q^3+564 q^2+60 q \\ 1978 q^3+2982 q^2+80 q \\ \end{array}

Also, it seems like both families of polynomials (checked for up to $n=8$), are real-rooted.

One can also consider a cyclic version of holeyness, where we add $1$ to $\delta(S)$ if not both $1$ and $n$ are in $S$. Here, $n$ is the number of elements in the permutation. What happens is that $D(\pi) = D( w\pi w^{-1})$ if $w = (123\dotsc,n)$, so every polynomial is divisible by $n$. \begin{array}{l} 1 \\ 2 \\ 6 \\ 16 q+8 \\ 110 q+10 \\ 216 q^2+492 q+12 \\ 3346 q^2+1680 q+14 \\ 4608 q^3+31536 q^2+4160 q+16 \\ \end{array} These also seem real-rooted.

Answer 2

Unless I am very mistaken, there is an easy way to establish a bound of the "much better" kind mentioned in the comments above. (I don't doubt one can and should give a more precise answer.)

Write $\phi$ for $\pi \sigma \pi^{-1}$ (meaning $\pi^{-1}\circ \sigma \circ \pi$), where $\sigma = (1 2 \dotsc n)$. Then $\delta(\pi(S))$ is the number of $m\in S$ such that $\phi(m) \notin S$.

(Well, there could be a difference of $1$, which does not matter. Let us redefine $\delta(S)$ to be the number of $m\in S$ such that $\sigma(m)\notin S$. Perhaps we should consult OEIS again, after this redefinition?)

For the sake of simplicity, we shall restrict our attention to maps $\pi$ without fixed points; that implies $\phi$ has no fixed points either. (This case covers the case of $\pi$ ranging over $n$-cycles, in particular.) Let $v=v_\phi$ be the number of $m\in [n]$ such that $\phi(m) \notin \{\sigma(m), \sigma^{-1}(m)\}$. A bit of doodling shows that the number $w=w_\phi$ of consecutive pairs $A=\{m,\sigma(m)\}$ such that $\phi(A)\cap A=\emptyset$ (called them "valid" pairs) is $\geq v_\phi/2$.

Now we build a set $S$ as follows. At each step, we add to $S$ a valid pair $\{m,\sigma(m)\}$ that has not yet been marked as forbidden. We also mark eight pairs as forbidden: $$\{\phi(m),\sigma^{\pm 1}(\phi(m))\}, \{\phi(\sigma(m)),\sigma^{\pm 1}(\phi(\sigma(m)))\}, \{\phi^{-1}(m),\sigma^{\pm 1}(\phi^{-1}(m))\}, \{\phi^{-1}(\sigma(m)),\sigma^{\pm 1}(\phi^{-1}(\sigma(m)))\}.$$ In this way, we get to build a set $S$ of size at least $2 \cdot w_\phi/9 \geq v_\phi/9$ with $\delta(S)\leq |S|/2$ and $\phi(S)\cap S = \emptyset$, so that $\delta(\pi(S)) = |S|$. Hence $$D(\pi) \geq v_\phi/18.$$

Thus, the number of distinct $\phi$ without fixed points coming from permutations $\pi$ with $D(\pi)\leq k$ is at most $2^n n^{18 k}$ (in fact, at most $2^{n-18k} n^{18 k}$). Now, at most $n$ permutations $\pi$ (in fact, exactly $n$ permutations $\pi$) give rise to the same $\phi = \pi \sigma \pi^{-1}$. Therefore, the total number of permutations without fixed points $\pi$ of $[n]$ such that $D(\pi)\leq k$ is at most $$2^n n^{18 k + 1}.$$

I think (though I haven't checked yet) that the analysis for arbitrary permutations $\pi$ should require only a little more work.