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

Author

N. J. A. Sloane, Apr 08 2011

Keywords

• nonn

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).

Crossrefs

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

Programs

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 *)