login
A084085
Length of lists created by n substitutions k -> Range[0,Mod[k+1,4]] starting with {0}.
1
1, 2, 5, 14, 38, 102, 273, 731, 1958, 5245, 14050, 37636, 100816, 270057, 723405, 1937794, 5190793, 13904642, 37246538, 99772766, 267262553, 715919535, 1917742590, 5137081001, 13760762966, 36861127432, 98740361920, 264497039329
OFFSET
0,2
COMMENTS
Equivalent to replacements 0 -> {0,1}; 1 -> {0,1,2}; 2 -> {0,1,2,3}; 3 -> {0} operating n times with {0}.
FORMULA
G.f.: (1-x+x^3)/(1-3*x+x^2-x^4).
EXAMPLE
{0}, {0,1}, {0,1,0,1,2}, {0,1,0,1,2,0,1,0,1,2,0,1,2,3} have lengths 1, 2, 5, 14.
MATHEMATICA
Length/@Flatten/@NestList[ # /. k_Integer:>Range[0, Mod[k+1, 4]]&, {0}, 8]
LinearRecurrence[{3, -1, 0, 1}, {1, 2, 5, 14}, 41] (* G. C. Greubel, Oct 15 2022 *)
PROG
(Magma) I:=[1, 2, 5, 14]; [n le 4 select I[n] else 3*Self(n-1) -Self(n-2) +Self(n-4): n in [1..41]]; // G. C. Greubel, Oct 15 2022
(SageMath)
def A084085_list(prec):
P.<x> = PowerSeriesRing(ZZ, prec)
return P( (1-x+x^3)/(1-3*x+x^2-x^4) ).list()
A084085_list(40) # G. C. Greubel, Oct 15 2022
CROSSREFS
Cf. A084086.
Sequence in context: A228952 A172259 A292327 * A052985 A052945 A026288
KEYWORD
nonn,easy
AUTHOR
Wouter Meeussen, May 11 2003
STATUS
approved