login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 1
1, 2, 10, 1299, 3161965550 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

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).

LINKS

Table of n, a(n) for n=0..4.

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

PROG

(GAP)

################################################################################

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

CROSSREFS

Cf. A005432, A215651.

Sequence in context: A245728 A171485 A291882 * A057015 A059732 A334575

Adjacent sequences:  A215647 A215648 A215649 * A215651 A215652 A215653

KEYWORD

nonn,hard,more,nice

AUTHOR

Attila Egri-Nagy, Aug 19 2012

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 12 22:55 EDT 2021. Contains 344978 sequences. (Running on oeis4.)