A109498 Number of closed walks of length 2n on the Heawood graph from a given node.

1, 3, 15, 111, 951, 8463, 75975, 683391, 6149751, 55346223, 498112935, 4483010271, 40347080151, 363123696783, 3268113221895, 29413018898751, 264717169892151, 2382454528636143, 21442090756938855

Offset: 0

Author

Mitch Harris, Jun 30 2005

Keywords

• nonn
• easy

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• Wikipedia, Heawood graph
• Index entries for linear recurrences with constant coefficients, signature (11,-18).

Programs

Magma

I:=[1,3]; [n le 2 select I[n] else 11*Self(n-1) - 18*Self(n-2): n in [1..30]]; // G. C. Greubel, Dec 30 2017

Mathematica

CoefficientList[Series[(1 - 8*x)/((9*x - 1)*(2*x - 1)), {x,0,50}], x] (* or *) LinearRecurrence[{11,-18}, {1,3}, 30] (* G. C. Greubel, Dec 30 2017 *)

PARI

x='x+O('x^30); Vec((1 - 8*x)/((9*x - 1)*(2*x - 1))) \\ G. C. Greubel, Dec 30 2017

Formula

O.g.f.: ( 1-8*x ) / ( (9*x-1)*(2*x-1) ).

a(n) = (9^n + 6*2^n)/7.

a(n) = A106133(n) - 8*A016133(n-1).