Attila Egri-Nagy - 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.

2, 3, 6, 31, 258, 10294

Offset: 1

Attila Egri-Nagy, Oct 27 2015

# GAP 4.7 http://www.gap-system.org
# brute-force enumeration of conjugacy classes 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;
# we choose the minimal element (in lexicographic order) as the
# representative of the equivalence class
Rep := function(A, Sn)
  return Minimum(Set(Sn, g->Set(A, x->x^g)));
end;
CalcIndependentConjugacyClasses := function(n)
  local Sn, allsubsets, iss, reps;
  Sn := SymmetricGroup(IsPermGroup,n);
  allsubsets := Combinations(AsList(Sn));
  iss := Filtered(allsubsets, IsIndependentSet);
  reps := Set(iss, x->Rep(x,Sn));
  Print(Size(iss)," ", Size(reps),"\n");
end;
for i in [1..4] do CalcIndependentConjugacyClasses(i); od;

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.

Original entry on oeis.org

2, 3, 16, 413, 25346, 6825268

Offset: 1

Attila Egri-Nagy, Oct 27 2015

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

A261750 Number of conjugacy classes of two-element generating sets in the symmetric group S_n.

Original entry on oeis.org

0, 1, 2, 5, 31, 163, 1576

Offset: 1

Attila Egri-Nagy, Aug 30 2015

Two generating sets are considered to be the same if they differ only by some relabeling of the points, i.e., conjugating by some element of S_n. For instance, the generating set {(1,2), (1,2,3,4)} is the same as {(2,3),(1,2,3,4)} by the relabeling 1->2, 2->3, 3->4, 4->1. As a non-example, the generating sets {(1,2),(1,2,3,4,5)} and {(1,3),(1,2,3,4,5)} are different, since the points in the transpositions are differently placed in the 5-cycle.

Cf. A001691.

# GAP 4.7 code for calculating the number of distinct 2-generating sets of
# symmetric groups.
# This code is written for readability, and to minimize package dependencies.
# 2015 Attila Egri-Nagy
# decides whether the given generating sets generate the symmetric group of
# degree n or not
IsSn := function(gens,n)
  return Size(Group(gens))=Factorial(n);
end;
# returns all degree n permutations (i.e., elements of the symmetric group)
AllPermsDegn := function(n)
  return AsList(SymmetricGroup(IsPermGroup,n));
end;
# first 5 entries of A001691 calculated in an inefficient manner
# taking all sets of cardinality 2 and check
gensets := List([1..5],
                x->Filtered(Combinations(AllPermsDegn(x),2),
                        y->IsSn(y,x)));
Display(List(gensets,Size));
# returns the conjugacy class representative of P under G
# calculates the conjugacy class of P and returns the minimum element
# P - set of permutations
# G - permutation group
ConjClRep := function(P, G)
  return Minimum(Set(AsList(G), x-> Set(P, y->y^x)));
end;
Display(List([1..5],
        x->Size(Set(gensets[x],
                y->ConjClRep(y,SymmetricGroup(IsPermGroup,x))))));

A242101 Number of conjugacy classes of the symmetric group S_n when conjugating only by even permutations.

Original entry on oeis.org

1, 2, 4, 6, 8, 12, 16, 24, 32, 44, 58, 80, 104, 138, 180, 236, 302, 390, 496, 634, 800, 1010, 1264, 1586, 1970, 2448, 3024, 3734, 4582, 5622, 6862, 8372, 10168, 12336, 14912, 18010, 21672, 26052, 31226, 37384, 44632, 53226, 63318, 75238, 89202, 105630, 124832

Offset: 1

Attila Egri-Nagy, Aug 14 2014

nonn

Cf. A242099 (by dihedral group), A000041 (by symmetric group itself), A061417 (by cyclic group).

Cf. A046682.

List([1..11], n->Size(OrbitsDomain(AlternatingGroup(IsPermGroup, n), SymmetricGroup(IsPermGroup, n), \^)));

For n >=2, a(n) = A000041(n) + A000700(n) = 2*A046682(n) [by a formula in A046682]. - Eric M. Schmidt, Aug 23 2014

More terms from Eric M. Schmidt, Aug 23 2014

A242099 Number of conjugacy classes of the symmetric group S_n when conjugating by the dihedral group D_n.

Original entry on oeis.org

1, 2, 3, 8, 18, 84, 387, 2670, 20373, 182796, 1816325, 19973962, 239523846, 3113717784, 43589470208, 653840410004, 10461400104968, 177843770847822, 3201186945761289, 60822551319191028, 1216451005946790780, 25545471110008012860, 562000363929678643211

Offset: 1

Attila Egri-Nagy, Aug 14 2014

nonn

Eric M. Schmidt, Table of n, a(n) for n = 1..100

Cf. A242101 (by alternating group), A000041 (by symmetric group itself), A061417 (by cyclic group).

List([1..11],n->Size(OrbitsDomain(DihedralGroup(IsPermGroup,2*n),SymmetricGroup(IsPermGroup,n),\^)));

def a(n) : return (sum(euler_phi(n//d) * (n//d)^d * factorial(d) for d in divisors(n))//n + [(factorial(n//2) + factorial((n+1)//2 - 1)) * 2^(n//2-1), factorial((n-1)//2) * 2^((n-1)//2)][n%2]) // 2 # Eric M. Schmidt, Aug 23 2014

a(n) = (A061417(n) + b(n))/2, where b(n) = ((n-1)/2)! * 2^((n-1)/2) if n is odd, b(n) = ((n/2)! + (n/2-1)!) * 2^(n/2-1) if n is even. - Eric M. Schmidt, Aug 23 2014

More terms from Eric M. Schmidt, Aug 23 2014

A212319 The number of abstract groups with minimal permutation representations of degree n.

Original entry on oeis.org

1, 1, 2, 5, 7, 13, 26, 82, 104, 212, 441, 1171, 1780

Offset: 1

Attila Egri-Nagy, Oct 25 2013

a(n) can be derived by setting a(1)=1 and then taking the differences between the consecutive elements of A174511. This is due to the fact that if an abstract group can be represented as a permutation group on n points, then it can also be represented by a permutation group of degree n+1, simply by including a fixed point. In other words, the sum of the first n terms give you the number of isomorphism classes of subgroups of the symmetric group of degree n.

			a(1)=1, since only the trivial group 1 can be represented as permutations of a single point. a(2)=1 because Z_2,1 can both be realized by permutations of two points but for 1 this representation is not minimal. a(3)=2 with Z_3 and S_3 appearing for the first time.

Cf. A174511.

a(1)=1, a(n) = A174511(n) - A174511(n-1), n>1.

A215651 Number of transformation semigroups acting on n points (counting conjugates as one), i.e., the number of subsemigroups of the full transformation semigroup T_n.

Original entry on oeis.org

1, 2, 8, 283, 132069776

Offset: 0

Attila Egri-Nagy, Aug 19 2012

The semigroup analog of A000638.

We apply the categorical viewpoint and consider the empty set as a semigroup.

James East, Attila Egri-Nagy, James D. Mitchell, Enumerating Transformation Semigroups, Semigroup Forum 95, 109-125 (2017); arXiv: 1403.0274 [math.GR], 2014-2017.

Cf. A000638, A215650.

################################################################################
# GAP 4.5 function calculating the conjugacy classes of a set of subsemigrops.
# (C) 2012 Attila Egri-Nagy www.egri-nagy.hu
# GAP can be obtained from www.gap-system.org
################################################################################
# Input: list of subsemigroups of a transformation semigroup,
#        automorphism group of the semigroup
# Output: list of conjugacy classes
ConjugacyClassesSubsemigroups := function(subsemigroups, G)
local ssg, #subsemigroup
      ccl, #conjugacy class
      ccls; #result: all conjugacy classes
  ccls := [];
  for ssg in subsemigroups do
    #we check whether the subsemigroup is already in a conjugacy class
    if not ForAny(ccls, x -> ssg in x) then
      #conjugating by all group elements
      ccl := DuplicateFreeList(
                     List(G,
                          g -> AsSortedList(List(ssg, t-> t^g))));
      Add(ccls, ccl);
    fi;
  od;
  return ccls;
end;

a(4) moved from a comment by Attila Egri-Nagy, Jan 09 2014 to data by Andrey Zabolotskiy, Mar 25 2021

A215650 Number of transformation semigroups acting on n points (counting conjugates as distinct); also the number of subsemigroups of the full transformation semigroup T_n.

Original entry on oeis.org

1, 2, 10, 1299, 3161965550

Offset: 0

Attila Egri-Nagy, Aug 19 2012

The semigroup analog of A005432.
We apply the categorical viewpoint and consider the empty set as a semigroup.
The first 4 terms can be calculated by brute force search (see attached program).

James East, Attila Egri-Nagy, James D. Mitchell, Enumerating Transformation Semigroups, Semigroup Forum 95, 109-125 (2017); arXiv: 1403.0274 [math.GR], 2014-2017.

Cf. A005432, A215651.

################################################################################
# GAP 4.5 function implementing a brute force search for submagmas of a magma.
# (C) 2012 Attila Egri-Nagy www.egri-nagy.hu
# GAP can be obtained from www.gap-system.org
################################################################################
# The function goes through all the subsets of the given magma (groups,
# semigroups) and checks whether they form a magma or not.
# If yes, then the submagma is collected.
# The function returns the list of all (nonempty) submagmas.
BruteForceSubMagmaSearch := function(M)
local bitlist, #the characteristic function of a subset
      i, #an integer to index through the bitlist
      n, #size of the input magma
      elms, #elements of the magma
      gens, #generator set of a submagma
      submagmas, #the submagmas
      duplicates, #for counting how many times we encounter the same submagma
      nonsubmagmas; #counting how many subsets are not submagmas
      # duplicates + nonsubmagmas = 2^n-1
  n := Size(M);
  submagmas := [];
  elms := AsList(M);
  duplicates := 0;
  nonsubmagmas := 0;
  bitlist := BlistList([1..n],[1]); #we start with the first element, the
  #empty set can be added afterwards, if the magma's definition allows it
  repeat
    #constructing a generator set based on the bitlist##########################
    gens := [];
    Perform([1..n],function(x) if bitlist[x] then Add(gens, elms[x]);fi;end);
    #checking whether it is a submagma
if Size(gens) = Size(Magma(gens)) then
      if gens in submagmas then
        duplicates := duplicates + 1;
      else
        AddSet(submagmas,gens);
      fi;
    else
      nonsubmagmas := nonsubmagmas + 1;
    fi;
    #binary +1 applied to bitlist###############################################
    i := 1;
    while (i<=n) and (bitlist[i]) do
      bitlist[i] := false;
      i := i + 1;
    od;
    if i <= n then bitlist[i] := true;fi;
    ############################################################################
  until SizeBlist(bitlist) = 0;
  Print("#I Submagmas:", Size(submagmas),
        " Duplicates:", duplicates,
        " Nonsubmagmas:", nonsubmagmas,"\n");
  return submagmas;
end;

a(4) moved from comments to data by Andrey Zabolotskiy, Mar 25 2021

cp's OEIS Frontend

User: Attila Egri-Nagy

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.

Views

Author

Keywords

Crossrefs

Programs

GAP

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.

Views

Author

Keywords

Programs

GAP

A261750 Number of conjugacy classes of two-element generating sets in the symmetric group S_n.

Views

Author

Keywords

Comments

Crossrefs

Programs

GAP

A242101 Number of conjugacy classes of the symmetric group S_n when conjugating only by even permutations.

Views

Author

Keywords

Crossrefs

Programs

GAP

Formula

Extensions

A242099 Number of conjugacy classes of the symmetric group S_n when conjugating by the dihedral group D_n.

Views

Author

Keywords

Links

Crossrefs

Programs

GAP

Sage

Formula

Extensions

A212319 The number of abstract groups with minimal permutation representations of degree n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A215651 Number of transformation semigroups acting on n points (counting conjugates as one), i.e., the number of subsemigroups of the full transformation semigroup T_n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Extensions

A215650 Number of transformation semigroups acting on n points (counting conjugates as distinct); also the number of subsemigroups of the full transformation semigroup T_n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Extensions