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,2

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.

Links

Table of n, a(n) for n=3..57.

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.

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

Example

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

Maple

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);
T_row := proc(n) local c, f, s;
c := N -> 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 *)

Crossrefs

Cf. A001003, A010683.

Sequence in context: A352247 A136535 A320579 * A125697 A090699 A214550

Adjacent sequences: A091367 A091368 A091369 * A091371 A091372 A091373

Keyword

nonn,tabl

Author

Emeric Deutsch, Mar 01 2004

Status

approved