A287805 Number of quinary sequences of length n such that no two consecutive terms have distance 2.

1, 5, 19, 73, 281, 1083, 4175, 16097, 62065, 239307, 922711, 3557761, 13717913, 52893147, 203943935, 786361409, 3032030689, 11690820555, 45077144455, 173807214241, 670161078089, 2583988659867, 9963272432111, 38416111919777, 148123788152017, 571131629935179

Offset

0,2

Links

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

Index entries for linear recurrences with constant coefficients, signature (4, 1, -6).

Formula

For n>0, a(n) = 4*a(n-1) + a(n-2) - 6*a(n-3), a(1)=5, a(2)=19, a(3)=73.

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

Example

For n=2 the a(2)=19=25-6 sequences contain every combination except these six: 02,20,13,31,24,42.

Mathematica

LinearRecurrence[{4, 1, -6}, {1, 5, 19, 73}, 40]

Prog

(Python)
def a(n):
.if n in [0, 1, 2, 3]:
..return [1, 5, 19, 73][n]
.return 4*a(n-1)+a(n-2)-6*a(n-3)

Crossrefs

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

Sequence in context: A255455 A255444 A377314 * A129166 A149763 A149764

Adjacent sequences: A287802 A287803 A287804 * A287806 A287807 A287808

Keyword

nonn,easy

Author

David Nacin, Jun 01 2017

Status

approved