|
%I #15 Sep 08 2022 08:44:50
%S 1,2,7,18,49,136,377,1044,2891,8006,22171,61398,170029,470860,1303949,
%T 3611016,9999959,27692810,76689487,212375610,588130153,1628704336,
%U 4510358465,12490501212,34589849507,95789405774,265268869027
%N Cycle-path coverings of a family of digraphs.
%H G. C. Greubel, <a href="/A030236/b030236.txt">Table of n, a(n) for n = 0..1000</a>
%H O. M. D'Antona and E. Munarini, <a href="https://doi.org/10.1006/aama.2000.0689">The Cycle-path Indicator Polynomial of a Digraph</a>, Advances in Applied Mathematics 25 (2000), 41-56.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,-1,1).
%F a(n+4) = 3*a(n+3) - a(n+2) + a(n+1), n >= 0.
%F a(n+3) = 2*a(n+2) + a(n+1) + 2*Sum_{k=0..n} a(k), n >= 0.
%F G.f.: (1-x+2*x^2-2*x^3)/(1-3*x+x^2-x^3).
%F a(n) = Sum_{k=0..n} binomial(n+k+1,3*k+1)*2^k + 2*Sum_{j=0..n-1} binomial(n+j-1,3*j+1)*2^j. - _Emanuele Munarini_, Dec 03 2012
%p seq(coeff(series((1-x+2*x^2-2*x^3)/(1-3*x+x^2-x^3), x, n+1), x, n), n = 0 .. 40); # _G. C. Greubel_, Oct 27 2019
%t LinearRecurrence[{3,-1,1}, {1,2,7,18}, 40] (* _G. C. Greubel_, Oct 27 2019 *)
%o (Maxima) makelist(sum(binomial(n+k+1,3*k+1)*2^k, k,0,n) + 2*sum(2^k* binomial(n+k-1,3*k+1), k,0,n-1), n,0,60); /* _Emanuele Munarini_, Dec 03 2012 */
%o (PARI) my(x='x+O('x^40)); Vec((1-x+2*x^2-2*x^3)/(1-3*x+x^2-x^3)) \\ _G. C. Greubel_, Oct 27 2019
%o (Magma) R<x>:=PowerSeriesRing(Integers(), 40); Coefficients(R!( (1-x+2*x^2-2*x^3)/(1-3*x+x^2-x^3) )); // _G. C. Greubel_, Oct 27 2019
%o (Sage)
%o def A030236_list(prec):
%o P.<x> = PowerSeriesRing(ZZ, prec)
%o return P( (1-x+2*x^2-2*x^3)/(1-3*x+x^2-x^3) ).list()
%o A030236_list(40) # _G. C. Greubel_, Oct 27 2019
%o (GAP) a:=[2,7,18];; for n in [4..40] do a[n]:=3*a[n-1]-a[n-2]+a[n-3]; od; Concatenation([1],a); # _G. C. Greubel_, Oct 27 2019
%Y Cf. A030186.
%K nonn,easy
%O 0,2
%A Ottavio D'Antona (dantona(AT)dsi.unimi.it) and _Emanuele Munarini_
|
