A287819 Number of nonary sequences of length n such that no two consecutive terms have distance 4.

1, 9, 71, 561, 4433, 35031, 276827, 2187585, 17287073, 136608591, 1079529611, 8530826457, 67413620993, 532726379847, 4209793089371, 33267280400913, 262889866978817, 2077449112980255, 16416740845208075, 129730917736941417, 1025179795159015841

Offset

0,2

Links

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

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

Formula

For n>2, a(n) = 8*a(n-1) + a(n-2) - 14*a(n-3), a(0)=1, a(1)=9, a(2)=71, a(3)=561.

G.f.: (1 + x - 2 x^2 - 2 x^3)/(1 - 8 x - x^2 + 14 x^3).

Example

For n=2 the a(2) = 81 - 10 = 71 sequences contain every combination except these ten: 04,40,15,51,26,62,37,73,48,84.

Mathematica

LinearRecurrence[{8, 1, -14}, {1, 9, 71, 561}, 40]

Prog

(Python)
def a(n):
    if n in [0, 1, 2, 3]:
        return [1, 9, 71, 561][n]
    return 8*a(n-1)+a(n-2)-14*a(n-3)

Crossrefs

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

Sequence in context: A164551 A178869 A057080 * A001706 A368268 A251284

Adjacent sequences: A287816 A287817 A287818 * A287820 A287821 A287822

Keyword

nonn,easy

Author

David Nacin, Jun 02 2017

Status

approved