A091001 Number of walks of length n between adjacent nodes on the Petersen graph.

0, 1, 0, 5, 4, 33, 56, 253, 588, 2105, 5632, 18261, 52052, 161617, 473928, 1443629, 4287196, 12948969, 38672144, 116365957, 348398820, 1046594561, 3136987480, 9416554845, 28238479724, 84737808793, 254168687136, 762595539893

Offset: 0

Author

Paul Barry, Dec 12 2003

Keywords

• easy
• nonn

References

• N. Biggs, Algebraic Graph Theory, Cambridge, 2nd. Ed., 1993, p. 20.
• F. Harary, Graph Theory, Addison-Wesley, 1969, p. 89.

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+3)+5)/30); # G. C. Greubel, Feb 01 2019

Magma

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

Mathematica

Table[(3^(n+1)+(-2)^(n+3)+5)/30, {n,0,30}] (* or *) LinearRecurrence[{2, 5,-6}, {0,1,0}, 30] (* G. C. Greubel, Feb 01 2019 *)

PARI

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

Sage

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

Formula

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

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

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

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

a(n) = A091002(n+1) - 2*A091002(n). - R. J. Mathar, Oct 30 2014

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