cp's OEIS Frontend

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.

%I A370656 #61 Apr 28 2024 11:20:20
%S A370656 1,1,1,2,5,21,108,737,5795,53635,549777,6294420
%N 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.
%C A370656 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.
%H A370656 Constantinos Kourouzides, <a href="/A370656/a370656.txt">C++ program</a>.
%H A370656 Constantinos Kourouzides, <a href="/A370656/a370656_3.txt">Python program</a>.
%H A370656 Constantinos Kourouzides, <a href="/A370656/a370656_2.txt">GNU Octave program</a>.
%H A370656 Ioannis Michos, Christina Savvidou, and Demetris Hadjiloucas, <a href="https://doi.org/10.37236/6808">On super-strong Wilf equivalence classes of permutations</a>, The Electronic Journal of Combinatorics, 25(2) (2018), #P2.54.
%e A370656 a(4)=5.
%e A370656 The 1st equivalence class, consisting of multisets {{1}, {1,2}, {1,2,3}}, contains the following 8 permutations in S_4:
%e A370656   (1) 1 2 3 4,
%e A370656   (2) 1 2 4 3,
%e A370656   (3) 1 4 3 2,
%e A370656   (4) 3 4 2 1,
%e A370656   (5) 2 4 3 1,
%e A370656   (6) 1 3 4 2,
%e A370656   (7) 4 3 2 1,
%e A370656   (8) 2 3 4 1.
%e A370656 The 2nd equivalence class, consisting of multisets {{1}, {2,3}, {1,1,2}}, contains the following 4 permutations in S_4:
%e A370656   (1) 4 3 1 2,
%e A370656   (2) 2 1 4 3,
%e A370656   (3) 3 4 1 2,
%e A370656   (4) 2 1 3 4.
%e A370656 The 3rd equivalence class, consisting of multisets {{2}, {1,1}, {1,2,3}}, contains the following 4 permutations in S_4:
%e A370656   (1) 4 2 3 1,
%e A370656   (2) 1 4 2 3,
%e A370656   (3) 1 3 2 4,
%e A370656   (4) 3 2 4 1.
%e A370656 The 4th equivalence class, consisting of multisets {{2}, {1,3}, {1,1,2}}, contains the following 4 permutations in S_4:
%e A370656   (1) 3 1 4 2,
%e A370656   (2) 4 1 3 2,
%e A370656   (3) 2 3 1 4,
%e A370656   (4) 2 4 1 3.
%e A370656 The 5th equivalence class, consisting of multisets {{3}, {1,2}, {1,1,2}}, contains the following 4 permutations in S_4:
%e A370656   (1) 3 2 1 4,
%e A370656   (2) 4 2 1 3,
%e A370656   (3) 4 1 2 3,
%e A370656   (4) 3 1 2 4.
%p A370656 f:= l-> (n-> {seq(sort([seq(abs(l[i]-l[j]), i=1..j-1)]), j=2..n)})(nops(l)):
%p A370656 a:= n-> nops({map(f, combinat[permute](n))[]}):
%p A370656 seq(a(n), n=0..9);  # _Alois P. Heinz_, Mar 13 2024
%o A370656 (PARI)
%o A370656 C(p)={vector(#p, i, vecsort(vector(i-1, j, abs(p[i]-p[j]))))}
%o A370656 a(n)={my(M=Map()); forperm(n, p, mapput(M,C(p),1)); #M} \\ _Andrew Howroyd_, Feb 24 2024
%Y A370656 Cf. A000142, A001710.
%K A370656 nonn,more
%O A370656 0,4
%A A370656 _Constantinos Kourouzides_, Feb 24 2024
%E A370656 a(11) from _Andrew Howroyd_, Feb 24 2024