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

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

Links

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

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

Example

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.

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 *)

Prog

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

Crossrefs

Row sums are the Catalan numbers A000108.

Each column is A071724.

Sequence in context: A102435 A340882 A152570 * A069605 A080510 A350772

Adjacent sequences: A100534 A100535 A100536 * A100538 A100539 A100540

Keyword

nonn,tabl

Author

David Callan, Nov 27 2004

Status

approved