|
%I #94 May 12 2017 09:29:27
%S 1,0,1,1,0,1,1,3,0,1,3,4,6,0,1,6,15,10,10,0,1,15,36,45,20,15,0,1,36,
%T 105,126,105,35,21,0,1,91,288,420,336,210,56,28,0,1,232,819,1296,1260,
%U 756,378,84,36,0,1,603,2320,4095,4320,3150,1512,630,120,45,0,1,1585,6633,12760,15015,11880,6930,2772,990,165,55,0,1
%N Triangle read by rows: T(n,k) = number of Dyck paths of semilength n having k peaks at odd height.
%C Number of ordered trees with n edges having k leaves at odd height. Row sums are the Catalan numbers (A000108). T(n,0)=A005043(n). Sum_{k=0..n} k*T(n,k) = binomial(2n-2,n-1).
%C T(n,k)=number of Dyck paths of semilength n and having k ascents of length 1 (an ascent is a maximal string of consecutive up steps). Example: T(4,2)=6 because we have UdUduud, UduuddUd, uuddUdUd, uudUdUdd, UduudUdd and uudUddUd (the ascents of length 1 are indicated by U instead of u).
%C T(n,k) is the number of Łukasiewicz paths of length n having k level steps (i.e., (1,0)). 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(4,1)=4 because we have HU(2)DD, U(2)HDD, U(2)DHD and U(2)DDH, where H=(1,0), U(1,1), U(2)=(1,2) and D=(1,-1). - _Emeric Deutsch_, Jan 06 2005
%C T(n,k) = number of noncrossing partitions of [n] containing k singleton blocks. Also, T(n,k) = number of noncrossing partitions of [n] containing k adjacencies. An adjacency is an occurrence of 2 consecutive integers in the same block (here 1 and n are considered consecutive). In fact, the statistics # singletons and # adjacencies have a symmetric joint distribution.
%C Exponential Riordan array [e^x*(Bessel_I(0,2x)-Bessel_I(1,2x)),x]. - _Paul Barry_, Mar 03 2011
%C T(n,k) is the number of ordered trees having n edges and exactly k nodes with one child. - _Geoffrey Critzer_, Feb 25 2013
%C From _Tom Copeland_, Nov 01 and 04 2014: (Start)
%C Summing the coeff. of the partitions in A134264 for a Lagrange inversion formula (see also A249548) containing (h_1)^k = (1')^k gives this triangle, so this array's o.g.f. H(x,t) = x + t * x^2 + (1 + t^2) * x^3 ... is the inverse of the o.g.f. of A104597 with a sign change, i.e., H^(-1)(x,t) = (x-x^2) / [1 + (t-1)(x-x^2)] = Cinv(x)/[1 + (t-1)Cinv(x)] = P[Cinv(x),t-1] where Cinv(x)= x * (1-x) is the inverse of C(x) = [1-sqrt(1-4*x)]/2, an o.g.f. for the Catalan numbers A000108, and P(x,t) = x/(1+t*x) with inverse Pinv(x,t) = -P(-x,t) = x/(1-t*x). Therefore,
%C O.g.f.: H(x,t) = C[Pinv(x,t-1)] = C[P(x,1-t)] = C[x/(1-(t-1)x)] = {1-sqrt[1-4*x/(1-(t-1)x)]}/2 (for A091867). Reprising,
%C Inverse O.g.f.: H^(-1)(x,t) = x*(1-x) / [1 + (t-1)x(1-x)] = P[Cinv(x),t-1].
%C From general arguments in A134264, the row polynomials are an Appell sequence with lowering operator d/dt, having the umbral property (p(.,t)+a)^n=p(n,t+a) with e.g.f. = e^(x*t)/w(x), where 1/w(x)= e.g.f. of first column for the Motzkin numbers in A005043. (Mislabeled argument corrected on Jan 31 2016.)
%C Cf. A124644 (t-shifted polynomials), A026378 (t=-4), A001700 (t=-3), A005773 (t=-2), A126930 (t=-1) and A210736 (t=-1, a(0)=0, unsigned), A005043 (t=0), A000108 (t=1), A007317 (t=2), A064613 (t=3), A104455 (t=4), A030528 (for inverses).
%C (End)
%C The sequence of binomial transforms A126930, A005043, A000108, ... in the above comment appears in A126930 and the link therein to a paper by F. Fite et al. on page 42. - _Tom Copeland_, Jul 23 2016
%D R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison and Wesley, 1996, page 254 (first edition)
%H Alois P. Heinz, <a href="/A091867/b091867.txt">Rows n = 0..200, flattened</a>
%H David Callan, <a href="http://arxiv.org/abs/math/0508052">On conjugates for set partitions and integer compositions </a>, arXiv:math/0508052 [math.CO], 2005.
%H A. Sapounakis, I. Tasoulas and P. Tsikouras, <a href="http://dx.doi.org/10.1016/j.disc.2007.03.005">Counting strings in Dyck paths</a>, Discrete Math., 307 (2007), 2909-2924.
%H F. Yano and H. Yoshida, <a href="http://dx.doi.org/10.1016/j.disc.2007.03.050">Some set partition statistics in non-crossing partitions and generating functions</a>, Discr. Math., 307 (2007), 3147-3160.
%F T(n, k) = [binomial(n+1, k)/(n+1)]*Sum_{j=1..floor((n-k)/2)} binomial(n+1-k, j)*binomial(n-k-j-1, j-1) for k<n; T(n, n) = 1; T(n, k) = 0 for k>n. G.f.=G=G(t, z) satisfies z(1+z-tz)G^2-(1+z-tz)G+1=0. T(n, k)=r(n-k)*binomial(n, k), where r(n)=A005043(n) are the Riordan numbers.
%F G.f.: 1/(1-xy-x^2/(1-x-xy-x^2/(1-x-xy-x^2/(1-x-xy-x^2/(1-... (continued fraction). - _Paul Barry_, Aug 03 2009
%F Sum_{k=0..n} T(n,k)*x^k = A126930(n), A005043(n), A000108(n), A007317(n), A064613(n), A104455(n) for x = -1,0,1,2,3,4 respectively. - _Philippe Deléham_, Dec 03 2009
%F Sum_{k=0..n} (-1)^(n-k)*T(n,k)*x^k = A168491(n), A099323(n+1), A001405(n), A005773(n+1), A001700(n), A026378(n+1), A005573(n), A122898(n) for x = -1, 0, 1, 2, 3, 4, 5, 6 respectively. - _Philippe Deléham_, Dec 03 2009
%F E.g.f.: e^(x+xy)*(Bessel_I(0,2x)-Bessel_I(1,2x)). - _Paul Barry_, Mar 10 2010
%F From _Tom Copeland_, Nov 03 and 06 2014: (Start)
%F O.g.f.: H(x,t) = {1-sqrt[1-4x/(1-(t-1)x)]}/2 (shifted index, as given in Copeland's comment, see comp. inverse there).
%F H(x,t)= x / [1-(C.+(t-1))x] = Sum_{n>=1} (C.+ (t-1))^(n-1)*x^n umbrally, e.g., (a.+b.)^2 = a_0*b_2 + 2 a_1*b1_+ a_0*b_2, where (C.)^n = C_n are the Catalan numbers (1,1,2,5,14,..) of A000108.
%F This shows directly that the lowering operator for the polynomials is D=d/dt, i.e., D p(n,t)= D(C. + (t-1))^n = n * (C. + (t-1))^(n-1) = n*p(n-1,t), so that the polynomials form an Appell sequence, and that p(n,0) gives a Motzkin sum, or Riordan, number A005043.
%F (End)
%F T(n,k) = (-1)^(n+k)*binomial(n,k)*hypergeom([k-n,1/2],[2],4). - _Peter Luschny_, Jul 27 2016
%e T(4,2)=6 because we have (ud)uu(ud)dd, uu(ud)dd(ud), uu(ud)(ud)dd, (ud)(ud)uudd, (ud)uudd(ud) and uudd(ud)(ud) (here u=(1,1), d=(1,-1) and the peaks at odd height are shown between parentheses).
%e Triangle begins:
%e 1,
%e 0, 1,
%e 1, 0, 1,
%e 1, 3, 0, 1,
%e 3, 4, 6, 0, 1,
%e 6, 15, 10, 10, 0, 1,
%e 15, 36, 45, 20, 15, 0, 1,
%e 36, 105, 126, 105, 35, 21, 0, 1
%p T := proc(n,k) if k>n then 0 elif k=n then 1 else (binomial(n+1,k)/(n+1))*sum(binomial(n+1-k,j)*binomial(n-k-j-1,j-1),j=1..floor((n-k)/2)) fi end: seq(seq(T(n,k),k=0..n),n=0..12);
%p T := (n,k) -> (-1)^(n+k)*binomial(n,k)*hypergeom([-n+k,1/2],[2],4): seq(seq(simplify(T(n, k)), k=0..n), n=0..10); # _Peter Luschny_, Jul 27 2016
%p # alternative 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)*z^irem(t*y, 2), 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(2*n, 0$2)):
%p seq(T(n), n=0..16); # _Alois P. Heinz_, May 12 2017
%t nn=10;cy = ( 1 + x - x y - ( -4x(1+x-x y) + (-1 -x + x y)^2)^(1/2))/(2(1+x-x y)); Drop[CoefficientList[Series[cy,{x,0,nn}],{x,y}],1]//Grid (* _Geoffrey Critzer_, Feb 25 2013 *)
%t Table[Which[k == n, 1, k > n, 0, True, (Binomial[n + 1, k]/(n + 1)) Sum[Binomial[n + 1 - k, j] Binomial[n - k - j - 1, j - 1], {j, Floor[(n - k)/2]}]], {n, 0, 11}, {k, 0, n}] // Flatten (* _Michael De Vlieger_, Jul 25 2016 *)
%Y Cf. A000108, A001700, A005043, A005773, A007317, A026378, A030528, A064613, A104455, A104597, A124644, A126930, A210736.
%K nonn,tabl
%O 0,8
%A _Emeric Deutsch_, Mar 10 2004
|
