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

1, 10, 88, 776, 6844, 60364, 532412, 4695892, 41417932, 365307620, 3222026092, 28418383780, 250651147340, 2210751960772, 19498910274028, 171981076403492, 1516879160180620, 13378927697789188, 118002614210453804, 1040787219651555556, 9179779989094951372

Offset

0,2

Links

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

Index entries for linear recurrences with constant coefficients, signature (9, 0, -14).

Formula

For n>3, a(n) = 9*a(n-1) - 14*a(n-3), a(0)=1, a(1)=10, a(2)=88, a(3)=776.

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

Mathematica

LinearRecurrence[{9, 0, -14}, {1, 10, 88, 776}, 30]

Prog

(Python)
def a(n):
.if n in [0, 1, 2, 3]:
..return [1, 10, 88, 776][n]
.return 9*a(n-1)-14*a(n-3)

Crossrefs

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

Sequence in context: A125398 A273585 A165148 * A264320 A298134 A163030

Adjacent sequences: A287825 A287826 A287827 * A287829 A287830 A287831

Keyword

nonn,easy

Author

David Nacin, Jun 02 2017

Status

approved