A109499 Number of closed walks of length n on the complete graph on 5 nodes from a given node.

1, 0, 4, 12, 52, 204, 820, 3276, 13108, 52428, 209716, 838860, 3355444, 13421772, 53687092, 214748364, 858993460, 3435973836, 13743895348, 54975581388, 219902325556, 879609302220, 3518437208884, 14073748835532

Offset

0,3

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Ji Young Choi, A Generalization of Collatz Functions and Jacobsthal Numbers, J. Int. Seq., Vol. 21 (2018), Article 18.5.4.

Index entries for linear recurrences with constant coefficients, signature (3,4).

Formula

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

a(n) = (4^n + 4*(-1)^n)/5.

a(n+1) = 4*A015521(n). - Paul Curtz, Nov 01 2009

a(n) = 3*a(n-1) + 4*a(n-1). - G. C. Greubel, Dec 30 2017

a(n) = A108020((n - 1) / 2) = 'ccc...c' (n digits) in base 16, for odd n. - Georg Fischer, Mar 23 2019

E.g.f.: (exp(4*x) + 4*exp(-x))/5. - G. C. Greubel, Mar 23 2019

Mathematica

CoefficientList[Series[(1-3*x)/(1-3*x-4*x^2), {x, 0, 30}], x] (* or *) LinearRecurrence[{3, 4}, {1, 0}, 30] (* G. C. Greubel, Dec 30 2017 *)

Prog

(Magma) [(4^n + 4*(-1)^n)/5: n in [0..30]]; // Vincenzo Librandi, Aug 12 2011
(PARI) a(n)=(4^n+4*(-1)^n)/5 \\ Charles R Greathouse IV, Oct 01 2012
(Sage) [(4^n+4*(-1)^n)/5 for n in (0..30)] # G. C. Greubel, Mar 23 2019
(GAP) a:=[1, 0];; for n in [3..30] do a[n]:=3*a[n-1]+4*a[n-2]; od; a; # G. C. Greubel, Mar 23 2019

Crossrefs

Cf. A108020 (bisection), A109502.

Cf. A001045, A078008, A097073, A115341, A015518, A054878, A015521 (forms k=4^n-k). - Vladimir Joseph Stephan Orlovsky, Dec 11 2008

Sequence in context: A149411 A149412 A259274 * A282587 A188230 A124006

Adjacent sequences: A109496 A109497 A109498 * A109500 A109501 A109502

Keyword

nonn,easy,walk

Author

Mitch Harris, Jun 30 2005

Extensions

Corrected by Franklin T. Adams-Watters, Sep 18 2006

Status

approved