|
%I #80 Oct 08 2022 06:21:04
%S 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,
%T 66,30,10,6,0,1,622,432,220,96,40,12,7,0,1,2120,1466,744,328,130,51,
%U 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
%N Triangle T(n,k) giving number of Dyck paths of length 2n with exactly k hills (0 <= k <= n).
%C 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
%C 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
%C 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
%C 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
%C Inverse of Riordan array ((1-2x)/(1-x)^2,x(1-2x)/(1-x)^2); see A124394. - _Paul Barry_, Jan 27 2009
%C Triangle read by rows, product of A033184 and A130595 considered as infinite lower triangular arrays; A065600 = A033184*A130595. - _Philippe Deléham_, Dec 07 2009
%C 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
%C Also the convolution triangle of the Fine numbers A000957. - _Peter Luschny_, Oct 08 2022
%H Alois P. Heinz, <a href="/A065600/b065600.txt">Rows n = 0..200, flattened</a>
%H E. Barcucci, E. Pergola, R. Pinzani and S. Rinaldi, <a href="http://www.mat.univie.ac.at/~slc/wpapers/s46rinaldi.html">ECO method and hill-free generalized Motzkin paths</a>, Séminaire Lotharingien de Combinatoire, B46b (2001), 14 pp.
%H Naiomi Cameron, J. E. McLeod, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/McLeod/mcleod3.html">Returns and Hills on Generalized Dyck Paths</a>, Journal of Integer Sequences, Vol. 19, 2016, #16.6.1.
%H E. 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 E. Deutsch and L. Shapiro, <a href="http://dx.doi.org/10.1016/S0012-365X(01)00121-2">A survey of the Fine numbers</a>, Discrete Math., 241 (2001), 241-265.
%H Filippo Disanto, Andrea Frosini and Simone Rinaldi, Renzo Pinzani, <a href="http://www.seams-bull-math.ynu.edu.cn/downloadfile.jsp?filemenu=_200805&filename=The%20Combinatorics%20of%20Convex%20Permutominoes.pdf">The Combinatorics of Convex Permutominoes</a>, Southeast Asian Bulletin of Mathematics (2008) 32: 883-912.
%H S. Elizalde and I. Pak, <a href="http://dx.doi.org/10.1016/j.jcta.2003.10.009">Bijections for refined restricted permutations</a>, Journal of Combinatorial Theory Ser. A, 105, 2004, 207-219.
%H FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/StatisticsDatabase/St000117">The number of centered tunnels of a Dyck path.</a>
%H Shishuo Fu, Yaling Wang, <a href="https://arxiv.org/abs/1908.03912">Bijective recurrences concerning two Schröder triangles</a>, arXiv:1908.03912 [math.CO], 2019.
%H B. Hackl, H. Prodinger, <a href="https://arxiv.org/1704.03734">Growing and destroying Catalan-Stanley trees</a>, arxiv:1704.03734 [math.CO] (2017), proposition 2.1
%H R. Pemantle and M. C. Wilson, <a href="http://dx.doi.org/10.1137/050643866">Twenty Combinatorial Examples of Asymptotics Derived from Multivariate Generating Functions, SIAM Rev., 50 (2008), no. 2, 199-272. See p. 235
%H A. Robertson, D. Saracino and D. Zeilberger, <a href="http://arXiv.org/abs/math.CO/0203033">Refined restricted permutations</a>, arXiv:math/0203033 [math.CO], 2002.
%H <a href="/index/Lu#Lukasiewicz">Index entries for sequences related to Łukasiewicz</a>
%F See Maple line.
%F 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
%F 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
%F 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
%F 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
%F G.f.: 2 / (1 + 2*x + (1 - 4*x)^(1/2) - 2*x*y). - _Michael Somos_, Jun 01 2016
%e From _Philippe Deléham_, Feb 23 2012: (Start)
%e Triangle begins:
%e 1;
%e 0, 1;
%e 1, 0, 1;
%e 2, 2, 0, 1;
%e 6, 4, 3, 0, 1;
%e 18, 13, 6, 4, 0, 1;
%e 57, 40, 21, 8, 5, 0, 1; (End)
%e 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).
%p T := proc(n,k) if k<n then sum(i*binomial(k+i,i)*binomial(2*n-2*k-2*i,n-k)/(n-k-i), i=0..floor((n-k)/2)) elif k=n then 1 else 0 fi end:
%p # second Maple program:
%p b:= proc(x, y, t) option remember; expand(`if`(x=0, 1,
%p `if`(y>0, b(x-1, y-1, 0)*`if`(t*y=1, z, 1), 0)+
%p `if`(y<x-1, b(x-1, y+1, 1), 0)))
%p end:
%p T:= n-> (p-> seq(coeff(p, z, i), i=0..n))(b(n+n, 0$2)):
%p seq(T(n), n=0..12); # _Alois P. Heinz_, Nov 02 2017
%p # Uses function PMatrix from A357368. Adds a row above and a column to the left.
%p PMatrix(10, A000957); # _Peter Luschny_, Oct 08 2022
%t t[n_, k_] := If[ k<n , Sum[i*Binomial[k+i, i]*Binomial[2*n-2*k-2*i, n-k]/(n-k-i), {i, 0, Floor[(n-k)/2]}] , If[ k == n, 1, 0]]; Flatten[ Table[t[n, k], {n, 0, 11}, {k, 0, n}]] (* _Jean-François Alcover_, Dec 14 2011, after Maple *)
%t 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 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 *)
%o (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 */
%Y First columns are A000957, A065601, A294527.
%K nonn,tabl,easy,nice
%O 0,7
%A _N. J. A. Sloane_, Dec 02 2001
%E More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 29 2003
|
