A091370 Triangle read by rows: T(n,k) is the number of dissections of a convex n-gon by nonintersecting diagonals, having a k-gon over a fixed edge (base).

1, 2, 1, 7, 3, 1, 28, 12, 4, 1, 121, 52, 18, 5, 1, 550, 237, 84, 25, 6, 1, 2591, 1119, 403, 125, 33, 7, 1, 12536, 5424, 1976, 630, 176, 42, 8, 1, 61921, 26832, 9860, 3206, 930, 238, 52, 9, 1, 310954, 134913, 49912, 16470, 4908, 1316, 312, 63, 10, 1

Offset: 3

Author

Emeric Deutsch, Mar 01 2004

Keywords

• nonn
• tabl

Comments

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.

Examples

			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.
Triangle starts:
1;
2,1;
7,3,1;
28,12,4,1;
121,52,18,5,1;
...
		

Links

• P. Flajolet and M. Noy, Analytic combinatorics of non-crossing configurations, Discrete Math., 204, 203-229, 1999.
• J.-C. Novelli and J.-Y. Thibon, Noncommutative Symmetric Functions and Lagrange Inversion, arXiv:math/0512570 [math.CO], 2005-2006.

Crossrefs

Cf. A001003, A010683.

Programs

Maple

a := proc(n,k) if k=0 or k=1 or k=2 then 0 elif k=n then 1 elif k hypergeom([1-N, N+2], [2], -1);
f := n -> 1+add(simplify(c(i))*x^i,i=1..n):
s := j -> coeff(series(f(j)^2/(1-x*t*f(j)),x,j+1),x,j):
seq(coeff(s(n),t,j),j=0..n) end:
seq(T_row(n), n=0..9); # Peter Luschny, Oct 30 2015

Mathematica

T[n_, n_] = 1; 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}];
Table[T[n, k], {n, 3, 13}, {k, 3, n}] // Flatten (* Jean-François Alcover, Nov 24 2017 *)

Formula

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-t*z*S), where S = (1+z-sqrt(1-6*z+z^2))/(4*z) is the g.f. of the little Schroeder numbers (A001003).