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

2, 3, 16, 413, 25346, 6825268

Offset: 1

Author

Attila Egri-Nagy, Oct 27 2015

Keywords

• nonn
• hard
• more

Programs

GAP

# GAP 4.7 http://www.gap-system.org
# brute-force  enumeration of independent sets in the symmetric group
# inefficient (~4GB RAM needed, n=4 can take hours),
# but short, readable, self-contained
# higher terms can be calculated by the SubSemi package
# https://github.com/egri-nagy/subsemi
IsIndependentSet := function(A)
return IsDuplicateFreeList(A) and
         (Size(A)<2 or
          ForAll(A,x-> not (x in Group(Difference(A,[x])))));
end;
for n in [1..4] do
Sn := SymmetricGroup(IsPermGroup,n);
allsubsets := Combinations(AsList(Sn));
iss := Filtered(allsubsets, IsIndependentSet);
Display(Size(iss));
od;