# d-regular partitions and permutations

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?

• A naive approach would be to attempt to count $d$-regular permutations by there associated set partitions (sending cycles to blocks). Given a particular $d$-regular set partition, it is easy to count the number of $d$-regular permutations associated to it. However, the map given in the paper, however pretty, doesn't play nicely with the block structure, so I think such an approach is doomed to fail. – Andy Soffer Jun 3 '14 at 5:49

## 1 Answer

$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}$$

• The second column in the second display looks familiar. – Gerry Myerson Jun 3 '14 at 23:32
• But I'm not sure I understand the count. The only strictly 2-regular permutation of $\{\,1,2,3\,\}$ I can see is $(13)$. The other transpositions $(12)$ and $(23)$ contain consecutive numbers, as do the 3-cycles $(123)$ and $(132)$, and I'm not sure what $d$ to assign to the identity, but the first display says the number of strictly 2-regular permutations is 3. – Gerry Myerson Jun 3 '14 at 23:38
• Oh, I see, I misread the conditions, the tables above has "in each block, the max difference is at most d". Will edit shortly, and fix the mistake. – Per Alexandersson Jun 4 '14 at 6:28
• @PerAlexandersson: If it is easy to tweak your code, can you please report if there is anything familiar when "difference" is replaced by "cyclic distance (mod $n$)"? I am not too surprised the above tables look mysterious because of boundary effects. – Peter Dukes Jun 4 '14 at 16:42
• @PeterDukes: Added. However, I can't see any new structure. – Per Alexandersson Jun 7 '14 at 10:10