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

1, 5, 19, 65, 247, 955, 3733, 14649, 57583, 226505, 891219, 3507047, 13801285, 54313277, 213745019, 841177105, 3310392415, 13027820227, 51270096661, 201769982673, 794052091767, 3124938240153, 12297982928987, 48397879544975

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.

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (5,-3,-5,1,1).

Formula

From Colin Barker, Jun 04 2017: (Start)

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

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

a(n) = -4*[n=0] + LucasL(n-1) + 3*A099503(n) - 8*A099503(n-1). - G. C. Greubel, Aug 03 2023

Mathematica

LinearRecurrence[{5, -3, -5, 1, 1}, {1, 5, 19, 65, 247, 955}, 60] (* 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) R<x>:=PowerSeriesRing(Integers(), 30); Coefficients(R!( (1-3*x^2-10*x^3+3*x^4+4*x^5)/((1-x-x^2)*(1-4*x+x^3)) )); // G. C. Greubel, Aug 03 2023
(SageMath)
@CachedFunction
def a(n): # a = A124806
    if (n<6): return (1, 5, 19, 65, 247, 955)[n]
    else: return 5*a(n-1)-3*a(n-2)-5*a(n-3)+a(n-4)+a(n-5)
[a(n) for n in range(31)] # G. C. Greubel, Aug 03 2023

Crossrefs

Cf. A000032, A005191, A099503, A124805, A124807.

Sequence in context: A359919 A099448 A239618 * A059509 A137745 A005021

Adjacent sequences: A124803 A124804 A124805 * A124807 A124808 A124809

Keyword

nonn,easy

Author

R. H. Hardin, Dec 28 2006

Status

approved