cp's OEIS Frontend

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

%I A235163 #33 Sep 26 2021 08:11:46
%S A235163 9,26,75,217,629,1826,5307,15438,44941,130900,381444,1111926,3242224,
%T A235163 9455987,27583372,80472698,234799873,685149328,1999414181,5835044495,
%U A235163 17029601028,49702671494,145066398937,423412132499,1235854038791,3607255734629,10529101874491
%N A235163 Number of positive integers with n digits in which adjacent digits differ by at most 1.
%H A235163 Alois P. Heinz, <a href="/A235163/b235163.txt">Table of n, a(n) for n = 1..1000</a>
%H A235163 <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (6,-10,1,6,-1).
%F A235163 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).
%F A235163 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
%e A235163 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.
%p A235163 u:= proc(n, r) option remember; `if`(n=1, `if`(r=0, 0, 1),
%p A235163       add(`if`(r+i in [$0..9], u(n-1, r+i), 0), i=-1..1))
%p A235163     end:
%p A235163 a:= n-> add(u(n, r), r = 0..9):
%p A235163 seq(a(n), n=1..30);  # _Alois P. Heinz_, Jan 12 2014
%t A235163 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 *)
%o A235163 (Python)
%o A235163 from functools import cache
%o A235163 @cache
%o A235163 def u(n, r):
%o A235163     if r < 0 or r > 9: return 0
%o A235163     if n == 1: return (r > 0)
%o A235163     return u(n-1, r-1) + u(n-1, r) + u(n-1, r+1)
%o A235163 def a(n): return sum(u(n, r) for r in range(10))
%o A235163 print([a(n) for n in range(1, 28)]) # _Michael S. Branicky_, Sep 26 2021
%Y A235163 Cf. A032981, A090994, A126364 (allowing leading zeros).
%K A235163 nonn,base,easy
%O A235163 1,1
%A A235163 _Gerry Leversha_, Jan 04 2014