A254598 Numbers of n-length words on alphabet {0,1,...,8} with no subwords ii, for i from {0,1}.

1, 9, 79, 695, 6113, 53769, 472943, 4159927, 36590017, 321839625, 2830847119, 24899654327, 219013164449, 1926402895881, 16944315318191, 149039342816695, 1310924949760897, 11530674997804041, 101421874630758607, 892089722030697143, 7846670898660887393, 69017995243501979145

Offset: 0

Author

Milan Janjic, Feb 02 2015

Keywords

• nonn
• easy

Comments

Is this essentially A251366? - Bruno Berselli, Feb 02 2015

Yes, it is: see proof at A251366. - Robert Israel, Mar 19 2018

a(n) is the number of nonary sequences of length n such that no two consecutive terms have distance 8. - David Nacin, May 31 2017

Links

• Colin Barker, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (8,7).

Crossrefs

Cf. A015576, A251366.

Programs

Maple

f:= gfun:-rectoproc({a(n) = 8*a(n-1) + 7*a(n-2), a(0)=1, a(1)=9},a(n), remember):
map(f, [$0..30]); # Robert Israel, Mar 19 2018

Mathematica

RecurrenceTable[{a[0] == 1, a[1] == 9, a[n] == 8 a[n - 1] + 7 a[n - 2]}, a[n], {n, 0, 25}] (* Bruno Berselli, Feb 03 2015 *)
LinearRecurrence[{8,7},{1,9},30] (* Harvey P. Dale, Oct 14 2017 *)

PARI

Vec(-(x+1)/(7*x^2+8*x-1) + O(x^100)) \\ Colin Barker, Feb 02 2015

Formula

a(n) = 8*a(n-1) + 7*a(n-2) with n>1, a(0) = 1, a(1) = 9.

G.f.: -(x+1) / (7*x^2 + 8*x - 1). - Colin Barker, Feb 02 2015

a(n) = (((4-sqrt(23))^n * (-5+sqrt(23)) + (4+sqrt(23))^n * (5+sqrt(23)))) / (2*sqrt(23)). - Colin Barker, Sep 08 2016

a(n) = A015576(n) + A015576(n+1). - R. J. Mathar, Feb 13 2020