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,2

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

Index entries for linear recurrences with constant coefficients, signature (4,-1,-2).

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)

Mathematica

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

Prog

(S/R) stvar $[N]:(0..M-1) init $[]:=0 asgn $[]->{*} kill +[i in 0..N-1](($[i]`-$[(i+1)mod N]`>2)+($[(i+1)mod N]`-$[i]`>2))
(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
(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

Crossrefs

Cf. A005191, A124806, A206776.

Sequence in context: A081670 A297016 A258255 * A362279 A121530 A121299

Adjacent sequences: A124802 A124803 A124804 * A124806 A124807 A124808

Keyword

nonn,easy

Author

R. H. Hardin, Dec 28 2006

Status

approved