A181626 - OEIS

%I #7 Dec 25 2017 11:22:41

%S 4,0,10,12,50,100,298,700,1890,4692,12250,31020,80018,204100,524170,

%T 1340572,3437250,8799540,22548538,57746700,147940850,378927652,

%U 970691050,2486401660,6369165858,16314772500,41791435930,107050525932,274216269650,702418373380,1799283451978

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

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

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

%H Colin Barker, <a href="/A181626/b181626.txt">Table of n, a(n) for n = 1..1000</a>

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (0,5,4).

%F 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)).

%F From _Colin Barker_, Dec 25 2017: (Start)

%F 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.

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

%F (End)

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

%o (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

%K easy,nonn

%O 1,1

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