3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Andy Soffer Jun 3 '14 at 5:49
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ The second column in the second display looks familiar. $\endgroup$ – Gerry Myerson Jun 3 '14 at 23:32
  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson Jun 3 '14 at 23:38
  • $\begingroup$ 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. $\endgroup$ – Per Alexandersson Jun 4 '14 at 6:28
  • $\begingroup$ @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. $\endgroup$ – Peter Dukes Jun 4 '14 at 16:42
  • $\begingroup$ @PeterDukes: Added. However, I can't see any new structure. $\endgroup$ – Per Alexandersson Jun 7 '14 at 10:10

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.