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

1, 10, 94, 886, 8350, 78694, 741646, 6989590, 65872894, 620814406, 5850821230, 55140648694, 519669123166, 4897584703270, 46156938822094, 435002788211926, 4099652849195710, 38636886795609094, 364130592557264686, 3431722880197818550, 32342028292009425694

Offset: 0

Author

David Nacin, Jun 02 2017

Keywords

• nonn
• easy

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

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

Crossrefs

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

Programs

Mathematica

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

Python

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

Formula

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

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

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

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