OFFSET
2,1
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
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.
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
EXAMPLE
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)
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 *)
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
David Callan, Jul 25 2005
STATUS
approved