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,4

Comments

Binomial transform of A091005.

The n-fold homomorphic graph product ( ... ((K3 X (K3 X ... (K3 X (K3 X K3)) ... ) represents a regular graph with 3^(n+1) vertices. 2 * a(n+1) is the degree of regularity for this graph. - Helmut Ruhland, Oct 29 2025

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).

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

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 *)

Prog

(SageMath) 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
(SageMath) [(3^(n+1) - (-2)^(n+1) - 5)/30 for n in range(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
(Magma) [(3^(n+1) - (-2)^(n+1) - 5)/30: n in [0..30]]; // G. C. Greubel, Feb 01 2019
(GAP) List([0..30], n -> (3^(n+1) - (-2)^(n+1) - 5)/30); # G. C. Greubel, Feb 01 2019

Crossrefs

Sequence in context: A026589 A319792 A383499 * A389293 A330419 A025176

Adjacent sequences: A090999 A091000 A091001 * A091003 A091004 A091005

Keyword

easy,nonn

Author

Paul Barry, Dec 12 2003

Status

approved