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

1, 10, 92, 848, 7816, 72040, 663992, 6120008, 56408056, 519912520, 4792028792, 44168084168, 407096815096, 3752207504200, 34584061167992, 318760965520328, 2938016812018936, 27079673239211080, 249593092776937592, 2300497181470860488, 21203660818791619576

Offset

0,2

Comments

In general, the number of sequences over the alphabet {0,1,...,9} such that no two consecutive terms have distance 5+k for k in {0,1,2,3,4} is given by a(n) = 9*a(n-1) + 2*k*a(n-2), a(0)=1, a(1)=10.

Links

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

Index entries for linear recurrences with constant coefficients, signature (9,2).

Formula

a(n) = 9*a(n-1) + 2*a(n-2), a(0)=1, a(1)=10.

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

a(n) = ((1 - 11/sqrt(89))/2)*((9 - sqrt(89))/2)^n + ((1 + 11/sqrt(89))/2)*((9 + sqrt(89))/2)^n.

a(n) = A015579(n)+A015579(n+1). - R. J. Mathar, Oct 20 2019

Mathematica

LinearRecurrence[{9, 2}, {1, 10}, 30]

Prog

(Python)
def a(n):
.if n in [0, 1]:
..return [1, 10][n]
.return 9*a(n-1)+2*a(n-2)

Crossrefs

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

Sequence in context: A037534 A120996 A190990 * A265242 A262173 A103944

Adjacent sequences: A287826 A287827 A287828 * A287830 A287831 A287832

Keyword

nonn,easy

Author

David Nacin, Jun 02 2017

Status

approved