A254657 Numbers of words on alphabet {0,1,...,8} with no subwords ii, where i is from {0,1,2}.

1, 9, 78, 678, 5892, 51204, 444984, 3867096, 33606672, 292055952, 2538087648, 22057036896, 191684821056, 1665820789824, 14476675244928, 125808326698368, 1093326665056512, 9501463280642304, 82571666235477504, 717582109567673856, 6236086873954255872

Offset

0,2

Links

Colin Barker, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (8,6).

Formula

G.f.: (1 + x)/(1 - 8*x - 6*x^2).

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

a(n) = (((4-sqrt(22))^n*(-5+sqrt(22)) + (4+sqrt(22))^n*(5+sqrt(22))))/(2*sqrt(22)). - Colin Barker, Nov 16 2016

Mathematica

RecurrenceTable[{a[0] == 1, a[1] == 9, a[n] == 8 a[n - 1] + 6 a[n - 2]}, a[n], {n, 0, 20}]

Prog

(Magma) [n le 1 select 9^n else 8*Self(n)+6*Self(n-1): n in [0..20]];
(PARI) Vec((1+x)/(1-8*x-6*x^2) + O(x^30)) \\ Colin Barker, Nov 16 2016

Crossrefs

Cf. A055099, A126473, A126501, A126528, A190560, A254598, A254602.

Sequence in context: A231596 A350428 A190980 * A231590 A240797 A279683

Adjacent sequences: A254654 A254655 A254656 * A254658 A254659 A254660

Keyword

nonn,easy

Author

Milan Janjic, Feb 04 2015

Status

approved