A126364 Number of base 10 n-digit numbers with adjacent digits differing by one or less.

10, 28, 80, 230, 664, 1922, 5574, 16188, 47064, 136946, 398746, 1161634, 3385486, 9869934, 28781908, 83948652, 244894048, 714493794, 2084792450, 6083620812, 17753709802, 51812911858, 151218254846, 441351052720

Offset: 1

Author

R. H. Hardin, Dec 26 2006

Keywords

• nonn
• base
• easy

Comments

[Empirical] a(base,n)=a(base-1,n)+3^(n-1) for base>=n; a(base,n)=a(base-1,n)+3^(n-1)-2 when base=n-1.

Links

• G. C. Greubel, Table of n, a(n) for n = 1..1000
• Index entries for linear recurrences with constant coefficients, signature (6,-10,1,6,-1).

Programs

Mathematica

CoefficientList[ Series[(1 + 4x - 22x^2 + 11x^3 + 14x^4 - 3x^5)/(1 - 6x + 10x^2 - x^3 - 6x^4 + x^5), {x, 0, 24}], x] (* Robert G. Wilson v, Aug 19 2011 *)
LinearRecurrence[{6, -10, 1, 6, -1}, {10, 28, 80, 230, 664}, 30] (* Vincenzo Librandi, Mar 21 2015 *)

PARI

Vec((1+4*x-22*x^2+11*x^3+14*x^4-3*x^5)/(1-6*x+10*x^2-x^3-6*x^4+x^5)+O(x^99)) \\ Charles R Greathouse IV, Aug 23 2011

Formula

G.f.: (1 + 4*x - 22*x^2 + 11*x^3 + 14*x^4 - 3*x^5)/(1 - 6*x + 10*x^2 - x^3 - 6*x^4 + x^5). - Alexander R. Povolotsky_, Aug 18 2011

Conjecture: a(n) = 3*a(n-1) - A025565(n), n >= 2. - Daniel Forgues, Aug 23 2011