The OEIS is supported by the many generous donors to the OEIS Foundation.
%I #57 Jan 29 2025 07:55:16
%S 1,1,0,1,1,1,2,0,0,1,1,3,3,1,2,3,0,0,0,1,1,6,4,6,8,6,1,2,3,4,0,0,0,0,
%T 1,1,10,5,20,20,10,10,15,15,10,1,2,3,4,5,0,0,0,0,0,1,1,15,6,50,40,15,
%U 50,60,45,20,15,24,27,24,15,1,2,3,4,5,6,0,0,0,0,0,0,1
%N A pyramid F(n,p,r) of successive triangular arrays read by rows, relating Dyck path peaks and returns to the x axis (n = semilength of Dyck paths, p = number of peaks, r = returns to the x axis).
%C For each value of n there is a triangular array. For each triangle array level the elements equal the sum of 1 to n.
%C For given values of n and p with r=1 to p: the row sums of F(n,p,r) = Narayana triangle (A001263) T(n,p) for Dyck path peaks.
%C For given values of n and r with p=r to n: the column sums for F(n,p,r) = (A033184) a(n,r) for Dyck path returns to the x axis.
%C For a given n and p=1 to n: F(n,p,p) = Pascal triangle row for (A007318) C(n-1,p-1).
%C For a given n (n > 1): F(n,n-1,r) = r.
%C For a given n and p=1 to n-1: F(n,p,1) = Narayana triangle (A001263) T(n-1,p) for Dyck path peaks.
%C Sum of terms in n-th triangle = A000108(n). - _Alois P. Heinz_, Feb 02 2015
%C F(n,p,r) generates the same Dyck path tetrahedral array when the number of peaks (p) is replaced by the number of Up movements in odd numbered positions. Example: for F(5,3,2): Up=up movement in odd numbered position, u=up movement in even numbered position, d=down movement, _=return to the x axis UuUddd_Uudd_. - _Roger Ford_, Nov 02 2017
%C F(n,p,r) is also the number of ordered trees with n edges, p leaves, and root of degree r. - _Robin Houston_, Nov 03 2017
%H Alois P. Heinz, <a href="/A253938/b253938.txt">Triangles n = 1..40, flattened</a>
%H Emeric Deutsch, <a href="http://dx.doi.org/10.1016/S0012-365X(98)00371-9">Dyck path enumeration</a>, Discrete Math., 204, 1999, 167-202. See section 6.5.
%F F(n,p,r) = [r*(n-1)!*(n-r-1)!]/[p!*(p-r)!*(n-p)!(n-p-1)!], except if n=p=r then F(n,p,r) = 1. - _Roger Ford_, May 21 2016
%F F(n,p,r) is the product of a row multiplier array (M), a coefficient triangle array (D) and a numeric triangular array (I): F(n,p,r) = M(p)*D(p,r)*I(p,r).
%F The row multiplier array M(p) is
%F 1: 1
%F 2: (n-1)/(1!*2!)
%F 3: [(n-1)(n-2)]/(2!*3!)
%F 4: [(n-1)(n-2)(n-3)]/(3!*4!)
%F ...
%F p: [(n-1)(n-2)...(n-p+1)]/[(p-1)!*p!]
%F ...
%F The coefficient array D(p,r) uses a recursive formula except for D(p,1)=1 and D(p,p)= r!:
%F p\r 1 2 3 4 5 ...
%F 1: 1
%F 2: 1 2!
%F 3: 1 4 3!
%F 4: 1 6 18 4!
%F 5: 1 8 36 96 5!
%F ...
%F p: 1 D(p,r)=r*D(p-1,r-1)+D(p-1,r) ... r!
%F ...
%F The numeric array I(p,r) is
%F p\r 1 2 3 4 ....r
%F 1: 1
%F 2: (n-2) 1
%F 3: (n-2)(n-3) (n-3) 1
%F 4: (n-2)(n-3)(n-4) (n-3)(n-4) (n-4) 1
%F p: (n-2)(n-3)..(n-p) (n-3)(n-4)..(n-p) (n-4)(n-5)..(n-p) (n-5)(n-6)..(n-p) ....1
%e F(4,2,2) = M(2)*D(2,2)*I(2,2) = (4-1)/(1!*2!)*2!*1 = 3.
%e There are 3 Dyck paths of semilength 4 with 2 peaks and 2 returns to the x axis.
%e {(uudduudd)(uduuuddd)(uuudddud)}
%e for n=4:
%e p\r 1 2 3 4
%e 1: 1
%e 2: 3 3
%e 3: 1 2 3
%e 4: 0 0 0 1
%e F(7,4,3) = M(4)*D(4,3)* I(4,3) = [(7-1)(7-2)(7-3)]/(3!*4!)*18*(7-4) = 45.
%e There are 45 Dyck paths of semilength 7 with 4 peaks and 3 returns to the x axis.
%e for n=7:
%e p\r 1 2 3 4 5 6 7
%e 1: 1
%e 2: 15 6
%e 3: 50 40 15
%e 4: 50 60 45 20
%e 5: 15 24 27 24 15
%e 6: 1 2 3 4 5 6
%e 7: 0 0 0 0 0 0 1
%e The following is the ordering (read by rows) for n=1 to n=5 given in the DATA section:
%e n, p\r 1 2 3 4 5
%e 1, 1: 1
%e 2, 1: 1
%e 2, 2: 0 1
%e 3, 1: 1
%e 3, 2: 1 2
%e 3, 3: 0 0 1
%e 4, 1: 1
%e 4, 2: 3 3
%e 4, 3: 1 2 3
%e 4, 4: 0 0 0 1
%e 5, 1: 1
%e 5, 2: 6 4
%e 5, 3: 6 8 6
%e 5, 4: 1 2 3 4
%e 5, 5: 0 0 0 0 1
%e ...
%e For a larger value of n.......... n=10:
%e p\r 1 2 3 4 5 6 7 8 9 10
%e 1: 1
%e 2: 36 9
%e 3: 336 168 36
%e 4: 1176 882 378 84
%e 5: 1764 1764 1134 504 126
%e 6: 1176 1470 1260 840 420 126
%e 7: 336 504 540 480 360 216 84
%e 8: 36 63 81 90 90 81 63 36
%e 9: 1 2 3 4 5 6 7 8 9
%e 10: 0 0 0 0 0 0 0 0 0 1
%Y Cf. A000108, A001263, A007318, A033184.
%K nonn,tabf,uned,changed
%O 1,7
%A _Roger Ford_, Jan 19 2015