A265434 Consider the group freely generated by an element U of order 3 and an element S of order 2. a(n) gives the number of words in the alphabet {U,S} of length n that are equal to unity.

1, 0, 1, 1, 1, 5, 2, 14, 13, 31, 66, 77, 240, 286, 722, 1226, 2141, 4760, 7268, 16473, 27716, 54615, 106217, 187818, 388084, 685830, 1370162, 2569351, 4849538, 9526355, 17598392, 34694301, 65152925, 125679731, 242019753, 459049449, 893614680, 1695840536

Offset

0,6

Comments

One of the models of such a group is the full modular group PSL_2(Z).

Links

Robert Israel, Table of n, a(n) for n = 0..2000

G. Alkauskas, The modular group and words in its two generators, arXiv:1512.02596 [math.NT], 2015-2017.

G. Alkauskas, The modular group and words in its two generators, Lithuanian Math. J. 57(1) (2017), 1-12.

Jason Bell and Marni Mishna, On the Complexity of the Cogrowth Sequence, arXiv:1805.08118 [math.CO], 2018.

Formula

G.f.: G(x) satisfies (6*x^5-3*x^4+2*x^3+3*x^2-1)*G(x)^3 + (x^5-x^4+x^3+2*x^2-1)*G(x)^2 + (x^3-x^2+1)*G(x) + 1 = 0.

a(n) ~ sqrt(s*(5*r^3*s*(6*s+1) - 4*r^2*s*(3*s+1) + 3*r*(2*s^2+s+1) + 6*s^2+4*s-2) / (r^5*(18*s+1) - r^4*(9*s+1) + r^3*(6*s+1) + r^2*(9*s+2) - 3*s - 1)) / (2*sqrt(Pi)*n^(3/2)*r^(n-1)), where r = 0.5072330945238052458926282360080236... and s = 5.833428896122262867435103255185854... are real roots of the system of equations (r^3-r^2+1)*s + (6*r^5-3*r^4+2*r^3+3*r^2-1)*s^3 + (r^5-r^4+r^3+2*r^2-1)*s^2+1 = 0, r^3 + 3*(6*r^5-3*r^4+2*r^3+3*r^2-1)*s^2 + 2*(r^5-r^4+r^3+2*r^2-1)*s+1 = r^2. - Vaclav Kotesovec, Oct 24 2023

Example

For n=5 the a(n)=5 words are U^2S^2U, US^2U^2, S^2U^3, SU^3S, U^3S^2.

Maple

simpl:= proc(W) local A, Ap;
   Ap:= W;
   while A <> Ap do
     A:= Ap;
     Ap:= StringTools:-RegSubs("UUU"="", StringTools:-RegSubs("SS"="", A));
   od;
   A;
end proc:
F:= proc(n, W) option remember;
  if n = 0 then
     if W = "" then return 1 else return 0 fi;
  fi;
  procname(n-1, simpl(cat("S", W))) + procname(n-1, simpl(cat("UU", W)))
end proc:
seq(F(n, ""), n=0..40); # Robert Israel, Dec 09 2015

Mathematica

(* Program not suitable to compute a large number of terms *)
a[n_] := Count[Tuples[{U, S}, n] //. {A___, U, U, U, B___} | {A___, S, S, B___} -> {A, B}, {}];
Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 0, 20}] (* Jean-François Alcover, Jan 18 2018 *)

Crossrefs

Cf. A276408 (primitive words), A276409 (reduced words).

Sequence in context: A060422 A213751 A185781 * A189236 A341515 A191722

Adjacent sequences: A265431 A265432 A265433 * A265435 A265436 A265437

Keyword

nonn

Author

Giedrius Alkauskas, Dec 09 2015

Status

approved