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

Author

David Nacin, Jun 02 2017

Keywords

• nonn
• easy

Examples

			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.
		

Links

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

Crossrefs

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

Programs

Mathematica

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

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)

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).