A287817 Number of nonary sequences of length n such that no two consecutive terms have distance 2.

1, 9, 67, 501, 3747, 28025, 209609, 1567743, 11725731, 87701095, 655949055, 4906086571, 36694443381, 274451368893, 2052723708275, 15353082914309, 114831408642039, 858866749063989, 6423783365292409, 48045861327359751, 359352839194448551, 2687733333725785179

Offset

0,2

Links

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

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

Formula

a(n) = 8*a(n-1) - 1*a(n-2) - 23*a(n-3) + 10*a(n-4) + a(n-5), a(0)=1, a(1)=9, a(2)=67, a(3)=501, a(4)=3747.

G.f: (-1 - x + 4 x^2 + 3 x^3 - 3 x^4)/(-1 + 8 x - x^2 - 23 x^3 + 10 x^4 + x^5).

Example

For n=2 the a(2) = 81 - 14 = 67 sequences contain every combination except these fourteen: 02,20,13,31,24,42,35,53,46,64,57,75,68,86.

Mathematica

LinearRecurrence[{8, -1, -23, 10, 1}, {1, 9, 67 , 501, 3747}, 40]

Prog

(Python)
def a(n):
.if n in [0, 1, 2, 3, 4]:
..return [1, 9, 67 , 501, 3747][n]
.return 8*a(n-1)-a(n-2)-23*a(n-3)+10*a(n-4)+a(n-5)

Crossrefs

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

Sequence in context: A163349 A016130 A115202 * A155592 A002051 A231192

Adjacent sequences: A287814 A287815 A287816 * A287818 A287819 A287820

Keyword

nonn,easy

Author

David Nacin, Jun 02 2017

Status

approved