A370656 Number of cross-equivalence classes of the symmetric group S_n, where two permutations are cross-equivalent if the multiset of forward distances for every element i in the permutation, for 1 <= i <= n-1, up to and including n, is the same.

1, 1, 1, 2, 5, 21, 108, 737, 5795, 53635, 549777, 6294420

Offset

0,4

Comments

The equivalence classes are defined based on a problem described on page 10 of the paper "On super-strong Wilf equivalence classes of permutations" by Ioannis Michos, Christina Savvidou, and Demetris Hadjiloucas, The Electronic Journal of Combinatorics 25 (2) (2018). For each permutation of n elements, distances are calculated as the absolute difference in positions for each pair of elements. For each element in a permutation of S_n, that is less than or equal to n-1, one calculates the absolute difference with every other element that comes after it. Permutations are then grouped into equivalence classes when their multisets of distances match. The sequence was generated using a Python as well as a C++ program. The program enumerates all permutations of n elements and classifies them into these equivalence classes.

Links

Table of n, a(n) for n=0..11.

Constantinos Kourouzides, C++ program.

Constantinos Kourouzides, Python program.

Constantinos Kourouzides, GNU Octave program.

Ioannis Michos, Christina Savvidou, and Demetris Hadjiloucas, On super-strong Wilf equivalence classes of permutations, The Electronic Journal of Combinatorics, 25(2) (2018), #P2.54.

Example

a(4)=5.
The 1st equivalence class, consisting of multisets {{1}, {1,2}, {1,2,3}}, contains the following 8 permutations in S_4:
  (1) 1 2 3 4,
  (2) 1 2 4 3,
  (3) 1 4 3 2,
  (4) 3 4 2 1,
  (5) 2 4 3 1,
  (6) 1 3 4 2,
  (7) 4 3 2 1,
  (8) 2 3 4 1.
The 2nd equivalence class, consisting of multisets {{1}, {2,3}, {1,1,2}}, contains the following 4 permutations in S_4:
  (1) 4 3 1 2,
  (2) 2 1 4 3,
  (3) 3 4 1 2,
  (4) 2 1 3 4.
The 3rd equivalence class, consisting of multisets {{2}, {1,1}, {1,2,3}}, contains the following 4 permutations in S_4:
  (1) 4 2 3 1,
  (2) 1 4 2 3,
  (3) 1 3 2 4,
  (4) 3 2 4 1.
The 4th equivalence class, consisting of multisets {{2}, {1,3}, {1,1,2}}, contains the following 4 permutations in S_4:
  (1) 3 1 4 2,
  (2) 4 1 3 2,
  (3) 2 3 1 4,
  (4) 2 4 1 3.
The 5th equivalence class, consisting of multisets {{3}, {1,2}, {1,1,2}}, contains the following 4 permutations in S_4:
  (1) 3 2 1 4,
  (2) 4 2 1 3,
  (3) 4 1 2 3,
  (4) 3 1 2 4.

Maple

f:= l-> (n-> {seq(sort([seq(abs(l[i]-l[j]), i=1..j-1)]), j=2..n)})(nops(l)):
a:= n-> nops({map(f, combinat[permute](n))[]}):
seq(a(n), n=0..9);  # Alois P. Heinz, Mar 13 2024

Prog

(PARI)
C(p)={vector(#p, i, vecsort(vector(i-1, j, abs(p[i]-p[j]))))}
a(n)={my(M=Map()); forperm(n, p, mapput(M, C(p), 1)); #M} \\ Andrew Howroyd, Feb 24 2024

Crossrefs

Cf. A000142, A001710.

Sequence in context: A347497 A130471 A002628 * A357919 A020129 A129582

Adjacent sequences: A370652 A370653 A370654 * A370657 A370658 A370659

Keyword

nonn,more

Author

Constantinos Kourouzides, Feb 24 2024

Extensions

a(11) from Andrew Howroyd, Feb 24 2024

Status

approved