login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A108838 Triangle of Dyck paths counted by number of long interior inclines. 5
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 (list; table; graph; refs; listen; history; text; internal format)
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.

E. Deutsch, Dyck path enumeration, Discrete Math., 204, 1999, 167-202.

T. Doslic, Handshakes across a (round) table, JIS 13 (2010) #10.2.7.

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

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

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.

Sequence in context: A333907 A274486 A227961 * A318176 A105070 A154578

Adjacent sequences:  A108835 A108836 A108837 * A108839 A108840 A108841

KEYWORD

nonn,tabl

AUTHOR

David Callan, Jul 25 2005

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 10 21:03 EDT 2021. Contains 342856 sequences. (Running on oeis4.)