A287831 Number of sequences over the alphabet {0,1,...,9} such that no two consecutive terms have distance 8.

1, 10, 96, 924, 8892, 85572, 823500, 7924932, 76265388, 733938084, 7063035084, 67970944260, 654116708844, 6294876045156, 60578584659468, 582976518206148, 5610260171812140, 53990200655546148, 519573366930788172, 5000101506310370436, 48118353758378062956

Offset

0,2

Comments

In general, the number of sequences over the alphabet {0,1,...,9} such that no two consecutive terms have distance 5+k for k in {0,1,2,3,4} is given by a(n) = 9*a(n-1) + 2*k*a(n-2), a(0)=1, a(1)=10.

Links

Table of n, a(n) for n=0..20.

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

Formula

a(n) = 9*a(n-1) + 6*a(n-2), a(0)=1, a(1)=10.

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

a(n) = ((1 - 11/sqrt(105))/2)*((9 - sqrt(105))/2)^n + ((1 + 11/sqrt(105))/2)*((9 + sqrt(105))/2)^n.

Mathematica

LinearRecurrence[{9, 6}, {1, 10}, 30]

Prog

(Python)
def a(n):
.if n in [0, 1]:
..return [1, 10][n]
.return 9*a(n-1)+6*a(n-2)

Crossrefs

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

Sequence in context: A125945 A259497 A190986 * A288430 A209262 A308523

Adjacent sequences: A287828 A287829 A287830 * A287832 A287833 A287834

Keyword

nonn,easy

Author

David Nacin, Jun 02 2017

Status

approved