|
|
A075436
|
|
Right- or upward-moving paths connecting opposite corners of an n X n chessboard, visiting the diagonal in 0 up to (n-2) intermediate points between start and finish. Equivalently, subdivide the chessboard into 1 up to (n-1) blocks along the diagonal in all possible ways and sum the path-count over all sub-blocks.
|
|
5
|
|
|
2, 10, 52, 274, 1452, 7716, 41064, 218722, 1165564, 6213100, 33125336, 176629268, 941884088, 5022886536, 26786945232, 142857244674, 761881733148, 4063282813596, 21670523246712, 115574945807004, 616395334890408, 3287425475237496, 17532874879557552
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
2,1
|
|
COMMENTS
|
Invert transform gives the central binomial coefficients A000984.
If it is required that the paths stay at the same side of the diagonal between intermediate points, then the count of intermediate points becomes an exact count of crossings and one gets the central binomial coefficients A000984.
|
|
LINKS
|
|
|
FORMULA
|
G.f.: x*(1-sqrt(1-4*x)-8*x)/(-3+16*x).
Recurrence (for n>3): 3*(n-1)*a(n) = 2*(14*n-23)*a(n-1)-32*(2*n-5)*a(n-2). - Vaclav Kotesovec, Oct 13 2012
a(n) = 2^(4*n-7)/3^(n-2) * (1 - Sum_{k=2..n-1} C(2*k-1,k)*3^(k-2)/((2*k-1) * 2^(4*k-4)) ), for n>2. - Vaclav Kotesovec, Oct 28 2012
G.f.: 2/(Q(0)-4*x), where Q(k) = 2*x + (k+1)/(2*k+1) - 2*x*(k+1)/(2*k+1)/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Dec 03 2013
|
|
EXAMPLE
|
a(3) = 10 because 0 intermediate points produces 6 paths on a 3 X 3 board and 1 intermediate points produces 4 paths:
1 . 1
1 . 2 . 2
. . 2 . 4
or 6 + 4 = 10 paths in total.
|
|
MATHEMATICA
|
Rest[CoefficientList[Series[(1-Sqrt[1-4*x]-8*x)/(-3+16*x), {x, 0, 24}], x]] (* corrected by Vaclav Kotesovec, Oct 28 2012 *) or combinatorially: Plus@@@Table[Table[Plus@@Apply[Times, Compositions[n-1-k, k]+1 /. i_Integer->Binomial[2i, i], {1}], {k, 1, n-1}], {n, 2, 12}]
Flatten[{2, Table[2^(4*n-7)/3^(n-2)*(1-Sum[Binomial[2*k-1, k]*3^(k-2)/((2*k-1)*2^(4*k-4)), {k, 2, n-1}] ), {n, 3, 20}]}] (* Vaclav Kotesovec, Oct 28 2012 *)
|
|
PROG
|
(PARI) x='x+O('x^66); Vec(x*(1-sqrt(1-4*x)-8*x)/(-3+16*x)) \\ Joerg Arndt, May 07 2013
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|