A235163 Number of positive integers with n digits in which adjacent digits differ by at most 1.

9, 26, 75, 217, 629, 1826, 5307, 15438, 44941, 130900, 381444, 1111926, 3242224, 9455987, 27583372, 80472698, 234799873, 685149328, 1999414181, 5835044495, 17029601028, 49702671494, 145066398937, 423412132499, 1235854038791, 3607255734629, 10529101874491

Offset: 1

Author

Gerry Leversha, Jan 04 2014

Keywords

• nonn
• base
• easy

Examples

			a(2) = 26: 10, 11, 12, 21, 22, 23, 32, 33, 34, 43, 44, 45, 54, 55, 56, 65, 66, 67, 76, 77, 78, 87, 88, 89, 98, 99.
		

Links

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

Crossrefs

Cf. A032981, A090994, A126364 (allowing leading zeros).

Programs

Maple

u:= proc(n, r) option remember; `if`(n=1, `if`(r=0, 0, 1),
      add(`if`(r+i in [$0..9], u(n-1, r+i), 0), i=-1..1))
    end:
a:= n-> add(u(n, r), r = 0..9):
seq(a(n), n=1..30);  # Alois P. Heinz, Jan 12 2014

Mathematica

CoefficientList[Series[-x*(3*x^4-18*x^3-9*x^2+28*x-9)/(x^5-6*x^4-x^3+10*x^2-6*x+1),{x,0,30}],x]//Rest (* Harvey P. Dale, Aug 13 2019 *)

Python

from functools import cache
@cache
def u(n, r):
    if r < 0 or r > 9: return 0
    if n == 1: return (r > 0)
    return u(n-1, r-1) + u(n-1, r) + u(n-1, r+1)
def a(n): return sum(u(n, r) for r in range(10))
print([a(n) for n in range(1, 28)]) # Michael S. Branicky, Sep 26 2021

Formula

a(n) = Sum_{r=0..9} u(n,r) where u(n,r) = 0 if r<0 or r>9, u(1,0) = 0, u(1,r) = 1 for 1<=r<=9, and otherwise u(n,r) = u(n-1,r-1) + u(n-1,r) + u(n-1,r+1).

G.f.: -x*(3*x^4-18*x^3-9*x^2+28*x-9)/(x^5-6*x^4-x^3+10*x^2-6*x+1). - Alois P. Heinz, Jan 12 2014