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

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A065600 Triangle T(n,k) giving number of Dyck paths of length 2n with exactly k hills (0 <= k <= n). 13
 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 (list; table; graph; refs; listen; history; text; internal format)
 OFFSET 0,7 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 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 A. Robertson, D. Saracino and D. Zeilberger, Refined restricted permutations, arXiv:math/0203033 [math.CO], 2002. 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 EXAMPLE 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). 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 MATHEMATICA t[n_, k_] := If[ 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 *) PROG (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 */ CROSSREFS First columns are A000957, A065601, A294527. Sequence in context: A089246 A291684 A105929 * A029583 A011289 A288387 Adjacent sequences:  A065597 A065598 A065599 * A065601 A065602 A065603 KEYWORD nonn,tabl,easy,nice AUTHOR N. J. A. Sloane, Dec 02 2001 EXTENSIONS More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 29 2003 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.

Last modified June 21 06:11 EDT 2021. Contains 345358 sequences. (Running on oeis4.)