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

1, 2, 6, 20, 70, 248, 882, 3140, 11182, 39824, 141834, 505148, 1799110, 6407624, 22821090, 81278516, 289477726, 1030990208, 3671926074, 13077758636, 46577128054, 165886901432, 590814960402, 2104218684068, 7494285973006, 26691295287152, 95062457807466

Offset: 0

Author

Clark Kimberling, Aug 02 2011

Keywords

• nonn
• easy

Comments

For the definition of Q-residue, see A193649.

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

Links

• Colin Barker, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (4,-1,-2).

Crossrefs

Cf. A008288, A193649.

Programs

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

Mathematica

(* First program *)
q[n_, k_] := 1;
r[0] = 1; r[k_]:= Sum[q[k-1, i]*r[k-1-i], {i, 0, k-1}]
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 *)
v[n_]:= Sum[p[n, k]*r[n-k], {k, 0, n}];
Table[v[n], {n, 0, 16}]    (* A193653 *)
TableForm[Table[q[i, k], {i, 0, 4}, {k, 0, i}]]
Table[r[k], {k, 0, 8}]  (* 2^k *)
TableForm[Table[p[n, k], {n, 0, 4}, {k, 0, n}]]
(* Second program *)
LinearRecurrence[{4,-1,-2}, {1,2,6}, 40] (* G. C. Greubel, May 25 2021 *)

PARI

Vec((1-2*t-t^2)/(1-4*t+t^2+2*t^3) + O(t^40)) \\ Michel Marcus, Aug 23 2014

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

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

Formula

From David Neil McGrath, Aug 22 2014: (Start)

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

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)

G.f.: (1-2*t-t^2)/(1-4*t+t^2+2*t^3). - Robert Israel, Aug 22 2014

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

From G. C. Greubel, May 25 2021: (Start)

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

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