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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A306364 Triangular array of the number of binary, rooted, leaf-labeled tree topologies with n leaves and k cherries, n >= 2, 1 <= k <= floor(n/2). 2
1, 3, 12, 3, 60, 45, 360, 540, 45, 2520, 6300, 1575, 20160, 75600, 37800, 1575, 181440, 952560, 793800, 99225, 1814400, 12700800, 15876000, 3969000, 99225, 19958400, 179625600, 314344800, 130977000, 9823275 (list; graph; refs; listen; history; text; internal format)
OFFSET

2,2

COMMENTS

A cherry is an internal node with exactly two descendant leaves. Each binary, rooted, leaf-labeled tree topology with n leaves has at least 1 cherry and at most floor(n/2) cherries.

LINKS

Table of n, a(n) for n=2..31.

N. A. Rosenberg, Enumeration of lonely pairs of gene trees and species trees by means of antipodal cherries, Adv. Appl. Math. 102 (2019), 1-17.

T. Wu, K. P. Choi, On joint subtree distributions under two evolutionary models, Theor. Pop. Biol. 108 (2016), 13-23.

FORMULA

T(n,k) = n! (n-2)! / (2^(2k-1) (n-2k)! k! (k-1)! ).

EXAMPLE

For n=4 leaves A, B, C, and D, a(4,1)=12 and a(4,2)=3. The 12 labeled topologies with 1 cherry are (((A,B),C),D), (((A,B),D),C), (((A,C),B),D), (((A,C),D),B), (((A,D),B),C), (((A,D),C),B), (((B,C),A),D), (((B,C),D),A), (((B,D),A),C), (((B,D),C),A), (((C,D),A),B), (((C,D),B),A). The 3 labeled topologies with 2 cherries are ((A,B),(C,D)), ((A,C),(B,D)), ((A,D),(B,C)).

Triangular array begins:

        1;

        3;

       12,        3;

       60,       45;

      360,      540,       45;

     2520,     6300,     1575;

    20160,    75600,    37800,    1575;

   181440,   952560,   793800,   99225;

  1814400, 12700800, 15876000, 3969000, 99225;

MATHEMATICA

Table[n! (n - 2)!/(2^(2 k - 1) (n - 2 k)! k! (k - 1)!), {n, 2, 15}, {k, 1, Floor[n/2]}]

CROSSREFS

Row sums equal A001147(n-1).

Column k=1 gives A001710.

T(2n,n) gives A079484(n-1).

Sequence in context: A170857 A227106 A085296 * A214401 A009781 A266913

Adjacent sequences:  A306361 A306362 A306363 * A306365 A306366 A306367

KEYWORD

nonn,tabf

AUTHOR

Noah A Rosenberg, Feb 10 2019

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 June 20 05:01 EDT 2019. Contains 324229 sequences. (Running on oeis4.)