A101475 Triangle T(n,k) read by rows: number of lattice paths from (0,0) to (0,2n) with steps (1,1) or (1,-1) that stay between the lines y=0 and y=k.

1, 1, 2, 3, 5, 6, 10, 15, 19, 20, 35, 50, 63, 69, 70, 126, 176, 217, 243, 251, 252, 462, 638, 770, 870, 913, 923, 924, 1716, 2354, 2794, 3159, 3355, 3419, 3431, 3432, 6435, 8789, 10307, 11610, 12430, 12766, 12855, 12869, 12870, 24310, 33099, 38489

Offset: 0

Author

Ralf Stephan, Jan 21 2005

Keywords

• nonn
• tabl
• walk

Examples

			Triangle begins
     1;
     1,    2;
     3,    5,     6;
    10,   15,    19,    20;
    35,   50,    63,    69,    70;
   126,  176,   217,   243,   251,   252;
   462,  638,   770,   870,   913,   923,   924;
  1716, 2354,  2794,  3159,  3355,  3419,  3431,  3432;
  6435, 8789, 10307, 11610, 12430, 12766, 12855, 12869, 12870;
		

Links

• W. Y. C. Cheng, E. Y. P. Deng, R. R. X. Du, R. P. Stanley and C. H. Yan, Crossings and nestings of matchings and partitions, arXiv:math/0501230 [math.CO], 2005.

Crossrefs

Left-hand columns include A001700 and A024718. Right-hand columns include A000984 and A030662. Row sums are in A101476.

Programs

Mathematica

T[n_, k_] := Sum[Binomial[2n, n-i(k+2)] - Binomial[2n, n+i(k+2)+k+1], {i, 0, n}]; Table[T[n, k], {n, 0, 9}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jan 20 2019 *)

Formula

T(n, k) = Sum_{i>=0} (binomial(2n, n-i*(k+2)) - binomial(2n, n+i*(k+2)+k+1)).