A287816 Number of nonary sequences of length n such that no two consecutive terms have distance 1.

1, 9, 65, 471, 3413, 24733, 179233, 1298853, 9412437, 68209395, 494295113, 3582023557, 25957960001, 188110345129, 1363185009337, 9878634630295, 71587804656589, 518777540353453, 3759441118026705, 27243657291488469, 197427447142906157, 1430703538380753875

Offset

0,2

Links

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

Index entries for linear recurrences with constant coefficients, signature (9, -11, -15, 19, 1).

Formula

a(n) = 9*a(n-1) - 11*a(n-2) - 15*a(n-3) + 19*a(n-4) + a(n-5), a(0)=1, a(1)=9, a(2)=65, a(3)=471, a(4)=3413.

G.f: (-1 + 5 x^2 - 5 x^4)/(-1 + 9 x - 11 x^2 - 15 x^3 + 19 x^4 + x^5).

Example

For n=2 the a(2) = 81 - 16 = 65 sequences contain every combination except these sixteen: 01,10,12,21,23,32,34,43,45,54,56,65,67,76,78,87.

Mathematica

LinearRecurrence[{9, -11, -15, 19, 1}, {1, 9, 65 , 471, 3413}, 40]

Prog

(Python)
def a(n):
.if n in [0, 1, 2, 3, 4]:
..return [1, 9, 65 , 471, 3413][n]
.return 9*a(n-1)-11*a(n-2)-15*a(n-3)+19*a(n-4)+a(n-5)

Crossrefs

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

Sequence in context: A127534 A037548 A238275 * A036731 A020234 A154996

Adjacent sequences: A287813 A287814 A287815 * A287817 A287818 A287819

Keyword

nonn,easy

Author

David Nacin, Jun 02 2017

Status

approved