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,1

Links

Table of n, a(n) for n=1..6.

Prog

(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;

Crossrefs

Sequence in context: A215638 A057997 A290590 * A005273 A171990 A103898

Adjacent sequences: A263799 A263800 A263801 * A263803 A263804 A263805

Keyword

nonn,hard,more

Author

Attila Egri-Nagy, Oct 27 2015

Status

approved