A257919 The number of combinatorial equivalence classes of n-endomorphisms on a rank-3 semigroup.

7, 304, 9958, 288280, 7973053, 217032088, 5875893676, 158794026640, 4288744989139, 115807878426592, 3126918614998354, 84427755760664680, 2279557984193621065, 61548142781949118216, 1661800549993751359192, 44868621103769828836000, 1211452826087259054393631

Offset: 1

Author

Louis J. Rubin, May 18 2015

Keywords

• nonn
• easy

Comments

An n-endomorphism of a free semigroup is an endomorphism that sends every generator to a word of length <= n. Two n-endomorphisms are combinatorially equivalent if they are conjugate under an automorphism of the semigroup. This sequence gives the number of combinatorial equivalence classes of n-endomorphisms on a rank-3 semigroup, for n=1,2,3,...

Links

• Louis Rubin and Brian Rushton, Combinatorial Equivalence of m-Endomorphisms, arXiv:1412.3001 [math.CO], 2014-2015.
• Index entries for linear recurrences with constant coefficients, signature (44,-553,2760,-6219,6156,-2187).

Crossrefs

Cf. A134057, which gives the number of classes for a rank-2 semigroup.

Cf. A006516, which gives the number of classes for a rank-2 monoid.

Programs

Magma

[(3^n-1)*(12*n+17+9*(9^n-2*3^n))/16: n in [1..20]]; // Bruno Berselli, May 19 2015

Mathematica

Table[(3^n-1)(12 n + 17 + 9 (9^n - 2 3^n))/16, {n, 20}] (* Giovanni Resta, May 19 2015 *)

Formula

a(n) = (1/6)*(((3^(n+1)-3)/2)^3+3*n*((3^(n+1)-3)/2)+2*((3^(n+1)-3)/2)) = (3^n-1)*(12*n + 17 + 9*(9^n - 2*3^n))/16. [simplified by_Giovanni Resta_]

G.f.: x*(7 - 4*x + 453*x^2 - 1080*x^3)/((1 - 36*x + 243*x^2)*(1 - 4*x + 3*x^2)^2). [Bruno Berselli, May 19 2015]