A115055 Lower level digraph derived from a voltage graph.

0, 1, 0, 0, 1, 3, 3, 2, 6, 15, 21, 24, 42, 86, 138, 192, 305, 546, 906, 1381, 2175, 3651, 6042, 9582, 15225, 24901, 40836, 65748, 105364, 170796, 278184, 450017, 724968, 1172412, 1902321, 3080367, 4975551, 8044478, 13029534, 21096027, 34114553

Offset: 1

Author

Roger L. Bagula, Dec 09 2006

Keywords

• nonn

Comments

Lower level digraph derived from a voltage graph (Gross's covering graph construction) that is a generalized Fibonacci Markov. In matrix terms gives a 6 X 6 Markov with characteristic Polynomial (-1 - x + x^2)*(1 + 2*x + 2*x^2 + x^3 + x^4).

This digraph construction gives a complex substructure to the Fibonacci Pisot that is not Pisot. Gross's covering graph constructions called voltage graphs are abstractions from lower level graphs.

limit_{n to Infinity} (a(n+1)/a(n)) = Golden Mean.

References

• J. L. Gross and T. W. Tucker, Topological Graph Theory, Wiley, 1987; see Figure 2.5 p. 62

Links

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

Programs

GAP

a:=[0,1,0,0,1,3];; for n in [7..50] do a[n]:=a[n-3]+3*a[n-4]+ 3*a[n-5]+a[n-6]; od; a; # G. C. Greubel, Mar 22 2019

Magma

R:=PowerSeriesRing(Integers(), 50); [0] cat Coefficients(R!( x/(1-(x+x^2)^3) )); // G. C. Greubel, Mar 22 2019

Mathematica

(* Gross page 62 voltage group L3 : weights set to one *)
M = {{0, 0, 0, 0, 1, 1}, {1, 0, 0, 0, 0, 0}, {1, 1, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 0}, {0, 0, 1, 1, 0, 0}, {0, 0, 0, 0, 1, 0}} v[1] = {0, 0, 0, 0, 0, 1} v[n_] := v[n] = M.v[n - 1] a = Table[Floor[v[n][[1]]], {n, 1, 50}]
(* alternate program *)
LinearRecurrence[{0,0,1,3,3,1}, {0,1,0,0,1,3}, 50] (* G. C. Greubel, Mar 22 2019 *)

PARI

my(x='x+O('x^50)); concat([0], Vec(x/(1-(x+x^2)^3))) \\ G. C. Greubel, Mar 22 2019

Sage

(x/(1-(x+x^2)^3)).series(x, 50).coefficients(x, sparse=False) # G. C. Greubel, Mar 22 2019

Formula

Let M be the 6x6 matrix given by: M = {{0, 0, 0, 0, 1, 1}, {1, 0, 0, 0, 0, 0}, {1, 1, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 0}, {0, 0, 1, 1, 0, 0}, {0, 0, 0, 0, 1, 0}}, then v(n) = M.v(n-1), where a(n) = v(n)(1).

From Vladimir Kruchinin, Oct 12 2011: (Start)

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

a(n) = Sum_{k=0..n} binomial(3*k,n-3*k). (End)

a(n) = a(n-3) + 3*a(n-4) + 3*a(n-5) + a(n-6). - G. C. Greubel, Mar 22 2019

Extensions

Edited by G. C. Greubel, Mar 22 2019