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

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.

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 (5,-3,-5,1,1).

Crossrefs

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

Programs

Magma

R:=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

Mathematica

LinearRecurrence[{5,-3,-5,1,1}, {1,5,19,65,247,955}, 60] (* 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

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