0,8

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*T(n,k),k=0..n) = binom(2n-2,n-1).

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).

T(n,k) is the number of Lukasiewicz paths of length n having k level steps (i.e., (1,0)). A Lukasiewicz 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

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.

Exponential Riordan array [exp(x)*(Bessel_I(0,2x)-Bessel_I(1,2x)),x]. - Paul Barry, Mar 03 2011

T(n,k) is the number of ordered trees having n edges and exactly k nodes with one child. - Geoffrey Critzer, Feb 25 2013

From Tom Copeland, Nov 01 and 04 2014: (Start)

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,

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,

Inverse O.g.f.: H^(-1)(x,t) = x*(1-x) / [1 + (t-1)x(1-x)] = P[C(x),t-1].

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(t), where 1/w(t)= e.g.f. of first column for the Motzkin numbers in A005043.

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). (End)

R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison and Wesley, 1996, page 254 (first edition)

Table of n, a(n) for n=0..67.

David Callan, On conjugates for set partitions and integer compositions , arXiv:math/0508052 [math.CO], 2005.

A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.

F. Yano and H. Yoshida, Some set partition statistics in non-crossing partitions and generating functions, Discr. Math., 307 (2007), 3147-3160.

T(n, k) = [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)) 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.

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

Sum_{k, 0<=k<=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

Sum_{k, 0<=k<=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

E.g.f.: exp(x+xy)*(Bessel_I(0,2x)-Bessel_I(1,2x)). - Paul Barry, Mar 10 2010

From Tom Copeland, Nov 03 and 06 2014: (Start)

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).

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.

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. (End)

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).

{{1}, {0, 1}, {1, 0, 1}, {1, 3, 0, 1}, {3, 4, 6, 0, 1}, {6, 15, 10, 10, 0, 1}}

Triangle begins

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, 105, 126, 105, 35, 21, 0, 1

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);

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 *)

Cf. A000108, A005043.

Cf. A124644, A026378, A001700, A005773, A126930, A210736, A007317, A064613, A104455, A030528, A104597.

Sequence in context: A169940 A121481 A121469 * A127158 A112367 A035623

Adjacent sequences:  A091864 A091865 A091866 * A091868 A091869 A091870

nonn,tabl

Emeric Deutsch, Mar 10 2004

approved