

A091370


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


3



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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



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 n1 leaves and having root of degree k1. 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 noncrossing configurations, Discrete Math., 204, 203229, 1999.
J.C. Novelli and J.Y. Thibon, Noncommutative Symmetric Functions and Lagrange Inversion, arXiv:math/0512570 [math.CO], 20052006.


FORMULA

T(n, k) = [(k1)/(nk)]*sum(2^j*binomial(n2, nk1j)*binomial(nk, j), j=0..nk1).
G.f.: t^3*z^3*S^2/(1t*z*S), where S = (1+zsqrt(16*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 (k1)*sum(2^j*binomial(n2, nk1j)*binomial(nk, j), j=0..nk1)/(nk) 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([1N, N+2], [2], 1);
f := n > 1+add(simplify(c(i))*x^i, i=1..n):
s := j > coeff(series(f(j)^2/(1x*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 (* JeanFrançois Alcover, Nov 24 2017 *)


CROSSREFS

Cf. A001003, A010683.
Sequence in context: A197328 A136535 A320579 * A125697 A090699 A214550
Adjacent sequences: A091367 A091368 A091369 * A091371 A091372 A091373


KEYWORD

nonn,tabl


AUTHOR

Emeric Deutsch, Mar 01 2004


STATUS

approved



