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, 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

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

Table of n, a(n) for n=2..45.

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.
PMatrix(10, n -> binomial(2*n, n)); # Peter Luschny, Oct 19 2022

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))
A075435 = lambda n, k: T(k, n)
for n in (1..9): print([A075435(n, k) for k in (1..n)]) # Peter Luschny, Mar 12 2016

Crossrefs

Row sums give A075436.

Cf. A039598, A000108.

Sequence in context: A079579 A309243 A112326 * A069875 A202962 A019088

Adjacent sequences: A075432 A075433 A075434 * A075436 A075437 A075438

Keyword

easy,nonn,tabl

Author

Wouter Meeussen, Sep 15 2002

Status

approved