A124805 Number of circular n-letter words over the alphabet {0,1,2,3} with adjacent letters differing by at most 2.

1, 4, 14, 46, 162, 574, 2042, 7270, 25890, 92206, 328394, 1169590, 4165554, 14835838, 52838618, 188187526, 670239810, 2387094478, 8501763050, 30279478102, 107841960402, 384084837406, 1367938433018, 4871984973862

Offset: 0

Author

R. H. Hardin, Dec 28 2006

Keywords

• nonn
• easy

Comments

Empirical: a(base, n) = a(base-1, n) + A005191(n+1) for base >= 2*floor(n/2) + 1 where base is the number of letters in the alphabet.

Sequence appears to have generating function (1-x^2-4*x^3)/((1-x)*(1-3*x-2*x^2)). The degree of the numerator would drop by one if the initial term were changed from 1 to 3: (3-8*x+x^2)/((1-x)*(1-3*x-2*x^2)). - Creighton Dement, Aug 20 2007

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• OEIS Wiki, Number of base k circular n-digit numbers with adjacent digits differing by d or less
• Index entries for linear recurrences with constant coefficients, signature (4,-1,-2).

Crossrefs

Cf. A005191, A124806, A206776.

Programs

Magma

I:=[1,4,14,46]; [n le 4 select I[n] else 4*Self(n-1) -Self(n-2) -2*Self(n-3): n in [1..40]]; // G. C. Greubel, Aug 03 2023

Mathematica

LinearRecurrence[{4,-1,-2}, {1,4,14,46}, 40] (* G. C. Greubel, Aug 03 2023 *)

SageMath

A206776=BinaryRecurrenceSequence(3,2,2,3)
[1+A206776(n) -2*int(n==0) for n in range(41)] # G. C. Greubel, Aug 03 2023

Formula

a(n) = 1 + A206776(n) for n > 0. - Bruno Berselli, Jan 11 2013

From Colin Barker, Jun 02 2017: (Start)

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

a(n) = 1 + ((3-sqrt(17))/2)^n + ((3+sqrt(17))/2)^n for n>0.

a(n) = 4*a(n-1) - a(n-2) - 2*a(n-3) for n > 3. (End)