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