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).

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

Offset: 1

Author

Roger Ford, Jan 19 2015

Keywords

• nonn
• tabf
• uned

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.

Sum of terms in n-th triangle = A000108(n). - Alois P. Heinz, Feb 02 2015

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

Examples

			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
		

Links

• Alois P. Heinz, Triangles n = 1..40, flattened
• Emeric Deutsch, Dyck path enumeration, Discrete Math., 204, 1999, 167-202. See section 6.5.

Crossrefs

Cf. A000108, A001263, A007318, A033184.

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