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

%I #22 Sep 08 2022 08:45:12

%S 0,0,1,2,9,22,77,210,673,1934,5973,17578,53417,158886,479389,1432706,

%T 4309041,12905278,38759525,116191194,348748345,1045895510,3138385581,

%U 9413758642,28244072129,84726623982,254191056757,762550800650,2287697141193,6863001945094

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

%C Binomial transform of A091005.

%H G. C. Greubel, <a href="/A091002/b091002.txt">Table of n, a(n) for n = 0..1000</a>

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,5,-6).

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

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

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

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

%F a(n) = Sum_{k=1..n} binomial(n-k, k)*6^(k-1). - _Zerinvary Lajos_, Sep 30 2006

%F E.g.f.: (3*exp(3*x) + 2*exp(-2*x) - 5*exp(x))/30. - _G. C. Greubel_, Feb 01 2019

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

%t Table[(3^n -(-2)^n - 5)/30, {n, 40}] (* _Vladimir Joseph Stephan Orlovsky_, Jun 20 2011 *)

%t LinearRecurrence[{2,5,-6}, {0,0,1}, 30] (* _G. C. Greubel_, Feb 01 2019 *)

%o (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

%o (Sage) [(3^(n+1) - (-2)^(n+1) - 5)/30 for n in range(30)] # _G. C. Greubel_, Feb 01 2019

%o (PARI) vector(30, n, n--; (3^(n+1) - (-2)^(n+1) - 5)/30) \\ _G. C. Greubel_, Feb 01 2019

%o (Magma) [(3^(n+1) - (-2)^(n+1) - 5)/30: n in [0..30]]; // ~~~

%o (GAP) List([0..30], n -> (3^(n+1) - (-2)^(n+1) - 5)/30) # _G. C. Greubel_, Feb 01 2019

%K easy,nonn

%O 0,4

%A _Paul Barry_, Dec 12 2003