A081113 - OEIS

%I #57 Jan 21 2021 07:43:40

%S 1,4,17,68,259,950,3387,11814,40503,136946,457795,1515926,4979777,

%T 16246924,52694573,170028792,546148863,1747255194,5569898331,

%U 17698806798,56076828573,177208108824,558658899825,1757365514652

%N Number of paths of length n-1 a king can take from one side of an n X n chessboard to the opposite side.

%C 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

%C 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

%H Vincenzo Librandi, <a href="/A081113/b081113.txt">Table of n, a(n) for n = 1..200</a>

%H Simon Plouffe, <a href="https://web.archive.org/web/20150114055057/http://www.plouffe.fr/simon/OEIS/OEIS_conjectured_formulas.txt">OEIS conjectured formulas</a>.

%H D. Yaqubi, M. Farrokhi D. G., and H. Ghasemian Zoeram, <a href="https://arxiv.org/abs/1612.08697">Lattice paths inside a table, I </a>, arXiv:1612.08697 [math.CO], 2016-2017.

%F 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.

%F 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

%F 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

%F 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

%F a(n) ~ 3^(n-1)*n*(1-4/(sqrt(3*Pi*n))). - _Vaclav Kotesovec_, Oct 28 2012

%F 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

%e For n=2 the 4 paths are (0,0)->(0,1); (0,0)->(1,1); (1,0)->(0,1); (1,0)->(1,1).

%p 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:

%p A081113 := proc(n) add(k*(n-k+1)*A026300(n-1,k-1),k=1..n) ; end proc:

%p seq(A081113(n),n=1..20) ;

%p # _R. J. Mathar_, Jun 09 2010

%t 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]

%Y Cf. A005773 (paths which begin at a corner), diagonal of A296449.

%K easy,nonn

%O 1,2

%A _David Scambler_, Apr 16 2003