login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A091320 Triangle read by rows: T(n,k) is the number of noncrossing trees with n edges and k leaves. 2
1, 2, 1, 4, 7, 1, 8, 30, 16, 1, 16, 104, 122, 30, 1, 32, 320, 660, 365, 50, 1, 64, 912, 2920, 2875, 903, 77, 1, 128, 2464, 11312, 17430, 9856, 1960, 112, 1, 256, 6400, 39872, 88592, 78974, 28560, 3864, 156, 1, 512, 16128, 130944, 396480, 512316, 294042, 73008, 7074, 210, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

T(n,k) is the number of even trees with 2n edges and k-1 jumps. An even tree is an ordered tree in which each vertex has an even outdegree. In the preorder traversal of an ordered tree, any transition from a node at a deeper level to a node on a strictly higher level is called a jump. - Emeric Deutsch, Jan 19 2007

LINKS

Andrew Howroyd, Table of n, a(n) for n = 1..1275

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

M. Noy, Enumeration of noncrossing trees on a circle, Discrete Math., 180, 301-313, 1998.

FORMULA

T(n, k) = (1/n)*binomial(n, k)*Sum_{j=0..n} 2^(n+1-2k+j)*binomial(n, j)*binomial(n-k, k-1-j).

G.f.: G(t, z) satisfies z*G^3 - (1 + z - t*z)*G + 1 = 0.

EXAMPLE

Triangle starts:

   1;

   2,   1;

   4,   7,   1;

   8,  30,  16,   1;

  16, 104, 122,  30,  1;

  32, 320, 660, 365, 50, 1;

  ...

MAPLE

T := proc(n, k) if k=n then 1 else (1/n)*binomial(n, k)*sum(2^(n+1-2*k+j)*binomial(n, j)*binomial(n-k, k-1-j), j=0..n) fi end: seq(seq(T(n, k), k=1..n), n=1..12);

MATHEMATICA

T[n_, k_] := 1/n Binomial[n, k] Sum[2^(n+1-2k+j) Binomial[n, j] Binomial[n-k, k-1-j], {j, 0, n}];

Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-Fran├žois Alcover, Jul 29 2018 *)

PROG

(PARI) T(n, k) = binomial(n, k)*sum(j=0, n, 2^(n+1-2*k+j)*binomial(n, j)*binomial(n-k, k-1-j))/n; \\ Andrew Howroyd, Nov 06 2017

CROSSREFS

Row sums give A001764.

Column 2 is A276289.

Cf. A072247.

Sequence in context: A221499 A059579 A261763 * A225468 A048787 A030102

Adjacent sequences:  A091317 A091318 A091319 * A091321 A091322 A091323

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, Feb 24 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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 13 11:09 EST 2018. Contains 317133 sequences. (Running on oeis4.)