cp's OEIS Frontend

A263803 Number of conjugacy classes of independent sets of permutations of n points, i.e., subsets of the symmetric group of degree n up to relabeling the points with the property that none of the elements in the subset can be generated by the rest of the subset.

%I A263803 #16 Mar 25 2016 05:59:46
%S A263803 2,3,6,31,258,10294
%N A263803 Number of conjugacy classes of independent sets of permutations of n points, i.e., subsets of the symmetric group of degree n up to relabeling the points with the property that none of the elements in the subset can be generated by the rest of the subset.
%o A263803 (GAP)
%o A263803 # GAP 4.7 http://www.gap-system.org
%o A263803 # brute-force enumeration of conjugacy classes of
%o A263803 # independent sets in the symmetric group,
%o A263803 # inefficient (~4GB RAM needed, n=4 can take hours),
%o A263803 # but short, readable, self-contained
%o A263803 # higher terms can be calculated by the SubSemi package
%o A263803 # https://github.com/egri-nagy/subsemi
%o A263803 IsIndependentSet := function(A)
%o A263803   return IsDuplicateFreeList(A) and
%o A263803          (Size(A)<2 or
%o A263803           ForAll(A,x-> not (x in Group(Difference(A,[x])))));
%o A263803 end;
%o A263803 # we choose the minimal element (in lexicographic order) as the
%o A263803 # representative of the equivalence class
%o A263803 Rep := function(A, Sn)
%o A263803   return Minimum(Set(Sn, g->Set(A, x->x^g)));
%o A263803 end;
%o A263803 CalcIndependentConjugacyClasses := function(n)
%o A263803   local Sn, allsubsets, iss, reps;
%o A263803   Sn := SymmetricGroup(IsPermGroup,n);
%o A263803   allsubsets := Combinations(AsList(Sn));
%o A263803   iss := Filtered(allsubsets, IsIndependentSet);
%o A263803   reps := Set(iss, x->Rep(x,Sn));
%o A263803   Print(Size(iss)," ", Size(reps),"\n");
%o A263803 end;
%o A263803 for i in [1..4] do CalcIndependentConjugacyClasses(i); od;
%Y A263803 Cf. A263802.
%K A263803 nonn,hard,more
%O A263803 1,1
%A A263803 _Attila Egri-Nagy_, Oct 27 2015