A072844 Number of words of length 2n-1 generated by the two letters s and t that reduce to the identity 1 by 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.

0, 0, 0, 1, 9, 55, 286, 1365, 6188, 27132, 116281, 490337, 2043275, 8439210, 34621041, 141290436, 574274008, 2326683921, 9402807817, 37923176863, 152705590518, 614111175965, 2467123420524, 9903167265124, 39725253489545

Offset: 1

Author

Jamaine Paddyfoot and John W. Layman, Jul 24 2002

Keywords

• nonn

Examples

			The 9 words of length 9 are ssssssstt, sssssstts, sssssttss, ssssttsss, sssttssss, ssttsssss, sttssssss, ttsssssss, tssssssst. - _Sean A. Irvine_, Oct 31 2024
		

References

• H.S.M. Coxeter and W.O.J. Moser, Generators and Relations for Discrete Groups, Fourth Edition, (p.134).

Links

• Haggai Liu, Enumerative Properties of Cogrowth Series on Free Products of Finite Groups, ACA 2021 Session on Algorithmic Combinatorics, 2021.

Crossrefs

Cf. A072266.

Bisection of A377573.

Formula

a(n) = 9*a(n-1) - 26*a(n-2) + 25*a(n-3) - 4*a(n-4).

g.f.: x^4 / ((1 - 4*x)*(1 - 5*x + 6*x^2 - x^3)). - Colin Barker, Feb 24 2017

28*a(n) = 4^n -4*( 2*A005021(n) -9*A005021(n-1) +11*A005021(n-2) ). - R. J. Mathar, Nov 05 2024