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

%I #22 Aug 05 2023 21:31:54

%S 1,5,19,65,247,955,3733,14649,57583,226505,891219,3507047,13801285,

%T 54313277,213745019,841177105,3310392415,13027820227,51270096661,

%U 201769982673,794052091767,3124938240153,12297982928987,48397879544975

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

%C 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.

%H G. C. Greubel, <a href="/A124806/b124806.txt">Table of n, a(n) for n = 0..1000</a>

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (5,-3,-5,1,1).

%F From _Colin Barker_, Jun 04 2017: (Start)

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

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

%F a(n) = -4*[n=0] + LucasL(n-1) + 3*A099503(n) - 8*A099503(n-1). - _G. C. Greubel_, Aug 03 2023

%t LinearRecurrence[{5,-3,-5,1,1}, {1,5,19,65,247,955}, 60] (* _G. C. Greubel_, Aug 03 2023 *)

%o (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))

%o (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

%o (SageMath)

%o @CachedFunction

%o def a(n): # a = A124806

%o if (n<6): return (1,5,19,65,247,955)[n]

%o else: return 5*a(n-1)-3*a(n-2)-5*a(n-3)+a(n-4)+a(n-5)

%o [a(n) for n in range(31)] # _G. C. Greubel_, Aug 03 2023

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

%K nonn,easy

%O 0,2

%A _R. H. Hardin_, Dec 28 2006