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

%I #31 Aug 03 2023 15:09:54

%S 1,4,14,46,162,574,2042,7270,25890,92206,328394,1169590,4165554,

%T 14835838,52838618,188187526,670239810,2387094478,8501763050,

%U 30279478102,107841960402,384084837406,1367938433018,4871984973862

%N Number of circular n-letter words over the alphabet {0,1,2,3} 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.

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

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

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

%F a(n) = 1 + A206776(n) for n > 0. - _Bruno Berselli_, Jan 11 2013

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

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

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

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

%t LinearRecurrence[{4,-1,-2}, {1,4,14,46}, 40] (* _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) 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

%o (SageMath)

%o A206776=BinaryRecurrenceSequence(3,2,2,3)

%o [1+A206776(n) -2*int(n==0) for n in range(41)] # _G. C. Greubel_, Aug 03 2023

%Y Cf. A005191, A124806, A206776.

%K nonn,easy

%O 0,2

%A _R. H. Hardin_, Dec 28 2006