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

1, 10, 86, 742, 6404, 55274, 477082, 4117804, 35541714, 306768722, 2647791524, 22853698754, 197255539962, 1702558017644, 14695170558994, 126837403201602, 1094762853302164, 9449150445514434, 81557794797885642, 703944119701429084, 6075903902137709074

Offset

0,2

Links

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

Index entries for linear recurrences with constant coefficients, signature (9, -1, -20, 10).

Formula

For n>4, a(n) = 9*a(n-1) - a(n-2) - 20*a(n-3) + 10*a(n-4), a(0)=1, a(1)=10, a(2)=86, a(3)=742, a(4)=6404.

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

Mathematica

LinearRecurrence[{9, -1, -20, 10}, {1, 10, 86, 742, 6404}, 30]

Prog

(Python)
def a(n):
.if n in [0, 1, 2, 3, 4]:
..return [1, 10, 86, 742, 6404][n]
.return 9*a(n-1)-a(n-2)-20*a(n-3)+10*a(n-4)

Crossrefs

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

Sequence in context: A184122 A228123 A163412 * A321853 A264174 A218894

Adjacent sequences: A287824 A287825 A287826 * A287828 A287829 A287830

Keyword

nonn,easy

Author

David Nacin, Jun 02 2017

Status

approved