|
%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
| 