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

Author

Wouter Meeussen, Sep 15 2002

Keywords

• easy
• nonn
• tabl

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

Examples

			{2},
{6, 4},
{20, 24, 8},
{70, 116, 72, 16},
{252, 520, 456, 192, 32},
...
		

Crossrefs

Row sums give A075436.

Cf. A039598, A000108.

Programs

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}]

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

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]