login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A030236
Cycle-path coverings of a family of digraphs.
2
1, 2, 7, 18, 49, 136, 377, 1044, 2891, 8006, 22171, 61398, 170029, 470860, 1303949, 3611016, 9999959, 27692810, 76689487, 212375610, 588130153, 1628704336, 4510358465, 12490501212, 34589849507, 95789405774, 265268869027
OFFSET
0,2
LINKS
O. M. D'Antona and E. Munarini, The Cycle-path Indicator Polynomial of a Digraph, Advances in Applied Mathematics 25 (2000), 41-56.
FORMULA
a(n+4) = 3*a(n+3) - a(n+2) + a(n+1), n >= 0.
a(n+3) = 2*a(n+2) + a(n+1) + 2*Sum_{k=0..n} a(k), n >= 0.
G.f.: (1-x+2*x^2-2*x^3)/(1-3*x+x^2-x^3).
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
MAPLE
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
MATHEMATICA
LinearRecurrence[{3, -1, 1}, {1, 2, 7, 18}, 40] (* G. C. Greubel, Oct 27 2019 *)
PROG
(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 */
(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
(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
(Sage)
def A030236_list(prec):
P.<x> = PowerSeriesRing(ZZ, prec)
return P( (1-x+2*x^2-2*x^3)/(1-3*x+x^2-x^3) ).list()
A030236_list(40) # G. C. Greubel, Oct 27 2019
(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
CROSSREFS
Cf. A030186.
Sequence in context: A022726 A192873 A017925 * A074141 A122931 A094976
KEYWORD
nonn,easy
AUTHOR
Ottavio D'Antona (dantona(AT)dsi.unimi.it) and Emanuele Munarini
STATUS
approved