A287825 Number of sequences over the alphabet {0,1,...,9} such that no two consecutive terms have distance 1.

1, 10, 82, 674, 5540, 45538, 374316, 3076828, 25291120, 207889674, 1708825732, 14046322404, 115458919774, 949057110644, 7801124426174, 64124215108032, 527092600834054, 4332631742719370, 35613662169258228, 292739611493034596, 2406281042646218328

Offset

0,2

Links

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

Index entries for linear recurrences with constant coefficients, signature (9, -4, -21, 9, 5).

Formula

For n>5, a(n) = 9*a(n-1) - 4*a(n-2) - 21*a(n-3) + 9*a(n-4) + 5*a(n-5), a(0)=1, a(1)=10, a(2)=82, a(3)=674, a(4)=5540, a(5)=45538.

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

Mathematica

LinearRecurrence[{9, -4, -21, 9, 5}, {1, 10, 82, 674, 5540, 45538}, 40]

Prog

(Python)
def a(n):
    if n in [0, 1, 2, 3, 4, 5]:
        return [1, 10, 82, 674, 5540, 45538][n]
    return 9*a(n-1) - 4*a(n-2) - 21*a(n-3) + 9*a(n-4) + 5*a(n-5)

Crossrefs

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

Sequence in context: A154246 A037549 A238276 * A199701 A103460 A339689

Adjacent sequences: A287822 A287823 A287824 * A287826 A287827 A287828

Keyword

nonn,easy

Author

David Nacin, Jun 02 2017

Status

approved