1,4

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.

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. Sum_{n>=1, k>=1}T(n, k)x^n*y^k = x*y+x^2*CatalanGF[x]^3/(1-x*y) where CatalanGF[x] = (1 - (1 - 4*x)^(1/2))/(2*x).

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.

Row sums are the Catalan numbers A000108. Each column is A071724.

Sequence in context: A034801 A102435 A152570 this_sequence A069605 A080510 A124496

Adjacent sequences: A100534 A100535 A100536 this_sequence A100538 A100539 A100540

nonn,tabl

David Callan (callan(AT)stat.wisc.edu), Nov 27 2004