A287818 Number of nonary sequences of length n such that no two consecutive terms have distance 3.

1, 9, 69, 531, 4089, 31491, 242529, 1867851, 14385369, 110789811, 853254609, 6571393371, 50609994249, 389776014531, 3001884188289, 23119197549291, 178053936060729, 1371293449053651, 10561101680875569, 81336980637343611, 626421808927336809, 4824426473972595171

Offset

0,2

Links

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

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

Formula

For n>2, a(n) = 9*a(n-1) - 10*a(n-2), a(0)=1, a(1)=9, a(2)=69.

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

For n>0, a(n)=(1/5)(3 - 18/sqrt(41))*((9 - sqrt(41))/2)^n + (1/5)(3 + 18/sqrt(41))*((9 + sqrt(41))/2)^n.

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

Example

For n=2 the a(2) = 81 - 12 = 69 sequences contain every combination except these twelve: 03,30,14,41,25,52,36,63,47,74,58,85.

Mathematica

LinearRecurrence[{9, -10}, {1, 9, 69}, 40]

Prog

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

Crossrefs

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

Sequence in context: A361139 A081616 A299915 * A297222 A126530 A351810

Adjacent sequences: A287815 A287816 A287817 * A287819 A287820 A287821

Keyword

nonn,easy

Author

David Nacin, Jun 02 2017

Status

approved