|
%I #24 Nov 09 2022 19:21:23
%S 1,4,10,22,54,134,340,872,2254,5854,15250,39802,104004,271964,711490,
%T 1861862,4873054,12755614,33391060,87413152,228841254,599099054,
%U 1568437210,4106182322,10750060804,28143920884,73681573690,192900592822,505019869254,1322158472054
%N Number of base 4 circular n-digit numbers with adjacent digits differing by 1 or less.
%C [Empirical] a(base,n)=a(base-1,n)+A002426(n+1) for base>=1.int(n/2)+1
%C a(n) = T(n, 4) where T(n, k) = Sum_{j=1..k} (1+2*cos(j*Pi/(k+1)))^n. These are the number of smooth cyclic words of length n over the alphabet {1,2,3,4}. See theorem 3.3 in Knopfmacher and others, reference in A124696. - _Peter Luschny_, Aug 13 2012
%H Colin Barker, <a href="/A124697/b124697.txt">Table of n, a(n) for n = 0..1000</a>
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (4,-3,-2,1).
%F G.f.: A(x) = (3*x^4-4*x^3-3*x^2+1) / ((x^2-3*x+1)*(1-x-x^2)). - _Colin Barker_, Jul 19 2015
%F From _Peter Bala_, Nov 08 2022: (Start)
%F a(n) = Lucas(n) + Lucas(2*n) = A000032(n) + A005248(n) for n >= 1.
%F A(x) = 1 + x*B'(x)/B(x), where B(x) = 1/((1 - x - x^2)*(1 - 3*x + x^2)) = 1 + 4*x + 13*x^2 + 38*x^3 + ... has integral coefficients. See A056014.
%F It follows that the Gauss congruences hold: a(n*p^r) == a(n*p^(r-1)) (mod p^r) for all primes p and positive integers n and r. (End)
%t LinearRecurrence[{4,-3,-2,1},{1,4,10,22,54},30] (* _Harvey P. Dale_, Oct 14 2016 *)
%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))
%o (PARI) Vec(-(3*x^4-4*x^3-3*x^2+1)/((x^2-3*x+1)*(x^2+x-1)) + O(x^40)) \\ _Colin Barker_, Jul 19 2015
%Y Cf. A000032, A005248, A056014.
%K nonn,base,easy
%O 0,2
%A _R. H. Hardin_, Dec 28 2006
|
