A049295 Number of subgroups of index 4 in free group of rank n+1.

1, 71, 2143, 54335, 1321471, 31817471, 764217343, 18344733695, 440294408191, 10567189327871, 253613279903743, 6086723113107455, 146081381003558911, 3505953301484470271, 84142880178680889343, 2019429129941297135615, 48466299152487396933631

Offset: 0

Author

Valery A. Liskovets

Keywords

• nonn
• easy
• nice

References

• P. de la Harpe, Topics in Geometric Group Theory, Univ. Chicago Press, 2000, p. 23, N_{4,n}.
• R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.13(b).

Links

• M. Hall, Subgroups of finite index in free groups, Canad. J. Math., 1 (1949), 187-190.
• V. A. Liskovets and A. Mednykh, Enumeration of subgroups in the fundamental groups of orientable circle bundles over surfaces, Commun. in Algebra, 28, No. 4 (2000), 1717-1738.
• Index entries for linear recurrences with constant coefficients, signature (37,-368,1436,-2256,1152).

Crossrefs

Cf. A003319, A027837, A049290-A049294.

Programs

Mathematica

LinearRecurrence[{37,-368,1436,-2256,1152},{1,71,2143,54335,1321471},20] (* Harvey P. Dale, Apr 14 2016 *)

Formula

a(n) = 4*24^n-4*6^n-2*4^n+4*2^n-1.

G.f.: (264*x^3+116*x^2-34*x-1) / ((x-1)*(2*x-1)*(4*x-1)*(6*x-1)*(24*x-1)). [Colin Barker, Feb 17 2013]

Extensions

More terms from Carrie Westbrook (s1213407(AT)cedarville.edu)

Terms corrected by Colin Barker, May 08 2012

a(16) from Colin Barker, Feb 17 2013