A091002 Number of walks of length n between non-adjacent nodes on the Petersen graph.

0, 0, 1, 2, 9, 22, 77, 210, 673, 1934, 5973, 17578, 53417, 158886, 479389, 1432706, 4309041, 12905278, 38759525, 116191194, 348748345, 1045895510, 3138385581, 9413758642, 28244072129, 84726623982, 254191056757, 762550800650, 2287697141193, 6863001945094

Offset: 0

Author

Paul Barry, Dec 12 2003

Keywords

• easy
• nonn

Comments

Binomial transform of A091005.

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (2,5,-6).

Programs

GAP

List([0..30], n -> (3^(n+1) - (-2)^(n+1) - 5)/30); # G. C. Greubel, Feb 01 2019

Magma

[(3^(n+1) - (-2)^(n+1) - 5)/30: n in [0..30]]; // G. C. Greubel, Feb 01 2019

Maple

a:=n->sum(binomial(n-k, k)*6^(k-1), k=1..n): seq(a(n),n=0..27); # Zerinvary Lajos, Sep 30 2006

Mathematica

Table[(3^n -(-2)^n - 5)/30, {n, 40}] (* Vladimir Joseph Stephan Orlovsky, Jun 20 2011 *)
LinearRecurrence[{2,5,-6}, {0,0,1}, 30] (* G. C. Greubel, Feb 01 2019 *)

PARI

vector(30, n, n--; (3^(n+1) - (-2)^(n+1) - 5)/30) \\ G. C. Greubel, Feb 01 2019

Sage

from sage.combinat.sloane_functions import recur_gen2b; it = recur_gen2b(1,2,1,6, lambda n: 1); [next(it) for i in range(0,29)] # Zerinvary Lajos, Jul 03 2008

Sage

[(3^(n+1) - (-2)^(n+1) - 5)/30 for n in range(30)] # G. C. Greubel, Feb 01 2019

Formula

3^n = A091000(n) + 3*A091001(n) + 6*a(n).

G.f.: x^2/((1-x)*(1+2*x)*(1-3*x)).

a(n) = (3^(n+1) - (-2)^(n+1) - 5)/30.

a(n) = (A000244(n) - A001045(n+1)*(-1)^n + 4*A001045(n)*(-1)^n)/10.

a(n) = Sum_{k=1..n} binomial(n-k, k)*6^(k-1). - Zerinvary Lajos, Sep 30 2006

E.g.f.: (3*exp(3*x) + 2*exp(-2*x) - 5*exp(x))/30. - G. C. Greubel, Feb 01 2019