A084085 Length of lists created by n substitutions k -> Range[0,Mod[k+1,4]] starting with {0}.

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

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

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

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

Adjacent sequences: A084082 A084083 A084084 * A084086 A084087 A084088

Keyword

nonn,easy

Author

Wouter Meeussen, May 11 2003

Status

approved