A065600 Triangle T(n,k) giving number of Dyck paths of length 2n with exactly k hills (0 <= k <= n).

1, 0, 1, 1, 0, 1, 2, 2, 0, 1, 6, 4, 3, 0, 1, 18, 13, 6, 4, 0, 1, 57, 40, 21, 8, 5, 0, 1, 186, 130, 66, 30, 10, 6, 0, 1, 622, 432, 220, 96, 40, 12, 7, 0, 1, 2120, 1466, 744, 328, 130, 51, 14, 8, 0, 1, 7338, 5056, 2562, 1128, 455, 168, 63, 16, 9, 0, 1, 25724, 17672, 8942, 3941, 1590, 602, 210, 76, 18, 10, 0, 1

Offset: 0

Author

N. J. A. Sloane, Dec 02 2001

Keywords

• nonn
• tabl
• easy
• nice

Comments

T(n,k) is the number of Łukasiewicz paths of length n having k level steps (i.e., (1,0)) on the x-axis. A Łukasiewicz path of length n is a path in the first quadrant from (0,0) to (n,0) using rise steps (1,k) for any positive integer k, level steps (1,0) and fall steps (1,-1) (see R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Univ. Press, Cambridge, 1999, p. 223, Exercise 6.19w; the integers are the slopes of the steps). Example: T(3,1)=2 because we have HUD and UDH, where H=(1,0), U(1,1) and D=(1,-1). - Emeric Deutsch, Jan 06 2005

The summand i*binomial(k+i,i)*binomial(2*n-2*k-2*i,n-k)/(n-k-i) in the Maple formula below counts Dyck n-paths containing k low peaks and k+i returns altogether. For example, with n=3, k=1, i=1, it counts the 2 paths UDUUDD, UUDDUD: each has k=1 low peaks and k+i=2 returns to ground level. - David Callan, Nov 02 2005

Renewal array for the Fine numbers: Riordan array (f(x)/x,f(x)) where f(x) is the g.f. for A000957. Row sums are the Catalan numbers A000108. - Paul Barry, Oct 30 2006, Jan 27 2009

T(n,k) is the number of 321-avoiding permutations of [n] having k fixed points. Example: T(4,2)=3 because we have 1243, 1324 and 2134. T(n,k) is the number of Dyck paths of semilength n having k centered tunnels. Example: T(4,2)=3 because we have UD(U)(U)(D)(D)UD, (U)UD(U)(D)UD(D) and (U)(U)UDUD(D)(D) (the extremities of the centered tunnels are shown between parentheses). - Emeric Deutsch, Sep 06 2007

Inverse of Riordan array ((1-2x)/(1-x)^2,x(1-2x)/(1-x)^2); see A124394. - Paul Barry, Jan 27 2009

Triangle read by rows, product of A033184 and A130595 considered as infinite lower triangular arrays; A065600 = A033184*A130595. - Philippe Deléham, Dec 07 2009

T(n,k) is the number of ordered, unlabeled, rooted trees with n+1 nodes that have exactly k subtrees of size 1. A subtree of size 1 is a subtree attached to the root that consists of only a single node. Cf. A000957 (column 1). - Geoffrey Critzer, Sep 16 2013

Also the convolution triangle of the Fine numbers A000957. - Peter Luschny, Oct 08 2022

Examples

			From _Philippe Deléham_, Feb 23 2012: (Start)
Triangle begins:
   1;
   0,  1;
   1,  0,  1;
   2,  2,  0,  1;
   6,  4,  3,  0,  1;
  18, 13,  6,  4,  0,  1;
  57, 40, 21,  8,  5,  0,  1; (End)
T(4,2)=3 because we have (UD)(UD)UUDD, (UD)UUDD(UD) and UUDD(UD)(UD), where U=(1,1), D=(1,-1) (the hills, i.e., peaks at level 1, are shown between parentheses).
		

Links

• Alois P. Heinz, Rows n = 0..200, flattened
• E. Barcucci, E. Pergola, R. Pinzani and S. Rinaldi, ECO method and hill-free generalized Motzkin paths, Séminaire Lotharingien de Combinatoire, B46b (2001), 14 pp.
• Naiomi Cameron, J. E. McLeod, Returns and Hills on Generalized Dyck Paths, Journal of Integer Sequences, Vol. 19, 2016, #16.6.1.
• E. Deutsch, Dyck path enumeration, Discrete Math., 204, 1999, 167-202.
• E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.
• Filippo Disanto, Andrea Frosini and Simone Rinaldi, Renzo Pinzani, The Combinatorics of Convex Permutominoes, Southeast Asian Bulletin of Mathematics (2008) 32: 883-912.
• S. Elizalde and I. Pak, Bijections for refined restricted permutations, Journal of Combinatorial Theory Ser. A, 105, 2004, 207-219.
• FindStat - Combinatorial Statistic Finder, The number of centered tunnels of a Dyck path.
• Shishuo Fu, Yaling Wang, Bijective recurrences concerning two Schröder triangles, arXiv:1908.03912 [math.CO], 2019.
• B. Hackl, H. Prodinger, Growing and destroying Catalan-Stanley trees, arxiv:1704.03734 [math.CO] (2017), proposition 2.1
• R. Pemantle and M. C. Wilson, Twenty Combinatorial Examples of Asymptotics Derived from Multivariate Generating Functions, SIAM Rev., 50 (2008), no. 2, 199-272. See p. 235.
• A. Robertson, D. Saracino and D. Zeilberger, Refined restricted permutations, arXiv:math/0203033 [math.CO], 2002.
• Index entries for sequences related to Łukasiewicz

Crossrefs

First columns are A000957, A065601, A294527.

Programs

Maple

T := proc(n,k) if k0, b(x-1, y-1, 0)*`if`(t*y=1, z, 1), 0)+
      `if`(y (p-> seq(coeff(p, z, i), i=0..n))(b(n+n, 0$2)):
seq(T(n), n=0..12);  # Alois P. Heinz, Nov 02 2017
# Uses function PMatrix from A357368. Adds a row above and a column to the left.
PMatrix(10, A000957); # Peter Luschny, Oct 08 2022

Mathematica

t[n_, k_] := If[ kJean-François Alcover, Dec 14 2011, after Maple *)
nn=10;g=(1-(1-4x)^(1/2))/2;CoefficientList[Series[x/(1-(g-x+y x)),{x,0,nn}],{x,y}]//Grid (* Geoffrey Critzer, Sep 16 2013 *)
T[ n_, k_] := If[ k < 0 || k > n, 0, Coefficient[ SeriesCoefficient[ Series[ 2 / (1 + 2*x + Sqrt[1 - 4*x] - 2*x*y), {x, 0, n}], {x, 0, n}], y, k]]; (* Michael Somos, Jun 01 2016 *)

PARI

{T(n, k) = if( k<0 || k>n, 0, polcoeff( polcoeff( 2 / (1 + 2*x + (1 - 4*x)^(1/2) - 2*x*y) + x * O(x^n), n), k))}; /* Michael Somos, Jun 01 2016 */

Formula

See Maple line.

G.f.: (1 - (1 - 4*x)^(1/2))/(x*(3 - y + (1 - 4*x)^(1/2)*(y-1))) = Sum_{n>=0, k>=0} T(n, k)x^n*y^k. - David Callan, Aug 17 2004

G.f.: 1/(1-xy-x^2/(1-2x-x^2/(1-2x-x^2/(1-2x-x^2/(1-.... (continued fraction). - Paul Barry, Jan 27 2009

G.f.: ((1-sqrt(1-4*x))/(3-sqrt(1-4*x)))^k = Sum_{n>=k} T(n+1,k+1)*x^n, where T(n,k) = (Sum_{i=0..n-k} (-1)^i*(k+i+1)*binomial(k+i,i)*binomial(2*n-k-i,n))/(n+1). - Vladimir Kruchinin, Dec 20 2011

T(n,k) = T(n-1,k-1) + Sum_{i>=0} T(n-1,k+1+i)*2^i. - Philippe Deléham, Feb 23 2012

G.f.: 2 / (1 + 2*x + (1 - 4*x)^(1/2) - 2*x*y). - Michael Somos, Jun 01 2016

Extensions

More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 29 2003