OFFSET
1,2
COMMENTS
a(n) = number of sequences (a_1,a_2,...,a_n) with 1<=a_i<=n for all i and |a_(i+1)-a_(i)|<=1 for 1<=i<=n-1. For n=2 the sequences are 11, 12, 21, 22. - David Callan, Oct 24 2004
Simon Plouffe proposes the ordinary generating function A(x) (for offset zero) in the implicit form 3-10*x+12*x^2+(-4+30*x+54*x^3-72*x^2)*A(x)+(81*x^4+54*x^2+1-12*x-108*x^3)*A(x)^2 = 0 which delivers at least the first 200 terms (i.e., as far as tested) correctly. - David Scambler, R. J. Mathar, Jan 06 2011
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 1..200
Simon Plouffe, OEIS conjectured formulas.
D. Yaqubi, M. Farrokhi D. G., and H. Ghasemian Zoeram, Lattice paths inside a table, I , arXiv:1612.08697 [math.CO], 2016-2017.
FORMULA
a(n) = Sum_{k=1..n} k*(n-k+1)*M(n-1, k-1) where k*(n-k+1) is the triangular view of A003991 and M() is the Motzkin triangle A026300.
Conjecture: g.f.(x)=z*A064808(z), where z=x*A001006(x) and A...(x) are the corresponding generating functions. - R. J. Mathar, Jul 07 2009
Conjecture from WolframAlpha (verified for 1<=n<=180): (n+3)*a(n+4) = 27*n*a(n) +27*a(n+1) -9*(2*n+5)*a(n+2) +(8*n+21)*a(n+3). - Alexander R. Povolotsky, Jan 04 2011
Shorter recurrence: (n-1)*(2*n-7)*a(n) = (10*n^2-39*n+23)*a(n-1) - 3*(2*n^2-n-9)*a(n-2) - 9*(n-3)*(2*n-5)*a(n-3). - Vaclav Kotesovec, Oct 28 2012
a(n) ~ 3^(n-1)*n*(1-4/(sqrt(3*Pi*n))). - Vaclav Kotesovec, Oct 28 2012
a(n) = (n+2)*3^(n-2)+2*Sum_{k=0..n-3} (n-k-2)*3^(n-k-3)*A001006(k). [Yaqubi Corollary 2.8] - R. J. Mathar, Dec 13 2017
EXAMPLE
For n=2 the 4 paths are (0,0)->(0,1); (0,0)->(1,1); (1,0)->(0,1); (1,0)->(1,1).
MAPLE
A026300 := proc(n, k) add( binomial(n, 2*i+n-k)*(binomial(2*i+n-k, i) -binomial(2*i+n-k, i-1)), i=0..floor(k/2)) ; end proc:
seq(A081113(n), n=1..20) ;
# R. J. Mathar, Jun 09 2010
MATHEMATICA
t[n_, k_] := Sum[ Binomial[n, 2i + n - k] (Binomial[2i + n - k, i] - Binomial[2i + n - k, i - 1]), {i, 0, Floor[k/2]}] (* from A026300 *); f[n_] := Sum[ k(n - k + 1)t[n - 1, k - 1], {k, n}]; Array[f, 24]
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
David Scambler, Apr 16 2003
STATUS
approved