cp's OEIS Frontend

A005345 Number of elements of a free idempotent monoid on n letters.

%I A005345 M1820 #28 Feb 16 2025 08:32:28
%S A005345 1,2,7,160,332381,2751884514766,272622932796281408879065987,
%T A005345 3641839910835401567626683593436003894250931310990279692,
%U A005345 848831867913830760986671126293000918118297635181600248839480614255059539078136221019132415247551725144817958905
%N A005345 Number of elements of a free idempotent monoid on n letters.
%C A005345 An idempotent monoid satisfies the equation xx=x for any element x.
%C A005345 A squarefree word may be equivalent to a smaller or larger word as a consequence of the idempotent equation.
%D A005345 M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA, 1983, p. 32.
%D A005345 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005345 Morgan Rogers, <a href="https://arxiv.org/abs/2408.17440">From free idempotent monoids to free multiplicatively idempotent rigs</a>, arXiv:2408.17440 [math.RA], 2024. See pp. 21, 23.
%H A005345 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Monoid.html">Monoid.</a>
%H A005345 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/FreeIdempotentMonoid.html">Free Idempotent Monoid</a>
%H A005345 <a href="/index/Mo#monoids">Index entries for sequences related to monoids</a>
%F A005345 a(n) = Sum_{k=0..n} (C(n, k) Prod_{i=1..k} (k-i+1)^(2^i)).
%F A005345 Binomial transform of A030450. - _Michael Somos_, Oct 22 2006
%t A005345 Array[Sum[Binomial[#, k]* Product[(k - i + 1)^(2^i), {i, k}], {k, 0, #}] &, 10, 0] (* _Michael De Vlieger_, Sep 05 2024 *)
%o A005345 (PARI) {a(n)=sum(k=0, n, binomial(n, k)*prod(i=1, k, (k-i+1)^2^i))} /* _Michael Somos_, Oct 22 2006 */
%Y A005345 A030449(n) = a(n) - 1.
%K A005345 nonn,easy
%O A005345 0,2
%A A005345 _N. J. A. Sloane_, _Jeffrey Shallit_
%E A005345 One more term from Gabriel Cunningham (gcasey(AT)mit.edu), Nov 14 2004