A084085 - OEIS

%I #13 Oct 17 2022 01:51:00

%S 1,2,5,14,38,102,273,731,1958,5245,14050,37636,100816,270057,723405,

%T 1937794,5190793,13904642,37246538,99772766,267262553,715919535,

%U 1917742590,5137081001,13760762966,36861127432,98740361920,264497039329

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

%C Equivalent to replacements 0 -> {0,1}; 1 -> {0,1,2}; 2 -> {0,1,2,3}; 3 -> {0} operating n times with {0}.

%H G. C. Greubel, <a href="/A084085/b084085.txt">Table of n, a(n) for n = 0..1000</a>

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (3,-1,0,1).

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

%e {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.

%t Length/@Flatten/@NestList[ # /. k_Integer:>Range[0, Mod[k+1, 4]]&, {0}, 8]

%t LinearRecurrence[{3,-1,0,1}, {1,2,5,14}, 41] (* _G. C. Greubel_, Oct 15 2022 *)

%o (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

%o (SageMath)

%o def A084085_list(prec):

%o     P.<x> = PowerSeriesRing(ZZ, prec)

%o     return P( (1-x+x^3)/(1-3*x+x^2-x^4) ).list()

%o A084085_list(40) # _G. C. Greubel_, Oct 15 2022

%Y Cf. A084086.

%K nonn,easy

%O 0,2

%A _Wouter Meeussen_, May 11 2003