OFFSET
0,3
COMMENTS
With offset 1, partial sums of A085350. - Paul Barry, Jun 24 2003
Number of walks of length 2n+2 between two nodes at distance 4 in the cycle graph C_12. - Herbert Kociemba, Jul 05 2004
From Enrique Navarrete, Mar 30 2026: (Start)
3*a(n) is the number of strings of length n+1 defined on {0,1,2,3} such that 0 appears at least once and the combined number of 0's and 1's is even.
Equivalently, 3*a(n) is the number of walks of length n on the K_4 graph with loops with set of vertices {0,1,2,3} such that one chosen vertex, say 0, is visited at least once and the total number of times the vertex set {0,1} is visited is even (see Example). (End)
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (8,-19,12).
FORMULA
a(n) = ((4^(n+1) - 1)/3 - 3^n)/2 = (4*4^n - 3*3^n - 1)/6.
G.f.: x*(1-2*x)/((1-x)*(1-3*x)*(1-4*x)).
From Elmo R. Oliveira, Aug 29 2024: (Start)
E.g.f.: exp(x)*(4*exp(3*x) - 3*exp(2*x) - 1)/6.
a(n) = 8*a(n-1) - 19*a(n-2) + 12*a(n-3) for n > 2. (End)
EXAMPLE
For n=3, the following are the sets of vertices in which 0 is visited at least once and the total number of times the vertex set {0,1} is visited is even (number of walks in parentheses, adding to 3*29 = 87): 0000 (1), 0111 (4), 0011 (6), 0001 (4), 0122 (12), 0022 (6), 0133 (12), 0033 (6), 0123 (24), 0023 (12). - Enrique Navarrete, Mar 30 2026
MATHEMATICA
Join[{a=0, b=1}, Table[c=7*b-12*a-1; a=b; b=c, {n, 60}]] (* Vladimir Joseph Stephan Orlovsky, Jan 19 2011 *)
CoefficientList[Series[(x(1-2x))/((1-x)(1-3x)(1-4x)), {x, 0, 30}], x] (* or *) LinearRecurrence[{8, -19, 12}, {0, 1, 6}, 30] (* Harvey P. Dale, Nov 28 2018 *)
PROG
(Magma) [((4^(n+1)-1)/3-3^n)/2: n in [0..30]]; // Vincenzo Librandi, Jul 17 2011
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Paul Barry, Mar 28 2003
STATUS
approved