A181626 Number of closed walks of length n in a kite graph (K4 with one edge deleted).

4, 0, 10, 12, 50, 100, 298, 700, 1890, 4692, 12250, 31020, 80018, 204100, 524170, 1340572, 3437250, 8799540, 22548538, 57746700, 147940850, 378927652, 970691050, 2486401660, 6369165858, 16314772500, 41791435930, 107050525932, 274216269650, 702418373380, 1799283451978

Offset

1,1

Comments

This is trace of A^n where A is adjacency matrix of the kite graph (K4 with one edge deleted).

References

Godsil, Algebraic Combinatorics, Chapman & Hall, Inc, 1993, pages 22-23

Links

Colin Barker, Table of n, a(n) for n = 1..1000

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

Formula

Generating function in terms of characteristic polynomial from Godsil (1993) is 2*x*(2 - 5*x^2 - 2*x^3) / ((1 + x)*(1 - x - 4*x^2)).

From Colin Barker, Dec 25 2017: (Start)

a(n) = 2^(-3-n) * ((-1)^(1+n)*2^(3+n) - (1-sqrt(17))^n*(1+sqrt(17)) + (-1+sqrt(17))*(1+sqrt(17))^n) for n>1.

a(n) = 5*a(n-2) + 4*a(n-3) for n>4.

(End)

Mathematica

Series[2*x*(2 - 5*x^2 - 2*x^3) / ((1 + x)*(1 - x - 4*x^2)), {x, 0, 20}][[3]]

Prog

(PARI) Vec(2*x*(2 - 5*x^2 - 2*x^3) / ((1 + x)*(1 - x - 4*x^2)) + O(x^40)) \\ Colin Barker, Dec 25 2017

Crossrefs

Sequence in context: A345057 A158976 A211243 * A279432 A019127 A019207

Adjacent sequences: A181623 A181624 A181625 * A181627 A181628 A181629

Keyword

easy,nonn

Author

Yaroslav Bulatov (yaroslavvb(AT)gmail.com), Nov 02 2010

Status

approved