|
|
A081113
|
|
Number of paths of length n-1 a king can take from one side of an n X n chessboard to the opposite side.
|
|
4
|
|
|
1, 4, 17, 68, 259, 950, 3387, 11814, 40503, 136946, 457795, 1515926, 4979777, 16246924, 52694573, 170028792, 546148863, 1747255194, 5569898331, 17698806798, 56076828573, 177208108824, 558658899825, 1757365514652
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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) = (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:
A081113 := proc(n) add(k*(n-k+1)*A026300(n-1, k-1), k=1..n) ; end proc:
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|