A287839 Number of words of length n over the alphabet {0,1,...,10} such that no two consecutive terms have distance 9.

1, 11, 117, 1247, 13289, 141619, 1509213, 16083463, 171399121, 1826575451, 19465548357, 207441511727, 2210673955769, 23558830139779, 251063019088173, 2675542001860183, 28512861152219041, 303857405535211691, 3238164083417650197, 34508642672922983807

Offset

0,2

Comments

In general, the number of sequences on {0,1,...,10} such that no two consecutive terms have distance 6+k for k in {0,1,2,3,4} has generating function (-1 - x)/(-1 + 10*x + (2*k+1)*x^2).

Links

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

Index entries for linear recurrences with constant coefficients, signature (10,7).

Formula

For n>2, a(n) = 10*a(n-1) + 7*a(n-2), a(0)=1, a(1)=11, a(2)=117.

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

a(n) = (((5-4*sqrt(2))^n*(-3+2*sqrt(2)) + (3+2*sqrt(2))*(5+4*sqrt(2))^n)) / (4*sqrt(2)). - Colin Barker, Nov 25 2017

Maple

a:=proc(n) option remember; if n=0 then 1 elif n=1 then 11 elif n=2 then 117 else 10*a(n-1)+7*a(n-2); fi; end: seq(a(n), n=0..30); # Wesley Ivan Hurt, Nov 25 2017

Mathematica

LinearRecurrence[{10, 7}, {1, 11, 117}, 20]

Prog

(Python)
def a(n):
.if n in [0, 1, 2]:
..return [1, 11, 117][n]
.return 10*a(n-1) + 7*a(n-2)
(PARI) Vec((1 + x) / (1 - 10*x - 7*x^2) + O(x^30)) \\ Colin Barker, Nov 25 2017

Crossrefs

Cf. A040000, A003945, A083318, A078057, A003946, A126358, A003946, A055099, A003947, A015448, A126473. A287804-A287819. A287825-A287839.

Sequence in context: A271477 A076554 A173616 * A268344 A289344 A240392

Adjacent sequences: A287836 A287837 A287838 * A287840 A287841 A287842

Keyword

nonn,easy

Author

David Nacin, Jun 07 2017

Status

approved