%I #43 May 09 2023 06:58:43
%S 1,3,7,15,35,83,199,479,1155,2787,6727,16239,39203,94643,228487,
%T 551615,1331715,3215043,7761799,18738639,45239075,109216787,263672647,
%U 636562079,1536796803,3710155683,8957108167,21624372015,52205852195
%N Number of base-3 circular n-digit numbers with adjacent digits differing by 1 or less.
%C These are the number of smooth cyclic words of length n over the alphabet {1,2,3}. See theorem 3.3 in Knopfmacher and others. - _Peter Luschny_, Aug 13 2012
%C This is the main entry for 234 similar sequences. Cf. the link to the OEIS Wiki for a list, the programs and a derivation of the linear recurrences. - _Georg Fischer_, Apr 09 2021
%H R. H. Hardin, <a href="/A124696/b124696.txt">Table of n, a(n) for n = 0..210</a> [uploaded by Georg Fischer, Apr 05 2021]
%H Arnold Knopfmacher, Toufik Mansour, Augustine Munagi, and Helmut Prodinger, <a href="http://arxiv.org/abs/0809.0551">Smooth words and Chebyshev polynomials</a>, arXiv:0809.0551v1 [math.CO], 2008.
%H OEIS Wiki, <a href="/wiki/Number_of_base_k_circular_n-digit_numbers_with_adjacent_digits_differing_by_d_or_less">Number of base k circular n-digit numbers with adjacent digits differing by d or less</a>
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,-1,-1).
%F [Empirical] a(base,n) = a(base-1,n) + A002426(n+1) for base = 1..floor(n/2)+1.
%F a(n) = T(n,3) for n > 0, where T(n,k) = Sum_{j=1..k} (1 + 2*cos(j*Pi/(k + 1)))^n. - _Peter Luschny_, Aug 13 2012
%F From _Colin Barker_, Nov 26 2012: (Start)
%F a(n) = 1 + (1 - sqrt(2))^n + (1 + sqrt(2))^n for n > 0.
%F a(n) = 3*a(n-1) - a(n-2) - a(n-3) for n > 3.
%F G.f.: -(2*x^3 + x^2 - 1)/((x - 1)*(x^2 + 2*x - 1)). (End)
%F a(n) = A002203(n)+1, n>0. - _R. J. Mathar_, May 09 2023
%p T := (n, k) -> `if`(n=0, 1, add((1 + 2*cos(j*Pi/(k + 1)))^n, j=1..k)):
%p a := n -> simplify(T(n, 3)): seq(a(n), n=0..28); # _Peter Luschny_, Mar 28 2021
%o (S/R) stvar $[N]:(0..M-1) init $[]:=0 asgn $[]->{*} kill +[i in 0..N-1](($[i]`-$[(i+1)mod N]`>1)+($[(i+1)mod N]`-$[i]`>1))
%Y Cf. A002426, Row 3 of A276562.
%K nonn,base,easy
%O 0,2
%A _R. H. Hardin_, Dec 28 2006
|