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,1

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).

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

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 *)

Prog

(S/R) stvar $[N]:(0..M-1) init $[]:=0 asgn $[]->{*} kill +[i in 0..N-2](($[i]`-$[i+1]`>1)+($[i+1]`-$[i]`>1))
(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

Crossrefs

Sequence in context: A124703 A333241 A251319 * A076712 A116973 A352180

Adjacent sequences: A126361 A126362 A126363 * A126365 A126366 A126367

Keyword

nonn,base,easy

Author

R. H. Hardin, Dec 26 2006

Status

approved