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

1, 4, 16, 64, 252, 996, 3936, 15552, 61452, 242820, 959472, 3791232, 14980572, 59193828, 233896896, 924213888, 3651913836, 14430073860, 57018604752, 225301777344, 890251367868, 3517715249892, 13899805185312, 54923315409216, 217022507533260, 857536884383364, 3388448121977520, 13389022541682432, 52905022644129948, 209047479923369700

Offset

0,2

Comments

G.f. for number of ways to spin a dreidel n times without having a run of length 4 of any of gimel, heh, nun or shin.

More generally, fix an alphabet of size M and consider the number of words of length n which do not contain M consecutive equal letters. The present sequence is the case M = 4.

For the cases M=2 through 5 see A040000, A121907, A188714, A188680.

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

J. Noonan and D. Zeilberger, The Goulden-Jackson cluster method: extensions, applications and implementations

Doron Zeilberger, Webpage of the paper `The Goulden-Jacskon Cluster Method: Extensions, Applications and Implementations', by John Noonan and Doron Zeilberger; Local copy, pdf file only, no active links

Index entries for linear recurrences with constant coefficients, signature (3, 3, 3).

Maple

# First download the Maple package DAVID_IAN from the Zeilberger web site
read(DAVID_IAN);
M:=4;
lis1:={}; for i from 1 to M do lis1:={op(lis1), x[i]}; od:
lis2:={}; for i from 1 to M do t1:=[]; for j from 1 to M do t1:=[op(t1), x[i]]; od: lis2:={op(lis2), t1}; od:
GJs(lis1, lis2, x);

Mathematica

CoefficientList[Series[(1+x+x^2+x^3)/(1-3x-3x^2-3x^3), {x, 0, 30}], x]  (* Harvey P. Dale, Apr 16 2011 *)

Crossrefs

Cf. A040000, A121907, A188680. Column 4 of A265624.

Sequence in context: A370143 A269771 A228980 * A005755 A269651 A077821

Adjacent sequences: A188711 A188712 A188713 * A188715 A188716 A188717

Keyword

nonn

Author

N. J. A. Sloane, Apr 08 2011

Status

approved