A072266 Number of words of length 2n generated by the two letters s and t that reduce to the identity 1 using the relations sssssss=1, tt=1 and stst=1. The generators s and t along with the three relations generate the 14-element dihedral group D7.

1, 1, 3, 10, 35, 126, 462, 1717, 6451, 24463, 93518, 360031, 1394582, 5430530, 21242341, 83411715, 328589491, 1297937234, 5138431851, 20380608990, 80960325670, 322016144629, 1282138331587, 5109310929719, 20374764059254

Offset

0,3

Links

Colin Barker, Table of n, a(n) for n = 0..1000

H. S. M. Coxeter and W. O. J. Moser, Generators and Relations for Discrete Groups, 4th ed., Springer-Verlag, NY, reprinted 1984, p. 134.

Index entries for linear recurrences with constant coefficients, signature (9,-26,25,-4).

Formula

G.f.: (1-8*x+20*x^2-16*x^3+2*x^4)/(1-9*x+26*x^2-25*x^3+4*x^4). - Michael Somos, Jul 21, 2002

a(n) = 9*a(n-1) - 26*a(n-2) + 25*a(n-3) - 4*a(n-4) for n>4. - Colin Barker, Apr 26 2019

Example

The words tttt=tsts=stst=1 so a(2)=3.

Mathematica

LinearRecurrence[{9, -26, 25, -4}, {1, 1, 3, 10, 35}, 30] (* Harvey P. Dale, Apr 16 2022 *)

Prog

(PARI) a(n)=if(n<1, n==0, sum(k=-(n-1)\7, (n-1)\7, C(2*n-1, n+7*k)))
(PARI) Vec((1 - 8*x + 20*x^2 - 16*x^3 + 2*x^4) / ((1 - 4*x)*(1 - 5*x + 6*x^2 - x^3)) + O(x^30)) \\ Colin Barker, Apr 26 2019

Crossrefs

Sequence in context: A001700 A088218 A300975 * A085282 A149036 A316596

Adjacent sequences: A072263 A072264 A072265 * A072267 A072268 A072269

Keyword

nonn,easy

Author

Jamaine Paddyfoot (jay_paddyfoot(AT)hotmail.com) and John W. Layman, Jul 08 2002

Status

approved