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

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

Links

Table of n, a(n) for n=0..76.

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.

Example

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;

Maple

T:=proc(n, k) local c: c:=n->binomial(2*n, n)/(n+1): if k<n then c(n-k)-c(n-k-1) elif k=n then 1 else 0 fi end: for n from 0 to 12 do seq(T(n, k), k=0..n) od; # yields sequence in triangular form

Crossrefs

Cf. A000108, A000245.

Sequence in context: A274490 A193357 A361953 * A294219 A091480 A034374

Adjacent sequences: A112410 A112411 A112412 * A112414 A112415 A112416

Keyword

nonn,tabl

Author

Emeric Deutsch, Dec 08 2005

Status

approved