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,1

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

Table of n, a(n) for n=1..17.

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

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]

Mathematica

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

Prog

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

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.

Sequence in context: A281435 A015005 A209806 * A002437 A376464 A300870

Adjacent sequences: A257916 A257917 A257918 * A257920 A257921 A257922

Keyword

nonn,easy

Author

Louis J. Rubin, May 18 2015

Status

approved