A124697 Number of base 4 circular n-digit numbers with adjacent digits differing by 1 or less.

1, 4, 10, 22, 54, 134, 340, 872, 2254, 5854, 15250, 39802, 104004, 271964, 711490, 1861862, 4873054, 12755614, 33391060, 87413152, 228841254, 599099054, 1568437210, 4106182322, 10750060804, 28143920884, 73681573690, 192900592822, 505019869254, 1322158472054

Offset: 0

Author

R. H. Hardin, Dec 28 2006

Keywords

• nonn
• base
• easy

Comments

[Empirical] a(base,n)=a(base-1,n)+A002426(n+1) for base>=1.int(n/2)+1

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

Links

• Colin Barker, 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 (4,-3,-2,1).

Crossrefs

Cf. A000032, A005248, A056014.

Programs

Mathematica

LinearRecurrence[{4,-3,-2,1},{1,4,10,22,54},30] (* Harvey P. Dale, Oct 14 2016 *)

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

Formula

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

From Peter Bala, Nov 08 2022: (Start)

a(n) = Lucas(n) + Lucas(2*n) = A000032(n) + A005248(n) for n >= 1.

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.

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)