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

Author

Constantinos Kourouzides, Feb 24 2024

Keywords

• nonn
• more

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.

Examples

			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.
		

Links

• 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.

Crossrefs

Cf. A000142, A001710.

Programs

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

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

Extensions

a(11) from Andrew Howroyd, Feb 24 2024