OFFSET
1,1
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).
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
EXAMPLE
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.
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 *)
PROG
(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
CROSSREFS
KEYWORD
nonn,base,easy
AUTHOR
Gerry Leversha, Jan 04 2014
STATUS
approved