A193653 - OEIS

%I #36 Sep 08 2022 08:45:58

%S 1,2,6,20,70,248,882,3140,11182,39824,141834,505148,1799110,6407624,

%T 22821090,81278516,289477726,1030990208,3671926074,13077758636,

%U 46577128054,165886901432,590814960402,2104218684068,7494285973006,26691295287152,95062457807466

%N Q-residue of the Delannoy triangle A008288, where Q is the triangular array (t(i,j)) given by t(i,j)=1.

%C For the definition of Q-residue, see A193649.

%C This sequence gives the number of closed walks from the two vertices having loops in the digraph defined by its adjacency matrix A = (2,1,1; 1,2,1; 1,1,0). - _David Neil McGrath_, Aug 22 2014

%H Colin Barker, <a href="/A193653/b193653.txt">Table of n, a(n) for n = 0..1000</a>

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

%F From _David Neil McGrath_, Aug 22 2014: (Start)

%F a(n) = 4*a(n-1) - a(n-2) - 2*a(n-3).

%F a(n-1) = (1,1) and (2,2) elements of A^(n-1) where A=(2,1,1; 1,2,1; 1,1,0) and n>1. (End)

%F G.f.: (1-2*t-t^2)/(1-4*t+t^2+2*t^3). - _Robert Israel_, Aug 22 2014

%F a(n) = (34 + (17-3*sqrt(17))*((3-sqrt(17))/2)^n + ((3+sqrt(17))/2)^n*(17+3*sqrt(17)))/68. - _Colin Barker_, Sep 02 2016

%F From _G. C. Greubel_, May 25 2021: (Start)

%F a(n) = (1/2)*(1 + (i*sqrt(2))^n * ChebyshevU(n, -3*i/(2*sqrt(2)))).

%F a(n) = (1/2)*( 1 + Sum_{j=0..floor(n/2)} binomial(n-k,k)*2^k*3^(n-2*k) ). (End)

%t (* First program *)

%t q[n_, k_] := 1;

%t r[0] = 1; r[k_]:= Sum[q[k-1, i]*r[k-1-i], {i, 0, k-1}]

%t p[n_, k_]:= p[n, k]= If[k==0 || k==n, 1, p[n-1, k-1] + p[n-2, k-1] + p[n-1, k]];  (* A008288, Delannoy *)

%t v[n_]:= Sum[p[n, k]*r[n-k], {k, 0, n}];

%t Table[v[n], {n, 0, 16}]    (* A193653 *)

%t TableForm[Table[q[i, k], {i, 0, 4}, {k, 0, i}]]

%t Table[r[k], {k, 0, 8}]  (* 2^k *)

%t TableForm[Table[p[n, k], {n, 0, 4}, {k, 0, n}]]

%t (* Second program *)

%t LinearRecurrence[{4,-1,-2}, {1,2,6}, 40] (* _G. C. Greubel_, May 25 2021 *)

%o (PARI) Vec((1-2*t-t^2)/(1-4*t+t^2+2*t^3) + O(t^40)) \\ _Michel Marcus_, Aug 23 2014

%o (PARI) a(n) = round((34+(17-3*sqrt(17))*((3-sqrt(17))/2)^n+((3+sqrt(17))/2)^n*(17+3*sqrt(17)))/68) \\ _Colin Barker_, Sep 02 2016

%o (Magma) [n le 3 select Factorial(n) else 4*Self(n-1) -Self(n-2) -2*Self(n-3): n in [1..41]]; // _G. C. Greubel_, May 25 2021

%o (Sage) [(1/2)*(1 + sum(binomial(n-k,k)*2^k*3^(n-2*k) for k in (0..n//2))) for n in (0..40)] # _G. C. Greubel_, May 25 2021

%Y Cf. A008288, A193649.

%K nonn,easy

%O 0,2

%A _Clark Kimberling_, Aug 02 2011