A057009 Number of conjugacy classes of subgroups of index 3 in free group of rank n.

1, 7, 41, 235, 1361, 7987, 47321, 281995, 1685921, 10096867, 60524201, 362972155, 2177309681, 13062280147, 78368930681, 470199300715, 2821152888641, 16926788453827, 101560343826761, 609360901747675, 3656161925798801, 21936961098633907, 131621735219132441

Offset

1,2

Comments

Starting at a(2), consider that 2/3 - 1/2 = 1/6 with 1+6=7=a(2); 8/9 - 3/4 = 5/36 with 5+36=41=a(3); 26/27 - 7/8=19/216 with 19+216=235=a(4); 80/81 - 15/16=65/1296 with 65+1296=1361=a(5) and so forth. The numerators starting at a(3) are 5,19,65,211,665,2059,6305,... (see A001047) with 19 mod 5=4, 65 mod 19=8, 211 mod 65=16, 665 mod 211=32, 2059 mod 665=64, 6305 mod 2059=128, and so forth for higher powers of 2. - J. M. Bergot, May 09 2015

In other words, let f(n) = (3^(n-1)-1)/3^(n-1) - (2^(n-1)-1)/2^(n-1), then for n>=1 a(n) = numerator(f(n)) + denominator(f(n)). - Michel Marcus, May 29 2015

References

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.13(c), pp. 76, 112.

Links

Table of n, a(n) for n=1..23.

J. H. Kwak and J. Lee, Enumeration of connected graph coverings, J. Graph Th., 23 (1996), 105-109.

J. H. Kwak and J. Lee, Enumeration of graph coverings and surface branched coverings, Lecture Note Series 1 (2001), Com^2MaC-KOSEF, Korea. See chapter 3.

V. A. Liskovets, Reductive enumeration under mutually orthogonal group actions, Acta Applic. Math., 52 (1998), 91-120.

Index entries for linear recurrences with constant coefficients, signature (11,-36,36).

Formula

G.f.: x(1-4x)/((1-2x)(1-3x)(1-6x)). a(n) = 6^(n-1)+3^(n-1)-2^(n-1).

E.g.f.: e^(6*x)+e^(3*x)-e^(2*x). [Mohammad K. Azarian, Jan 16 2009]

a(1)=1, a(2)=7, a(3)=41, a(n) = 11*a(n-1)-36*a(n-2)+36*a(n-3). [Harvey P. Dale, Nov 24 2011]

Mathematica

Table[6^(n-1)+3^(n-1)-2^(n-1), {n, 25}] (* or *) LinearRecurrence[ {11, -36, 36}, {1, 7, 41}, 25] (* Harvey P. Dale, Nov 24 2011 *)
CoefficientList[Series[(1 - 4 x)/((1 - 2 x) (1 - 3 x) (1 - 6 x)), {x, 0, 33}], x] (* Vincenzo Librandi, May 12 2015 *)

Prog

(PARI) a(n)=if(n<0, 0, 6^(n-1)+3^(n-1)-2^(n-1))
(Magma) [6^(n-1)+3^(n-1)-2^(n-1): n in [1..30]] /* or */ I:=[1, 7, 41]; [n le 3 select I[n] else 11*Self(n-1)-36*Self(n-2)+36*Self(n-3): n in [1..30]]; // Vincenzo Librandi, May 12 2015

Crossrefs

Cf. A057004, A057005, A057006, A057007, A057008, A057010, A057011, A057012, A057013.

Sequence in context: A152268 A026002 A173409 * A140480 A327055 A002315

Adjacent sequences: A057006 A057007 A057008 * A057010 A057011 A057012

Keyword

nonn

Author

N. J. A. Sloane, Sep 09 2000

Extensions

More terms from Francisco Salinas (franciscodesalinas(AT)hotmail.com), Dec 25 2001

Status

approved