A108838 Triangle of Dyck paths counted by number of long interior inclines.

2, 3, 2, 4, 8, 2, 5, 20, 15, 2, 6, 40, 60, 24, 2, 7, 70, 175, 140, 35, 2, 8, 112, 420, 560, 280, 48, 2, 9, 168, 882, 1764, 1470, 504, 63, 2, 10, 240, 1680, 4704, 5880, 3360, 840, 80, 2, 11, 330, 2970, 11088, 19404, 16632, 6930, 1320, 99, 2

Offset: 2

Author

David Callan, Jul 25 2005

Keywords

• nonn
• tabl

Comments

T(n,k) is the number of Dyck n-paths (A000108) containing k long interior inclines. An incline is an ascent or a descent where an ascent (resp. descent) is a maximal sequence of contiguous upsteps (resp. downsteps). An incline is long if it consists of at least 2 steps and is interior if it does not start or end the path.

T(n,k) is the number of Dyck (n+1)-paths whose last descent has length 2 and which contain n-k peaks. For example T(3,0)=3 counts UUDUDUDD, UDUUDUDD, UDUDUUDD. - David Callan, Jul 03 2006

T(n,k) is the number of parallelogram polyominoes of semiperimeter n+1 having k corners. - Emeric Deutsch, Oct 09 2008

T(n,k) is the number of rooted ordered trees with n non-root nodes and k leaves; see example. - Joerg Arndt, Aug 18 2014

Examples

			Table begins
\ k..0....1....2....3....4....5
n\
2 |..2
3 |..3....2
4 |..4....8....2
5 |..5...20...15....2
6 |..6...40...60...24....2
7 |..7...70..175..140...35....2
The paths UUUDDD, UUDUDD, UDUDUD have no long interior inclines; so T(3,0)=3.
From _Joerg Arndt_, Aug 18 2014: (Start)
The rooted ordered trees with n=3 nodes, as (preorder-) level sequences, together with their number of leaves, and an ASCII rendering, are:
:
:     1:  [ 0 1 1 1 ]   2
:  O--o
:  .--o
:  .--o
:
:     2:  [ 0 1 1 2 ]   2
:  O--o
:  .--o--o
:
:     3:  [ 0 1 2 1 ]   1
:  O--o--o
:  .--o
:
:     4:  [ 0 1 2 2 ]   1
:  O--o--o
:     .--o
:
:     5:  [ 0 1 2 3 ]   1
:  O--o--o--o
:
This gives [3, 2], row n=3 of the triangle.
(End)
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 2..11176 (rows 2 <= n <= 150, flattened)
• Per Alexandersson, Svante Linusson, Samu Potka, and Joakim Uhlin, Refined Catalan and Narayana cyclic sieving, arXiv:2010.11157 [math.CO], 2020.
• Tewodros Amdeberhan, Victor H. Moll, and Christophe Vignat, A probabilistic interpretation of a sequence related to Narayana Polynomials, arXiv:1202.1203 [math.NT], 2012. - From _N. J. A. Sloane_, Sep 19 2012
• Tewodros Amdeberhan, Victor H. Moll, and Christophe Vignat, A probabilistic interpretation of a sequence related to Narayana Polynomials, Online Journal of Analytic Combinatorics, Issue 8, 2013.
• David Callan, Some Identities for the Catalan and Fine Numbers, arXiv:math/0502532 [math.CO], 2005.
• M. Delest, J. P. Dubernard, and I. Dutour, Parallelogram polyominoes and corners, J. Symbolic Computation, 20(1995),503-515. [From _Emeric Deutsch_, Oct 09 2008]
• M. P. Delest, D. Gouyou-Beauchamps, and B. Vauquelin, Enumeration of parallelogram polyominoes with given bond and site parameter, Graphs and Combinatorics, 3 (1987), 325-339.
• Emeric Deutsch, Dyck path enumeration, Discrete Math., 204, 1999, 167-202.
• T. Doslic, Handshakes across a (round) table, JIS 13 (2010) #10.2.7.
• Sergi Elizalde, Johnny Rivera Jr., and Yan Zhuang, Counting pattern-avoiding permutations by big descents, arXiv:2408.15111 [math.CO], 2024. See pp. 6, 18, 27.

Crossrefs

Row sums are the Catalan numbers A000108. Column k=1 is A007290, k=2 is A006470. The Narayana numbers A001263 count Dyck paths by number of long nonterminal inclines. A091894 (Touchard distribution) counts Dyck paths by number of long nonterminal descents.

Cf. A145596.

Programs

Maple

T:=(n,k)->2*binomial(n-1,k)*binomial(n,k+2)/(n-1): for n from 2 to 11 do seq(T(n,k),k=0..n-2) od; # yields sequence in triangular form; Emeric Deutsch, Jul 23 2006

Mathematica

T[n_, 0] = n;
T[n_, k_] := T[n, k] = If[k == n-2, 2, T[n, k-1](n-k-1)(n-k)/(k(k+2))];
Table[T[n, k], {n, 2, 11}, {k, 0, n-2}] // Flatten (* Jean-François Alcover, Jul 27 2018, after Werner Schulte *)

Formula

T(n, k) = 2*binomial(n+1, k+2)*binomial(n-2, k)/(n+1).

G.f.: G(z, t) = Sum_{n>=1, k>=0} T(n, k)*z^n*t^k satisfies z - ( (1-z)^2 - (2*t-t^2)*z^2 )*G + (t^2*z)*G^2 = 0.

G.f.: 1+z(1+r)^2, where r=r(t,z) is the Narayana function defined by (1+r)*(1+tr)z=r, r(t,0)=0. - Emeric Deutsch, Jul 23 2006

For n >= 0, the row polynomials Sum_{k=0..n} T(n+2,k)*x^k = (2/(n+1))*(1-x)^n*P(n,2,1,(1+x)/(1-x)), where P(n,a,b,x) denotes the Jacobi polynomial. It follows that the row polynomials have negative real zeros. - Peter Bala, Jan 21 2008

The trivariate g.f. G=G(t,s,z) of Dyck paths with respect to number of DUU's (marked by t), number of DDU's (marked by s) and semilength (marked by z) satisfies G = 1 + z*G + z^2*(1+t*(G-1))*(1+s*(G-1))/(1-z*(1+t*s*(G-1))) (the number of long interior inclines is equal to the number of DUU and DDU's). - Emeric Deutsch, Oct 09 2008

Recurrence: T(n, k) = T(n, k-1)*(n-1-k)*(n-k)/(k*(k+2)) for k > 0 and n >= 2. - Werner Schulte, Jan 04 2017

The array can be extended to negative values of n: T(-n,k) = 2*binomial(-n+1, k+2)*binomial(-n-2, k)/(-n+1) = -A145596(n+k,k+1) for n >= 2. - Peter Bala, Apr 26 2022