A215650 - OEIS

%I #58 Mar 25 2021 10:23:05

%S 1,2,10,1299,3161965550

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

%C The semigroup analog of A005432.

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

%C The first 4 terms can be calculated by brute force search (see attached program).

%H James East, Attila Egri-Nagy, James D. Mitchell, <a href="https://doi.org/10.1007/s00233-017-9869-2">Enumerating Transformation Semigroups</a>, Semigroup Forum 95, 109-125 (2017); arXiv: <a href="https://arxiv.org/abs/1403.0274">1403.0274</a> [math.GR], 2014-2017.

%o (GAP)

%o ################################################################################

%o # GAP 4.5 function implementing a brute force search for submagmas of a magma.

%o # (C) 2012 Attila Egri-Nagy www.egri-nagy.hu

%o # GAP can be obtained from www.gap-system.org

%o ################################################################################

%o # The function goes through all the subsets of the given magma (groups,

%o # semigroups) and checks whether they form a magma or not.

%o # If yes, then the submagma is collected.

%o # The function returns the list of all (nonempty) submagmas.

%o BruteForceSubMagmaSearch := function(M)

%o local bitlist, #the characteristic function of a subset

%o       i, #an integer to index through the bitlist

%o       n, #size of the input magma

%o       elms, #elements of the magma

%o       gens, #generator set of a submagma

%o       submagmas, #the submagmas

%o       duplicates, #for counting how many times we encounter the same submagma

%o       nonsubmagmas; #counting how many subsets are not submagmas

%o       # duplicates + nonsubmagmas = 2^n-1

%o   n := Size(M);

%o   submagmas := [];

%o   elms := AsList(M);

%o   duplicates := 0;

%o   nonsubmagmas := 0;

%o   bitlist := BlistList([1..n],[1]); #we start with the first element, the

%o   #empty set can be added afterwards, if the magma's definition allows it

%o   repeat

%o     #constructing a generator set based on the bitlist##########################

%o     gens := [];

%o     Perform([1..n],function(x) if bitlist[x] then Add(gens, elms[x]);fi;end);

%o     #checking whether it is a submagma

%o if Size(gens) = Size(Magma(gens)) then

%o       if gens in submagmas then

%o         duplicates := duplicates + 1;

%o       else

%o         AddSet(submagmas,gens);

%o       fi;

%o     else

%o       nonsubmagmas := nonsubmagmas + 1;

%o     fi;

%o     #binary +1 applied to bitlist###############################################

%o     i := 1;

%o     while (i<=n) and (bitlist[i]) do

%o       bitlist[i] := false;

%o       i := i + 1;

%o     od;

%o     if i <= n then bitlist[i] := true;fi;

%o     ############################################################################

%o   until SizeBlist(bitlist) = 0;

%o   Print("#I Submagmas:", Size(submagmas),

%o         " Duplicates:", duplicates,

%o         " Nonsubmagmas:", nonsubmagmas,"\n");

%o   return submagmas;

%o end;

%Y Cf. A005432, A215651.

%K nonn,hard,more,nice

%O 0,2

%A _Attila Egri-Nagy_, Aug 19 2012

%E a(4) moved from comments to data by _Andrey Zabolotskiy_, Mar 25 2021