|
Search: id:A075436
|
|
|
| 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. |
|
+0
2
|
|
| 2, 10, 52, 274, 1452, 7716, 41064, 218722, 1165564, 6213100, 33125336, 176629268, 941884088, 5022886536, 26786945232, 142857244674, 761881733148, 4063282813596, 21670523246712, 115574945807004, 616395334890408
(list; graph; listen)
|
|
|
OFFSET
|
2,1
|
|
|
COMMENT
|
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. Row sums of A075435.
|
|
FORMULA
|
G.f.: (1-Sqrt[1-4*x]-8*x)/(-3+16*x)
|
|
EXAMPLE
|
a(3)=10 because 0 intermediate points produces 6 paths on a 3 by 3 board and 1 intermediate points produces 4 paths:
1 . 1
1 . 2 . 2
. . 2 . 4
or 6 + 4 = 10 paths in total.
|
|
MATHEMATICA
|
CoefficientList[Series[(1-Sqrt[1-4*x]-8*x)/(-3+16*x), {x, 0, 24}], x] 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}]
|
|
CROSSREFS
|
Cf. A075435, A000984.
Sequence in context: A019476 A019475 A020042 this_sequence A074612 A104497 A166694
Adjacent sequences: A075433 A075434 A075435 this_sequence A075437 A075438 A075439
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
Wouter Meeussen (wouter.meeussen(AT)pandora.be), Sep 15 2002
|
|
|
Search completed in 0.002 seconds
|
