d-regular partitions and permutations

Question

A $d$-regular partition is a partition of an $n$ element set with the additional restriction that $x,y$ with $|x-y|<d$ cannot be in the same block. So, if $d=2$, say, then the partition $\{1,4\}\cup\{2,3,5\}$ is not $d$-regular because $2$ and $3$ are consecutive elements (i.e., $|3-2|=1\ngeqslant d$). It is known that $d$-regular set partitions are counted by Bell numbers: $B_{n-d+1}$. See the nice paper of A. Kasraoui at http://www.emis.de/journals/SLC/wpapers/s62kasr.html for the details.

We can define $d$-regular permutations similarly where in place of blocks we use cycles. So, for example, the permutation (1 4) (2 3 5) is not permitted in a 2-regular permutation by the same reasons as above.

How many $d$-regular permutations are there on $n$ elements?

Answer 1

$d$-regularity

Define $d$-regularity of a permutation as the minimum over all possible differences within cycles of the permutation. It is convenient to let the identity permutation in $S_n$ has $d$-regularity equal to $n$.

This gives the following table (column $d$ count number of $d$-regular permutations): $$ \begin{array}{ccccccc} 1 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 1 & 1 & \text{} & \text{} & \text{} & \text{} & \text{} \\ 4 & 1 & 1 & \text{} & \text{} & \text{} & \text{} \\ 19 & 3 & 1 & 1 & \text{} & \text{} & \text{} \\ 103 & 12 & 3 & 1 & 1 & \text{} & \text{} \\ 651 & 54 & 10 & 3 & 1 & 1 & \text{} \\ 4702 & 281 & 42 & 10 & 3 & 1 & 1 \\ \end{array} $$ The first column gives no hit in the OEIS (which here seems like the most natural to test).

Accumulating the rows give $$ \begin{array}{ccccccc} 1 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 1 & 2 & \text{} & \text{} & \text{} & \text{} & \text{} \\ 4 & 5 & 6 & \text{} & \text{} & \text{} & \text{} \\ 19 & 22 & 23 & 24 & \text{} & \text{} & \text{} \\ 103 & 115 & 118 & 119 & 120 & \text{} & \text{} \\ 651 & 705 & 715 & 718 & 719 & 720 & \text{} \\ 4702 & 4983 & 5025 & 5035 & 5038 & 5039 & 5040 \\ \end{array} $$

$d$-irregularity

We can do a similar calculation, where we compute the maximum over all possible differences in the cycles, and then take the minimum over all such values. We can perhaps call this the $d$-irregullarity of a permutation. $$ \begin{array}{ccccccc} 1 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 1 & 1 & \text{} & \text{} & \text{} & \text{} & \text{} \\ 1 & 2 & 3 & \text{} & \text{} & \text{} & \text{} \\ 1 & 4 & 7 & 12 & \text{} & \text{} & \text{} \\ 1 & 7 & 17 & 35 & 60 & \text{} & \text{} \\ 1 & 12 & 44 & 93 & 210 & 360 & \text{} \\ 1 & 20 & 103 & 275 & 651 & 1470 & 2520 \\ \end{array}$$ that is, for permutations of $\{1,2,3,4,5,6\}$, there are 44 permutations which are strictly $2$-irregular, i.e., maximal difference within at least one block is exactly $2$.

Reading of the coefficients and accumulating, we obtain $$ \begin{array}{ccccccc} 1 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 1 & 2 & \text{} & \text{} & \text{} & \text{} & \text{} \\ 1 & 3 & 6 & \text{} & \text{} & \text{} & \text{} \\ 1 & 5 & 12 & 24 & \text{} & \text{} & \text{} \\ 1 & 8 & 25 & 60 & 120 & \text{} & \text{} \\ 1 & 13 & 57 & 150 & 360 & 720 & \text{} \\ 1 & 21 & 124 & 399 & 1050 & 2520 & 5040 \\ \end{array} $$ For example, there are 399 $3$-irregular permutations of $1...7$.

I find no hit in the OEIS.

The $d$-irregularity of a permutation can be seen as a statistic on permutations, and this is now available as [St000209] in FindStat.

EDIT: Here is the non-accumulated table for d-regularity, cyclic difference. Columns give no hits in OEIS.

$$ \begin{array}{ccccccc} 1 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 1 & 1 & \text{} & \text{} & \text{} & \text{} & \text{} \\ 5 & 0 & 1 & \text{} & \text{} & \text{} & \text{} \\ 20 & 3 & 0 & 1 & \text{} & \text{} & \text{} \\ 109 & 10 & 0 & 0 & 1 & \text{} & \text{} \\ 668 & 44 & 7 & 0 & 0 & 1 & \text{} \\ 4801 & 210 & 28 & 0 & 0 & 0 & 1 \\ \end{array} $$