# How rare are unholey permutations?

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?

• The permutations with $D(\pi) = 0$ are the identity permutation and the reverse permutation. The number of permutations with $D(\pi) = 1$ starts $0,0,4,22,82,240,520,960,1590, 2442$ (from $n=1$ to $n=10$) and is not in OEIS. Sep 9, 2019 at 9:39
• If k is fixed, then one can construct a permutation pattern which must be avoided in order to have D(pi)<=k. Therefore the number of such permutations is at most exponential in n. Sep 9, 2019 at 10:21
• Sep 9, 2019 at 12:46
• I was sorry to see the first question title go, though I recognise the new title is more informative... Sep 9, 2019 at 13:51
• Restored (as well as I can remember it). Sep 9, 2019 at 14:32

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.

• I confirm the first table. The next two rows are $2 + 1590q + 112874q^2 + 234014q^3 + 14400q^4$ and $2 + 2442q + 388126q^2 + 2622844q^3 + 615386q^4$. Sep 9, 2019 at 11:49

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.

• ... and, of course if we donot redefine $\delta$, the above argument still yields an upper bound of $2^n n^{18k+37}$. Sep 9, 2019 at 13:20