OFFSET
0,4
COMMENTS
The equivalence classes are defined from the notion of cross equivalence described on page 10 of the paper "On super-strong Wilf equivalence classes of permutations" by Demetris Hadjiloucas, Ioannis Michos, and Christina Savvidou, The Electronic Journal of Combinatorics 25 (2) (2018). Represent a permutation by its position vector p=(p_1,...,p_n), where p_i is the position of the element i. For i=1,...,n-1, form the multiset M_i(p) = {|p_i-p_j| : j=i+1,...,n}. Two permutations are equivalent if these multisets agree for every i. Initial terms were generated by Python and C++ programs which enumerate all permutations and classify them into equivalence classes. The terms a(13) through a(20) were computed using the recursive class-size distribution polynomial P_n(u) = Sum_{k >= 0} c(n,k)*u^k, where c(n,k) is the number of equivalence classes of cardinality 2^k. These values were independently verified by a separate C++ implementation, with checks P_n(2) = n! for n = 13, ..., 20. - edited by Constantinos Kourouzides, Jun 30 2026
LINKS
Constantinos Kourouzides, C++ program.
Constantinos Kourouzides, Python program.
Constantinos Kourouzides, GNU Octave program.
Constantinos Kourouzides, GitHub repository with programs and computational results for A370656.
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
KEYWORD
nonn,more,changed
AUTHOR
Constantinos Kourouzides, Feb 24 2024
EXTENSIONS
a(11) from Andrew Howroyd, Feb 24 2024
a(12)-a(20) from Constantinos Kourouzides, Jun 30 2026
STATUS
approved