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 '19 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 '19 at 10:21
  • 3
    $\begingroup$ see also findstat.org/StatisticsDatabase/St001469 $\endgroup$ Sep 9 '19 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$ Sep 9 '19 at 13:51
  • 2
    $\begingroup$ Restored (as well as I can remember it). $\endgroup$ Sep 9 '19 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.

  • $\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 '19 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 '19 at 13:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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