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

Author

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

Keywords

• nonn
• easy

Examples

			The words tttt=tsts=stst=1 so a(2)=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).

Crossrefs

Bisection of A377573.

Programs

Mathematica

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

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

Formula

G.f.: 1 -x*(2*x-1)*(x^2-4*x+1)/((4*x-1)*(x^3-6*x^2+5*x-1)). - 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

14*a(n) = 4^n +2*(3*A005021(n) -10*A005021(n-1) +6*A005021(n-2)), n>0. - R. J. Mathar, Nov 05 2024