|
%I #57 Apr 26 2022 11:57:05
%S 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 280,48,2,9,168,882,1764,1470,504,63,2,10,240,1680,4704,5880,3360,840,
%U 80,2,11,330,2970,11088,19404,16632,6930,1320,99,2
%N Triangle of Dyck paths counted by number of long interior inclines.
%C 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 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 T(n,k) is the number of parallelogram polyominoes of semiperimeter n+1 having k corners. - _Emeric Deutsch_, Oct 09 2008
%C 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 Michael De Vlieger, <a href="/A108838/b108838.txt">Table of n, a(n) for n = 2..11176</a> (rows 2 <= n <= 150, flattened)
%H 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 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 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 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 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 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 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 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.
%F T(n, k) = 2*binomial(n+1, k+2)*binomial(n-2, k)/(n+1).
%F 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 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 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 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 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 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 Table begins
%e \ k..0....1....2....3....4....5
%e n\
%e 2 |..2
%e 3 |..3....2
%e 4 |..4....8....2
%e 5 |..5...20...15....2
%e 6 |..6...40...60...24....2
%e 7 |..7...70..175..140...35....2
%e The paths UUUDDD, UUDUDD, UDUDUD have no long interior inclines; so T(3,0)=3.
%e From _Joerg Arndt_, Aug 18 2014: (Start)
%e The rooted ordered trees with n=3 nodes, as (preorder-) level sequences, together with their number of leaves, and an ASCII rendering, are:
%e :
%e : 1: [ 0 1 1 1 ] 2
%e : O--o
%e : .--o
%e : .--o
%e :
%e : 2: [ 0 1 1 2 ] 2
%e : O--o
%e : .--o--o
%e :
%e : 3: [ 0 1 2 1 ] 1
%e : O--o--o
%e : .--o
%e :
%e : 4: [ 0 1 2 2 ] 1
%e : O--o--o
%e : .--o
%e :
%e : 5: [ 0 1 2 3 ] 1
%e : O--o--o--o
%e :
%e This gives [3, 2], row n=3 of the triangle.
%e (End)
%p 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 T[n_, 0] = n;
%t T[n_, k_] := T[n, k] = If[k == n-2, 2, T[n, k-1](n-k-1)(n-k)/(k(k+2))];
%t Table[T[n, k], {n, 2, 11}, {k, 0, n-2}] // Flatten (* _Jean-François Alcover_, Jul 27 2018, after _Werner Schulte_ *)
%Y 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 Cf. A145596.
%K nonn,tabl
%O 2,1
%A _David Callan_, Jul 25 2005
|
