login
A287818
Number of nonary sequences of length n such that no two consecutive terms have distance 3.
0
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
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)
KEYWORD
nonn,easy
AUTHOR
David Nacin, Jun 02 2017
STATUS
approved