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?

  • 4
    $\begingroup$ 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. $\endgroup$ Sep 9, 2019 at 9:39
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 9, 2019 at 10:21
  • 3
    $\begingroup$ see also findstat.org/StatisticsDatabase/St001469 $\endgroup$ Sep 9, 2019 at 12:46
  • 2
    $\begingroup$ I was sorry to see the first question title go, though I recognise the new title is more informative... $\endgroup$
    – David Roberts
    Sep 9, 2019 at 13:51
  • 2
    $\begingroup$ Restored (as well as I can remember it). $\endgroup$ Sep 9, 2019 at 14:32

2 Answers 2


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.

  • $\begingroup$ 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$. $\endgroup$ 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.