cp's OEIS Frontend

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

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