A287804 Number of quinary sequences of length n such that no two consecutive terms have distance 1.

1, 5, 17, 59, 205, 713, 2481, 8635, 30057, 104629, 364225, 1267923, 4413861, 15365465, 53490097, 186209299, 648230545, 2256616133, 7855718641, 27347281995, 95201200637, 331413874569, 1153716087665, 4016309864843, 13981555011321, 48672509644725

Offset

0,2

Links

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

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

Formula

a(n) = 5*a(n-1) - 5a(n-2) - a(n-3), a(0)=1, a(1)=5, a(2)=17.

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

Example

For n=2 the a(2)=17=25-8 sequences contain every combination except these eight: 01,10,12,21,23,32,34,43.

Mathematica

LinearRecurrence[{5, -5, -1}, {1, 5, 17}, 50]

Prog

(Python)
def a(n):
    if n in [0, 1, 2]:
        return [1, 5, 17][n]
    return 5*a(n-1)-5*a(n-2)-a(n-3)

Crossrefs

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

Sequence in context: A171838 A105392 A090857 * A149657 A149658 A149659

Adjacent sequences: A287801 A287802 A287803 * A287805 A287806 A287807

Keyword

nonn,easy

Author

David Nacin, Jun 01 2017

Status

approved