|
|
A075435
|
|
T(n,k) = right- or upward-moving paths connecting opposite corners of an n X n chessboard, visiting the diagonal at k points between start and finish.
|
|
2
|
|
|
2, 6, 4, 20, 24, 8, 70, 116, 72, 16, 252, 520, 456, 192, 32, 924, 2248, 2496, 1504, 480, 64, 3432, 9520, 12624, 9728, 4480, 1152, 128, 12870, 39796, 60792, 56400, 33440, 12480, 2688, 256, 48620, 164904, 283208, 304704, 218720, 105600, 33152, 6144
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
2,1
|
|
COMMENTS
|
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 table A039598.
T is the convolution triangle of the central binomial coefficients. - Peter Luschny, Oct 19 2022
|
|
LINKS
|
|
|
FORMULA
|
G.f.: [2*x*c(x)/(1-x*c(x))]^m=sum(n>=m T(n,m)*x^n) where c(x) is the g.f. of A000108, also T(n,m)=sum(k=m..n, k/n*binomial(2*n-k-1,n-1)*2^k*binomial(k-1,m-1)), n>=m>0. [Vladimir Kruchinin, Mar 30 2011]
|
|
EXAMPLE
|
{2},
{6, 4},
{20, 24, 8},
{70, 116, 72, 16},
{252, 520, 456, 192, 32},
...
|
|
MAPLE
|
# Uses function PMatrix from A357368. Adds column 1, 0, 0, 0, ... to the left.
|
|
MATHEMATICA
|
Table[Table[Plus@@Apply[Times, Compositions[n-1-k, k]+1 /. i_Integer->Binomial[2i, i], {1}], {k, 1, n-1}], {n, 2, 12}]
|
|
PROG
|
(Maxima)
T(n, m):=sum(k/n*binomial(2*n-k-1, n-1)*2^k*binomial(k-1, m-1), k, m, n); /* Vladimir Kruchinin, Mar 30 2011 */
(Sage)
@cached_function
def T(k, n):
if k==n: return 2^n
if k==0: return 0
return sum(binomial(2*i, i)*T(k-1, n-i) for i in (1..n-k+1))
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|