cp's OEIS Frontend

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

%I A108838 #64 Sep 01 2024 10:34:16
%S A108838 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,
%T A108838 280,48,2,9,168,882,1764,1470,504,63,2,10,240,1680,4704,5880,3360,840,
%U A108838 80,2,11,330,2970,11088,19404,16632,6930,1320,99,2
%N A108838 Triangle of Dyck paths counted by number of long interior inclines.
%C A108838 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.
%C A108838 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
%C A108838 T(n,k) is the number of parallelogram polyominoes of semiperimeter n+1 having k corners. - _Emeric Deutsch_, Oct 09 2008
%C A108838 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
%H A108838 Michael De Vlieger, <a href="/A108838/b108838.txt">Table of n, a(n) for n = 2..11176</a> (rows 2 <= n <= 150, flattened)
%H A108838 Per Alexandersson, Svante Linusson, Samu Potka, and Joakim Uhlin, <a href="https://arxiv.org/abs/2010.11157">Refined Catalan and Narayana cyclic sieving</a>, arXiv:2010.11157 [math.CO], 2020.
%H A108838 Tewodros Amdeberhan, Victor H. Moll, and Christophe Vignat, <a href="https://arxiv.org/abs/1202.1203">A probabilistic interpretation of a sequence related to Narayana Polynomials</a>, arXiv:1202.1203 [math.NT], 2012. - From _N. J. A. Sloane_, Sep 19 2012
%H A108838 Tewodros Amdeberhan, Victor H. Moll, and Christophe Vignat, <a href="https://web.math.rochester.edu/misc/ojac/vol8/68.pdf">A probabilistic interpretation of a sequence related to Narayana Polynomials</a>, Online Journal of Analytic Combinatorics, Issue 8, 2013.
%H A108838 David Callan, <a href="https://arxiv.org/abs/math/0502532">Some Identities for the Catalan and Fine Numbers</a>, arXiv:math/0502532 [math.CO], 2005.
%H A108838 M. Delest, J. P. Dubernard, and I. Dutour, <a href="http://dx.doi.org/10.1006/jsco.1995.1062">Parallelogram polyominoes and corners</a>, J. Symbolic Computation, 20(1995),503-515. [From _Emeric Deutsch_, Oct 09 2008]
%H A108838 M. P. Delest, D. Gouyou-Beauchamps, and B. Vauquelin, <a href="http://dx.doi.org/10.1007/BF01788555">Enumeration of parallelogram polyominoes with given bond and site parameter</a>, Graphs and Combinatorics, 3 (1987), 325-339.
%H A108838 Emeric Deutsch, <a href="http://dx.doi.org/10.1016/S0012-365X(98)00371-9">Dyck path enumeration</a>, Discrete Math., 204, 1999, 167-202.
%H A108838 T. Doslic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Doslic/doslic6.html">Handshakes across a (round) table</a>, JIS 13 (2010) #10.2.7.
%H A108838 Sergi Elizalde, Johnny Rivera Jr., and Yan Zhuang, <a href="https://arxiv.org/abs/2408.15111">Counting pattern-avoiding permutations by big descents</a>, arXiv:2408.15111 [math.CO], 2024. See pp. 6, 18, 27.
%F A108838 T(n, k) = 2*binomial(n+1, k+2)*binomial(n-2, k)/(n+1).
%F A108838 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.
%F A108838 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
%F A108838 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
%F A108838 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
%F A108838 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
%F A108838 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
%e A108838 Table begins
%e A108838 \ k..0....1....2....3....4....5
%e A108838 n\
%e A108838 2 |..2
%e A108838 3 |..3....2
%e A108838 4 |..4....8....2
%e A108838 5 |..5...20...15....2
%e A108838 6 |..6...40...60...24....2
%e A108838 7 |..7...70..175..140...35....2
%e A108838 The paths UUUDDD, UUDUDD, UDUDUD have no long interior inclines; so T(3,0)=3.
%e A108838 From _Joerg Arndt_, Aug 18 2014: (Start)
%e A108838 The rooted ordered trees with n=3 nodes, as (preorder-) level sequences, together with their number of leaves, and an ASCII rendering, are:
%e A108838 :
%e A108838 :     1:  [ 0 1 1 1 ]   2
%e A108838 :  O--o
%e A108838 :  .--o
%e A108838 :  .--o
%e A108838 :
%e A108838 :     2:  [ 0 1 1 2 ]   2
%e A108838 :  O--o
%e A108838 :  .--o--o
%e A108838 :
%e A108838 :     3:  [ 0 1 2 1 ]   1
%e A108838 :  O--o--o
%e A108838 :  .--o
%e A108838 :
%e A108838 :     4:  [ 0 1 2 2 ]   1
%e A108838 :  O--o--o
%e A108838 :     .--o
%e A108838 :
%e A108838 :     5:  [ 0 1 2 3 ]   1
%e A108838 :  O--o--o--o
%e A108838 :
%e A108838 This gives [3, 2], row n=3 of the triangle.
%e A108838 (End)
%p A108838 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
%t A108838 T[n_, 0] = n;
%t A108838 T[n_, k_] := T[n, k] = If[k == n-2, 2, T[n, k-1](n-k-1)(n-k)/(k(k+2))];
%t A108838 Table[T[n, k], {n, 2, 11}, {k, 0, n-2}] // Flatten (* _Jean-François Alcover_, Jul 27 2018, after _Werner Schulte_ *)
%Y A108838 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.
%Y A108838 Cf. A145596.
%K A108838 nonn,tabl
%O A108838 2,1
%A A108838 _David Callan_, Jul 25 2005