%I #16 May 03 2021 02:09:11
%S 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,
%T 297,90,28,9,3,1,1,3432,1001,297,90,28,9,3,1,1,11934,3432,1001,297,90,
%U 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
%N Triangle read by rows: T(n,k) is the number of Dyck n-paths whose first descent has length k.
%C 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.
%C 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.
%C 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).
%C 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.
%C 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.
%C Essentially, Riordan array (f(x), x) where f(x) is the g.f. of A071724. - _Philippe Deléham_, Feb 07 2014
%H G. C. Greubel, <a href="/A100537/b100537.txt">Rows n = 1..50 of the triangle, flattened</a>
%F 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.
%F G.f.: (1-x)*y*(1 - 2*x - sqrt(1-4*x))/(2*x*(1 - x*y)).
%F 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
%e Table begins
%e * k..1...2...3......
%e n
%e 1 |..1
%e 2 |..1...1
%e 3 |..3...1...1
%e 4 |..9...3...1...1
%e 5 |.28...9...3...1...1
%e 6 |.90..28...9...3...1...1
%e 7 |297..90..28...9...3...1...1
%e For example, UUDDUD has first descent of length 2 and T(3,1)=3 counts UUDUDD, UDUUDD, UDUDUD.
%t T[n_, k_]:= Boole[k==n] + 3*(n-k)*CatalanNumber[n-k]/(n-k+2);
%t Table[T[n, k], {n,0,12}, {k,0,n}]//Flatten (* _G. C. Greubel_, May 03 2021 *)
%o (Magma)
%o A100537:= func< n,k | k eq n select 1 else 3*(n-k)*Catalan(n-k)/(n-k+2) >;
%o [A100537(n,k): k in [0..n], n in [0..12]]; // _G. C. Greubel_, May 03 2021
%o (Sage)
%o def A100537(n,k): return bool(k==n) + 3*(n-k)*catalan_number(n-k)/(n-k+2)
%o flatten([[A100537(n,k) for k in (0..n)] for n in (0..12)]) # _G. C. Greubel_, May 03 2021
%Y Row sums are the Catalan numbers A000108.
%Y Each column is A071724.
%K nonn,tabl
%O 1,4
%A _David Callan_, Nov 27 2004