|
%I #21 Oct 17 2022 07:05:04
%S 1,3,9,28,86,265,816,2513,7739,23833,73396,226030,696081,2143648,
%T 6601569,20330163,62608681,192809420,593775046,1828587033,5631308624,
%U 17342153393,53406819691,164471408185,506505428836,1559831901918
%N Length of lists created by n substitutions k -> Range[0,1+Mod[k+1,3]] starting with {0}.
%C Transformation invert T109 gave a match with A078039; T100 binomial gave a match with A012781; equivalent to replacements 0 -> {0,1,2}; 1 -> {0,1,2,3}; 2 -> {0,1}, 3 -> {0,1,2} operating n times with {0}.
%H G. C. Greubel, <a href="/A084084/b084084.txt">Table of n, a(n) for n = 0..1000</a>
%H Tomislav Doslic and I. Zubac, <a href="http://amc-journal.eu/index.php/amc/article/view/851">Counting maximal matchings in linear polymers</a>, Ars Mathematica Contemporanea 11 (2016) 255-276.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,3,1).
%F G.f.: (1+x)/(1-2*x-3*x^2-x^3).
%F a(n) = A000931(4*n + 6). - _Michael Somos_, Sep 18 2012
%e {0}, {0,1,2}, {0,1,2,0,1,2,3,0,1}, {0,1,2,0,1,2,3,0,1,0,1,2,0,1,2,3,0,1,0,1,2,0,1,2,0,1,2,3} have lengths 1, 3, 9, 28.
%e G.f. = 1 + 3*x + 9*x^2 + 28*x^3 + 86*x^4 + 265*x^5 + 816*x^6 + ...
%t Length/@Flatten/@NestList[ # /. k_Integer:>Range[0, 1+Mod[k+1, 3]]&, {0}, 8]
%t LinearRecurrence[{2,3,1}, {1,3,9}, 41] (* _G. C. Greubel_, Oct 16 2022 *)
%o (Magma) [n le 3 select 3^(n-1) else 2*Self(n-1) +3*Self(n-2) +Self(n-3): n in [1..41]]; // _G. C. Greubel_, Oct 16 2022
%o (SageMath)
%o def A084084_list(prec):
%o P.<x> = PowerSeriesRing(ZZ, prec)
%o return P( (1+x)/(1-2*x-3*x^2-x^3) ).list()
%o A084084_list(40) # _G. C. Greubel_, Oct 16 2022
%Y Cf. A000931, A078039, A012781.
%K nonn
%O 0,2
%A _Wouter Meeussen_, May 11 2003
|
