A198636 One half of total number of round trips, each of length 2n, on the graph P_6 (o-o-o-o-o-o).

3, 5, 13, 38, 117, 370, 1186, 3827, 12389, 40169, 130338, 423065, 1373466, 4459278, 14478659, 47011093, 152642789, 495626046, 1609284589, 5225309458, 16966465802, 55089756851, 178875298901, 580804419201, 1885860059450, 6123349080945

Offset

0,1

Comments

See the array and triangle A198632 for the general graph P_N case (there N is n and the length is l=2*k).

Links

M. F. Hasler, Table of n, a(n) for n = 0..499

S. Barbero, Dickson Polynomials, Chebyshev Polynomials, and Some Conjectures of Jeffery, Journal of Integer Sequences, 17 (2014), #14.3.8.

S. Barbero, U. Cerruti, N. Murru, Identities Involving Zeros of Ramanujan and Shanks Cubic Polynomials, J. Integer Seq., Vol. 16 (2013), Article 13.8.1, pp. 10-12.

Index entries for linear recurrences with constant coefficients, signature (5,-6,1).

Formula

a(n) = w(6,2*n)/2, n>=0, with w(6,l) the total number of closed walks on the graph P_6 (the simple path with 6 points (vertices) and 5 lines (or edges)).

O.g.f. for w(6,l) (with zeros for odd l): y*(d/dy)S(6,y)/S(6,y) with y=1/x and Chebyshev S-polynomials (coefficients A049310). See also A198632 for a rewritten form.

O.g.f.: (3-10*x+6*x^2)/(1-5*x+6*x^2-x^3). - Colin Barker, Jan 02 2012

Conjecture: a(n) = 2^(2*n)*(sum_{k=1,2,3} (cos(k*Pi/7))^(2*n)). - L. Edson Jeffery, Jan 21 2012 (in fact this conjecture was recently proved in [Barbero, et al.])

a(n) = 7*(binomial(2n-1,n-1) + sum_{k = 1..floor(n/7)} binomial(2n,n-7k)) - 2^(2n-1). - M. Lawrence Glasser, Feb 20 2013

Let r,s,t be the roots of x^3 + x^2 - 2x - 1; then apparently a(n) = r^(2n) + s^(2n) + t^(2n). - James R. Buddenhagen, Nov 03 2013 [This is equivalent to the conjecture by L. Edson Jeffery.]

a(n) = 5*a(n-1) - 6*a(n-2) + a(n-3). - M. F. Hasler, Nov 05 2013

G.f.: F(x) = (sum_{r=0..2} ((3-r)*(-1)^r*binomial(6-r,r))*x^r)/(sum_{s=0..3} ((-1)^s*binomial(6-s,s))*x^s). - L. Edson Jeffery, Nov 23 2013

Example

With the graph P_6 as 1-2-3-4-5-6:
n=0: a(0)=3 because w(6,0)=6, the number of vertices.
n=2: a(2)=5 because the 10 round trips of length 2 are 121, 212, 232, 323, 343, 434, 454, 545, 565 and 656.

Mathematica

Table[7 (Binomial[2 n - 1, n - 1] + Sum[Binomial[2 n, n - 7 k], {k, Floor[n/7]}]) - 2^(2 n - 1) - (7/2) Boole[n == 0], {n, 0, 25}] (* Michael De Vlieger, Jul 17 2017 *)

Prog

(PARI) vec_A198636(Nmax)=Vec((3-10*x+6*x^2)/(1-5*x+6*x^2-x^3)+O(x^Nmax)) \\ Indices will start at 1 in this vector. - M. F. Hasler, Nov 03 2013
(PARI) {a(n) = if( n<0, n=-n; polcoeff( (3 - 12*x + 5*x^2) / (1 - 6*x + 5*x^2 - x^3) + x * O(x^n), n), polcoeff( (3 - 10*x + 6*x^2) / (1 - 5*x + 6*x^2 -x^3) + x * O(x^n), n))}; /* Michael Somos, Jul 17 2017 */

Crossrefs

Cf. A198632, A198633, A005248, A198635.

Sequence in context: A175257 A190423 A278024 * A172023 A271667 A188583

Adjacent sequences: A198633 A198634 A198635 * A198637 A198638 A198639

Keyword

nonn,easy,walk

Author

Wolfdieter Lang, Nov 03 2011

Status

approved