login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 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 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: 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 26 12:00 EDT 2020. Contains 337371 sequences. (Running on oeis4.)