A112413 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n and starting with exactly k UD's, where U=(1,1), D=(1,-1) (0 <= k <= n).

1, 0, 1, 1, 0, 1, 3, 1, 0, 1, 9, 3, 1, 0, 1, 28, 9, 3, 1, 0, 1, 90, 28, 9, 3, 1, 0, 1, 297, 90, 28, 9, 3, 1, 0, 1, 1001, 297, 90, 28, 9, 3, 1, 0, 1, 3432, 1001, 297, 90, 28, 9, 3, 1, 0, 1, 11934, 3432, 1001, 297, 90, 28, 9, 3, 1, 0, 1, 41990, 11934, 3432, 1001, 297, 90, 28, 9, 3, 1, 0

Offset: 0

Author

Emeric Deutsch, Dec 08 2005

Keywords

• nonn
• tabl

Comments

All columns, except for initial terms, yield A000245. Row sums yield the Catalan numbers (A000108).

Riordan array ((1-x)*c(x),x), c(x) the g.f. of A000108; equal to A125177*A130595. - Philippe Deléham, Dec 08 2009

Examples

			T(5,2)=3 because we have UDUDUUDDUD, UDUDUUDUDD and UDUDUUUDDD, where U=(1,1), D=(1,-1).
Triangle begins:
   1;
   0, 1;
   1, 0, 1;
   3, 1, 0, 1;
   9, 3, 1, 0, 1;
  28, 9, 3, 1, 0, 1;
		

Crossrefs

Cf. A000108, A000245.

Programs

Maple

T:=proc(n,k) local c: c:=n->binomial(2*n,n)/(n+1): if k
				

Formula

T(n,k) = c(n-k) - c(n-k-1), where c(n) = binomial(2n, n)/(n+1) is the n-th Catalan number. G.f. = (1-z)*C/(1-tz), where C = (1-sqrt(1-4z))/(2z) is the Catalan function.