A263802 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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