login
Number of quasitrivial semigroups on an arbitrary n-element set.
8

%I #38 Jun 12 2024 12:06:10

%S 1,1,4,20,138,1182,12166,146050,2003882,30930734,530477310,

%T 10007736906,205965058162,4592120925862,110259944144486,

%U 2836517343551714,77836238876829882,2269379773783175454,70057736432648552782,2282895953541692345722

%N Number of quasitrivial semigroups on an arbitrary n-element set.

%C Number of associative and quasitrivial binary operations on {1,...,n}. Convention a(0)=1.

%H G. C. Greubel, <a href="/A292932/b292932.txt">Table of n, a(n) for n = 0..410</a>

%H Miguel Couceiro, Jimmy Devillet, and Jean-Luc Marichal, <a href="http://arxiv.org/abs/1709.09162">Quasitrivial semigroups: characterizations and enumerations</a>, arXiv:1709.09162 [math.RA], 2017.

%H Jimmy Devillet, <a href="https://arxiv.org/abs/1712.07856">Bisymmetric and quasitrivial operations: characterizations and enumerations</a>, arXiv:1712.07856 [math.RA], 2017.

%H Jimmy Devillet and Miguel Couceiro, <a href="http://orbilu.uni.lu/handle/10993/39720">Characterizations and enumerations of classes of quasitrivial n-ary semigroups</a>, 98th Workshop on General Algebra (AAA98, Dresden, Germany 2019).

%H Jimmy Devillet, Jean-Luc Marichal, and Bruno Teheux, <a href="https://arxiv.org/abs/1811.11113">Classifications of quasitrivial semigroups</a>, arXiv:1811.11113 [math.RA], 2018.

%H Amya Luo, <a href="https://math.dartmouth.edu/theses/undergrad/2024/Luo-thesis.pdf">Pattern Avoidance in Nonnesting Permutations</a>, Undergraduate Thesis, Dartmouth College (2024). See p. 16.

%F E.g.f.: 1/(3 + x - 2*exp(x)).

%F Recurrence: a(0) = 1, a(n+1) = (n+1)*a(n) + 2*Sum_{k=0...n-1} binomial(n+1,k)*a(k).

%F Explicit form: a(n) = Sum_{i=0...n} Sum_{k=0...n-i} 2^i * (-1)^k * binomial(n,k) * S2(n-k,i) * (i+k)!, where S2(n,k) are the Stirling numbers of the second kind.

%F a(n) ~ n! / ((r-1) * (r-3)^(n+1)), where r = -LambertW(-1, -2*exp(-3)) = 3.5830738760366909976807989989303134394318270218566... - _Vaclav Kotesovec_, Sep 27 2017

%t With[{m=30}, CoefficientList[Series[1/(3+x-2*Exp[x]), {x,0,m}], x]*Range[0,m]!] (* _G. C. Greubel_, May 21 2019 *)

%o (PARI) my(x='x + O('x^30)); Vec(serlaplace(1/(x+3-2*exp(x)))) \\ _Michel Marcus_, May 21 2019

%o (Magma) m:=30; R<x>:=PowerSeriesRing(Rationals(), m); b:=Coefficients(R!( 1/(3+x-2*Exp(x)) )); [Factorial(n-1)*b[n]: n in [1..m]]; // _G. C. Greubel_, May 21 2019

%o (Sage) m = 30; T = taylor(1/(3+x-2*exp(x)), x, 0, m); [factorial(n)*T.coefficient(x, n) for n in (0..m)] # _G. C. Greubel_, May 21 2019

%Y Cf. A292933, A292934.

%K nonn,easy

%O 0,3

%A _Jean-Luc Marichal_, Sep 27 2017