A100537 Triangle read by rows: T(n,k) is the number of Dyck n-paths whose first descent has length k.

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

Offset: 1

Author

David Callan, Nov 27 2004

Keywords

• nonn
• tabl

Comments

T(n,k) has several other interpretations in terms of Dyck n-paths: besides counting them by length k of first descent, it also counts them by (i) number of UDs with which path begins, (ii) height of lowest valley point, (iii) number of upsteps immediately following the last ascending valley point, (iv) number of consecutive UDs starting at the end of the last long ascent.

A valley point is a path vertex that's preceded by a downstep and followed by an upstep. Starting at the origin (treated as a valley point), scan the valley points left to right as long as their ordinates are weakly increasing to obtain the last ascending valley point.

For example, the valley points in UDUUDUduDDUUUDUDDD have ordinates 0,1,1,0,2 and so the last ascending one is the third (in small type) and k=1 in (iii).

A long ascent is one consisting of 2 or more upsteps and for this purpose an upstep is prepended to the path to ensure at least one long ascent. For example, UUDDUUUDUDDD has 2 long ascents and the last one continues as UUUDUD..., so (iv) has k=2 consecutive UDs.

These results all follow from a consideration of the effect of combinations of the involutions R and phi on Dyck paths where R is path reversal and phi is Deutsch's involution defined recursively by phi({}) = {}, phi(U P D Q) = U phi(Q) D phi(P) with P,Q Dyck paths.

Essentially, Riordan array (f(x), x) where f(x) is the g.f. of A071724. - Philippe Deléham, Feb 07 2014

Examples

			Table begins
  * k..1...2...3......
  n
  1 |..1
  2 |..1...1
  3 |..3...1...1
  4 |..9...3...1...1
  5 |.28...9...3...1...1
  6 |.90..28...9...3...1...1
  7 |297..90..28...9...3...1...1
For example, UUDDUD has first descent of length 2 and T(3,1)=3 counts UUDUDD, UDUUDD, UDUDUD.
		

Links

• G. C. Greubel, Rows n = 1..50 of the triangle, flattened

Crossrefs

Row sums are the Catalan numbers A000108.

Each column is A071724.

Programs

Magma

A100537:= func< n,k | k eq n select 1 else 3*(n-k)*Catalan(n-k)/(n-k+2) >;
[A100537(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, May 03 2021

Mathematica

T[n_, k_]:= Boole[k==n] + 3*(n-k)*CatalanNumber[n-k]/(n-k+2);
Table[T[n, k], {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, May 03 2021 *)

Sage

def A100537(n,k): return bool(k==n) + 3*(n-k)*catalan_number(n-k)/(n-k+2)
flatten([[A100537(n,k) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, May 03 2021

Formula

T(n, k) = Cat(n-k) - Cat(n-k-1) where (Cat(n))_{n>=0} = (1, 2, 5, 14, ...) is the convolution of the Catalan numbers A000108 with itself.

G.f.: (1-x)*y*(1 - 2*x - sqrt(1-4*x))/(2*x*(1 - x*y)).

T(n, k) = 3*(n-k)*C(n-k)/(n-k+2) + [k=n], where C(n) = A000108(n). - G. C. Greubel, May 03 2021