cp's OEIS Frontend

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.

%I A075435 #34 Oct 19 2022 11:24:46
%S A075435 2,6,4,20,24,8,70,116,72,16,252,520,456,192,32,924,2248,2496,1504,480,
%T A075435 64,3432,9520,12624,9728,4480,1152,128,12870,39796,60792,56400,33440,
%U A075435 12480,2688,256,48620,164904,283208,304704,218720,105600,33152,6144
%N 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.
%C A075435 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.
%C A075435 T is the convolution triangle of the central binomial coefficients. - _Peter Luschny_, Oct 19 2022
%F A075435 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]
%e A075435 {2},
%e A075435 {6, 4},
%e A075435 {20, 24, 8},
%e A075435 {70, 116, 72, 16},
%e A075435 {252, 520, 456, 192, 32},
%e A075435 ...
%p A075435 # Uses function PMatrix from A357368. Adds column 1,0,0,0,... to the left.
%p A075435 PMatrix(10, n -> binomial(2*n, n)); # _Peter Luschny_, Oct 19 2022
%t A075435 Table[Table[Plus@@Apply[Times, Compositions[n-1-k, k]+1 /. i_Integer->Binomial[2i, i], {1}], {k, 1, n-1}], {n, 2, 12}]
%o A075435 (Maxima)
%o A075435 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 */
%o A075435 (Sage)
%o A075435 @cached_function
%o A075435 def T(k,n):
%o A075435     if k==n: return 2^n
%o A075435     if k==0: return 0
%o A075435     return sum(binomial(2*i,i)*T(k-1,n-i) for i in (1..n-k+1))
%o A075435 A075435 = lambda n,k: T(k,n)
%o A075435 for n in (1..9): print([A075435(n,k) for k in (1..n)]) # _Peter Luschny_, Mar 12 2016
%Y A075435 Row sums give A075436.
%Y A075435 Cf. A039598, A000108.
%K A075435 easy,nonn,tabl
%O A075435 2,1
%A A075435 _Wouter Meeussen_, Sep 15 2002