|
| |
|
|
A253938
|
|
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).
|
|
2
|
|
|
|
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, 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, 50, 60, 45, 20, 15, 24, 27, 24, 15, 1, 2, 3, 4, 5, 6, 0, 0, 0, 0, 0, 0, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,7
|
|
|
COMMENTS
|
For each value of n there is a triangular array. For each triangle array level the elements equal the sum of 1 to n.
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.
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.
For a given n and p=1 to n: F(n,p,p) = Pascal triangle row for (A007318) C(n-1,p-1).
For a given n (n > 1): F(n,n-1,r) = r.
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.
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
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
|
|
|
LINKS
|
|
|
|
FORMULA
|
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(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).
The row multiplier array M(p) is
1: 1
2: (n-1)/(1!*2!)
3: [(n-1)(n-2)]/(2!*3!)
4: [(n-1)(n-2)(n-3)]/(3!*4!)
...
p: [(n-1)(n-2)...(n-p+1)]/[(p-1)!*p!]
...
The coefficient array D(p,r) uses a recursive formula except for D(p,1)=1 and D(p,p)= r!:
p\r 1 2 3 4 5 ...
1: 1
2: 1 2!
3: 1 4 3!
4: 1 6 18 4!
5: 1 8 36 96 5!
...
p: 1 D(p,r)=r*D(p-1,r-1)+D(p-1,r) ... r!
...
The numeric array I(p,r) is
p\r 1 2 3 4 ....r
1: 1
2: (n-2) 1
3: (n-2)(n-3) (n-3) 1
4: (n-2)(n-3)(n-4) (n-3)(n-4) (n-4) 1
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
|
|
|
EXAMPLE
|
F(4,2,2) = M(2)*D(2,2)*I(2,2) = (4-1)/(1!*2!)*2!*1 = 3.
There are 3 Dyck paths of semilength 4 with 2 peaks and 2 returns to the x axis.
{(uudduudd)(uduuuddd)(uuudddud)}
for n=4:
p\r 1 2 3 4
1: 1
2: 3 3
3: 1 2 3
4: 0 0 0 1
F(7,4,3) = M(4)*D(4,3)* I(4,3) = [(7-1)(7-2)(7-3)]/(3!*4!)*18*(7-4) = 45.
There are 45 Dyck paths of semilength 7 with 4 peaks and 3 returns to the x axis.
for n=7:
p\r 1 2 3 4 5 6 7
1: 1
2: 15 6
3: 50 40 15
4: 50 60 45 20
5: 15 24 27 24 15
6: 1 2 3 4 5 6
7: 0 0 0 0 0 0 1
The following is the ordering (read by rows) for n=1 to n=5 given in the DATA section:
n, p\r 1 2 3 4 5
1, 1: 1
2, 1: 1
2, 2: 0 1
3, 1: 1
3, 2: 1 2
3, 3: 0 0 1
4, 1: 1
4, 2: 3 3
4, 3: 1 2 3
4, 4: 0 0 0 1
5, 1: 1
5, 2: 6 4
5, 3: 6 8 6
5, 4: 1 2 3 4
5, 5: 0 0 0 0 1
.........For a larger value of n.......... n=10:
p\r 1 2 3 4 5 6 7 8 9 10
1: 1
2: 36 9
3: 336 168 36
4: 1176 882 378 84
5: 1764 1764 1134 504 126
6: 1176 1470 1260 840 420 126
7: 336 504 540 480 360 216 84
8: 36 63 81 90 90 81 63 36
9: 1 2 3 4 5 6 7 8 9
10: 0 0 0 0 0 0 0 0 0 1
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,tabf,uned
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
