A063759 Spherical growth series for modular group.

1, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128, 192, 256, 384, 512, 768, 1024, 1536, 2048, 3072, 4096, 6144, 8192, 12288, 16384, 24576, 32768, 49152, 65536, 98304, 131072, 196608, 262144, 393216, 524288, 786432, 1048576, 1572864, 2097152

Offset: 0

Author

N. J. A. Sloane, Aug 14 2001

Keywords

• nonn
• nice
• easy

Comments

Also number of sequences S of length n with entries in {1,..,q} where q = 3, satisfying the condition that adjacent terms differ in absolute value by exactly 1, see examples. - W. Edwin Clark, Oct 17 2008

Examples

			For n = 2 the a(2) = 4 sequences are (1,2),(2,1),(2,3),(3,2). - _W. Edwin Clark_, Oct 17 2008
From _Joerg Arndt_, Nov 23 2012: (Start)
There are a(6) = 16 such words of length 6:
[ 1]   [ 1 2 1 2 1 2 ]
[ 2]   [ 1 2 1 2 3 2 ]
[ 3]   [ 1 2 3 2 1 2 ]
[ 4]   [ 1 2 3 2 3 2 ]
[ 5]   [ 2 1 2 1 2 1 ]
[ 6]   [ 2 1 2 1 2 3 ]
[ 7]   [ 2 1 2 3 2 1 ]
[ 8]   [ 2 1 2 3 2 3 ]
[ 9]   [ 2 3 2 1 2 1 ]
[10]   [ 2 3 2 1 2 3 ]
[11]   [ 2 3 2 3 2 1 ]
[12]   [ 2 3 2 3 2 3 ]
[13]   [ 3 2 1 2 1 2 ]
[14]   [ 3 2 1 2 3 2 ]
[15]   [ 3 2 3 2 1 2 ]
[16]   [ 3 2 3 2 3 2 ]
(End)
		

References

• P. de la Harpe, Topics in Geometric Group Theory, Univ. Chicago Press, 2000, p. 156.

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
• Index entries for sequences related to modular groups
• Index entries for linear recurrences with constant coefficients, signature (0,2)

Crossrefs

Cf. A054886, A029744.

The sequence (ternary strings) seems to be related to A029744 and A090989.

Programs

Haskell

import Data.List (transpose)
a063759 n = a063759_list !! n
a063759_list = concat $ transpose [a151821_list, a007283_list]
-- Reinhard Zumkeller, Dec 16 2013

Mathematica

CoefficientList[Series[(1+3*x+2*x^2)/(1-2*x^2),{x,0,40}],x](* Jean-François Alcover, Mar 21 2011 *)
Join[{1},Transpose[NestList[{Last[#],2First[#]}&,{3,4},40]][[1]]] (* Harvey P. Dale, Oct 22 2011 *)

PARI

a(n)=([0,1; 2,0]^n*[1;3])[1,1] \\ Charles R Greathouse IV, Feb 09 2017

Formula

G.f.: (1+3*x+2*x^2)/(1-2*x^2).

a(n) = 2*a(n-2), n>2. - Harvey P. Dale, Oct 22 2011

a(2*n) = A151821(n+1); a(2*n+1) = A007283(n). - Reinhard Zumkeller, Dec 16 2013

Extensions

Information from A145751 included by Joerg Arndt, Dec 03 2012