login
Number of nonisomorphic groupoids with n elements.
(Formerly M4760 N2035)
58

%I M4760 N2035 #126 Sep 20 2023 10:01:40

%S 1,1,10,3330,178981952,2483527537094825,14325590003318891522275680,

%T 50976900301814584087291487087214170039,

%U 155682086691137947272042502251643461917498835481022016

%N Number of nonisomorphic groupoids with n elements.

%C The number of isomorphism classes of closed binary operations on a set of order n.

%C The term "magma" is also used as an alternative for "groupoid" since the latter has a different meaning in e.g. category theory. - _Joel Brennan_, Jan 20 2022

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Philip Tureček, <a href="/A001329/b001329.txt">Table of n, a(n) for n = 0..27</a>

%H J. Berman and S. Burris, <a href="http://www.math.uic.edu/~berman/1994-Groupoid-Catalog-Preprint.pdf">A computer study of 3-element groupoids</a> Lect. Notes Pure Appl. Math. 180 (1994) 379-429 <a href="http://www.ams.org/mathscinet-getitem?mr=1404949">MR1404949</a>

%H M. A. Harrison, <a href="http://dx.doi.org/10.1090/S0002-9939-1966-0200219-9">The number of isomorphism types of finite algebras</a>, Proc. Amer. Math. Soc., 17 (1966), 731-737.

%H Eric Postpischil, <a href="http://groups.google.com/groups?&amp;hl=en&amp;lr=&amp;ie=UTF-8&amp;selm=11802%40shlump.nac.dec.com&amp;rnum=2">Posting to sci.math newsgroup, May 21 1990</a>

%H Marko Riedel, <a href="http://math.stackexchange.com/questions/47792/how-many-non-isomorphic-binary-structures-on-the-set-of-n-elements">Counting non-isomorphic binary relations</a>, Mathematics Stack Exchange question.

%H N. J. A. Sloane, <a href="/A001329/a001329.jpg">Overview of A001329, A001423-A001428, A258719, A258720.</a>

%H T. Tamura, <a href="/A001329/a001329.pdf">Some contributions of computation to semigroups and groupoids</a>, pp. 229-261 of J. Leech, editor, Computational Problems in Abstract Algebra. Pergamon, Oxford, 1970. (Annotated and scanned copy)

%H Philip Turecek, <a href="/A001329/a001329.txt">Maple program</a>

%H Philip Tureček, <a href="https://arxiv.org/abs/2305.00269">Counting Finite Magmas</a>, arXiv:2305.00269 [math.CO], 2023.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Groupoid.html">Groupoid</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Magma_(algebra)">Magma (algebra)</a>

%H <a href="/index/Gre#groupoids">Index entries for sequences related to groupoids</a>

%F a(n) = Sum_{1*s_1+2*s_2+...=n} (fixA[s_1, s_2, ...]/(1^s_1*s_1!*2^s_2*s2!*...)) where fixA[s_1, s_2, ...] = Product_{i, j>=1} ( (Sum_{d|lcm(i, j)} (d*s_d))^(gcd(i, j)*s_i*s_j)). - _Christian G. Bower_, May 08 1998, Dec 03 2003

%F a(n) is asymptotic to n^(n^2)/n! = A002489(n)/A000142(n) ~ (e*n^(n-1))^n / sqrt(2*Pi*n). - _Christian G. Bower_, Dec 03 2003

%F a(n) = A079173(n) + A027851(n) = A079177(n) + A079180(n).

%F a(n) = A079183(n) + A001425(n) = A079187(n) + A079190(n).

%F a(n) = A079193(n) + A079196(n) + A079199(n) + A001426(n).

%p with(numtheory);

%p with(group):

%p with(combinat):

%p pet_cycleind_symm :=

%p proc(n)

%p local p, s;

%p option remember;

%p if n=0 then return 1; fi;

%p expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));

%p end;

%p pet_flatten_term :=

%p proc(varp)

%p local terml, d, cf, v;

%p terml := [];

%p cf := varp;

%p for v in indets(varp) do

%p d := degree(varp, v);

%p terml := [op(terml), seq(v, k=1..d)];

%p cf := cf/v^d;

%p od;

%p [cf, terml];

%p end;

%p bs_binop :=

%p proc(n)

%p option remember;

%p local dsjc, flat, p, q, len,

%p cyc, cyc1, cyc2, l1, l2, res;

%p if n=0 then return 1; fi;

%p if n=1 then return 1; fi;

%p res := 0;

%p for dsjc in pet_cycleind_symm(n) do

%p flat := pet_flatten_term(dsjc);

%p p := 1;

%p for cyc1 in flat[2] do

%p l1 := op(1, cyc1);

%p for cyc2 in flat[2] do

%p l2 := op(1, cyc2);

%p len := lcm(l1,l2); q := 0;

%p for cyc in flat[2] do

%p if len mod op(1, cyc) = 0 then

%p q := q + op(1, cyc);

%p fi;

%p od;

%p p := p * q^(l1*l2/len);

%p od;

%p od;

%p res := res + p*flat[1];

%p od;

%p res;

%p end;

%t magmas[n_] := (

%t rul1 = {{a[i_],j_},{a[k_],l_}} :> sum[i,k]^(j*l*GCD[i,k]*(2-Boole[i==k]));

%t rul2 = {a[r_],s_} :> If[Mod[lcm,r]==0,r*s,0];

%t trans[mo_] := (

%t listc = FactorList@mo;

%t list = listc[[2;;]];

%t sum[i_,k_] := (

%t lcm = LCM[i,k];

%t Plus@@(list/.rul2)

%t );

%t pairs = Select[Tuples[list,2],OrderedQ];

%t listc[[1,1]]^listc[[1,2]]*Times@@(pairs/.rul1)

%t );

%t trans/@CycleIndexPolynomial[SymmetricGroup@n,Array[a,n]]

%t );

%t (* _Philip Turecek_, May 25 2022 *)

%o (Sage)

%o R.<a> = InfinitePolynomialRing(QQ)

%o @cached_function

%o def Z(n):

%o if n==0:

%o return R.one()

%o return sum(a[k]*Z(n-k) for k in (1..n))/n

%o def magmas(n):

%o P = Z(n)

%o q = 0

%o c = P.coefficients()

%o count = 0

%o for m in P.monomials():

%o r = 1

%o T = m.variables()

%o S = list(T)

%o for u in T:

%o i = R.varname_key(str(u))[1]

%o j = m.degree(u)

%o D = 0

%o for d in divisors(i):

%o D += d*m.degrees()[-d-1]

%o r *= D^(i*j^2)

%o S.remove(u)

%o for v in S:

%o k = R.varname_key(str(v))[1]

%o l = m.degree(v)

%o D = 0

%o for d in divisors(lcm(i,k)):

%o try:

%o D += d*m.degrees()[-d-1]

%o except:

%o break

%o r *= D^(gcd(i,k)*j*l*2)

%o q += c[count]*r

%o count += 1

%o return q

%o # _Philip Turecek_, Nov 20 2022

%Y Cf. A001424, A001425, A002489, A006448, A029850, A030245-A030265, A030271, A038015-A038023.

%K nonn,nice

%O 0,3

%A _N. J. A. Sloane_

%E More terms from _Christian G. Bower_, May 08 1998