A071930 Number of words of length 2n in the two letters s and t that reduce to the identity 1 by using the relations ssTT=1, ststSS=1 and ststTT=1, where S and T are the inverses of s and t, respectively (i.e., sS=1 and tT=1). The generators s and t and the three stated relations generate the quaternion group Q4.

0, 6, 12, 72, 240, 1056, 4032, 16512, 65280, 262656, 1047552, 4196352, 16773120, 67117056, 268419072, 1073774592, 4294901760, 17180000256, 68719214592, 274878431232, 1099510579200, 4398048608256, 17592181850112

Offset: 1

Author

John W. Layman and Jamaine Paddyfoot (jay_paddyfoot(AT)hotmail.com), Jun 14 2002

Keywords

• nonn
• easy

Comments

a(n) = A003683(n+1)/6. No words of odd length (see the description above) reduce to 1.

Links

• G. C. Greubel, Table of n, a(n) for n = 1..1000
• Index entries for linear recurrences with constant coefficients, signature (2,8).

Crossrefs

Cf. A003674, A003683.

Programs

Magma

[4^(n-1)-(-2)^(n-1): n in [1..40]]; // G. C. Greubel, Feb 17 2023

Mathematica

Table[2^(2n-2)-(-2)^(n-1),{n,30}] (* or *) LinearRecurrence[{2,8},{0,6},30] (* Harvey P. Dale, Dec 10 2012 *)

SageMath

[4^(n-1)-(-2)^(n-1) for n in range(1,41)] # G. C. Greubel, Feb 17 2023

Formula

a(n) = 2^(2*n-2) - (-2)^(n-1) = 6*A003683(n-1).

From Harvey P. Dale, Dec 10 2012: (Start)

a(n) = 2*a(n-1) + 8*a-(n-2).

G.f.: 6*x^2/(1-2*x-8*x^2). (End)

G.f.: Q(0), where Q(k)= 1 - 1/(4^k - 4*x*16^k/(4*x*4^k - 1/(1 + 1/(2*4^k - 16*x*16^k/(8*x*4^k +1/Q(k+1)))))); (continued fraction). - Sergei N. Gladkovskii, May 21 2013

a(n) = 2*A003674(n-1). - G. C. Greubel, Feb 17 2023