3,2

Row sums give the little Schroeder numbers (A001003). Column 3 (first column, corresponding to k=3) gives A010683.

Number of short bushes (i.e. ordered trees with no vertices of outdegree 1) with n-1 leaves and having root of degree k-1. Example: T(5,3)=7 because, in addition to the five binary trees with 6 edges we have (i) two edges rb, rc hanging from the root r with three edges hanging from vertex b and (ii) two edges rb, rc hanging from the root r with three edges hanging from vertex c.

P. Flajolet and M. Noy, Analytic combinatorics of non-crossing configurations, Discrete Math., 204, 1999, 203-229.

J.-C. Novelli and J.-Y. Thibon, Noncommutative Symmetric Functions and Lagrange Inversion

T(n, k)=[(k-1)/(n-k)]sum(2^j*binomial(n-2, n-k-1-j)*binomial(n-k, j), j=0..n-k-1). G.f.=t^3*z^3*S^2/(1-tzS), where S = [1+z-sqrt(1-6*z+z^2)]/(4z) is the g.f. of the little Schroeder numbers (A001003).

T(5,4)=3 because the dissections of the pentagon ABCDEA that have a quadrilateral over the base AB are obtained by the diagonals (i) CE, (ii) AD and (iii) BD, respectively.

1; 2,1; 7,3,1; 28,12,4,1; 121,52,18,5,1;

a := proc(n, k) if k=0 or k=1 or k=2 then 0 elif k=n then 1 elif k<n then (k-1)*sum(2^j*binomial(n-2, n-k-1-j)*binomial(n-k, j), j=0..n-k-1)/(n-k) else 0 fi end:seq(seq(a(n, k), k=3..n), n=3..13);

Cf. A001003, A010683.

Sequence in context: A134929 A160413 A136535 this_sequence A125697 A090699 A120903

Adjacent sequences: A091367 A091368 A091369 this_sequence A091371 A091372 A091373

nonn,tabl

Emeric Deutsch (deutsch(AT)duke.poly.edu), Mar 01 2004