cp's OEIS Frontend

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

%I A306364 #24 Jan 03 2025 09:34:56
%S A306364 1,3,12,3,60,45,360,540,45,2520,6300,1575,20160,75600,37800,1575,
%T A306364 181440,952560,793800,99225,1814400,12700800,15876000,3969000,99225,
%U A306364 19958400,179625600,314344800,130977000,9823275
%N 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).
%C A306364 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.
%H A306364 Robert S. Maier, <a href="https://doi.org/10.1016/j.aam.2023.102485">Triangular recurrences, generalized Eulerian numbers, and related number triangles</a>, Adv. Appl. Math. 146 (2023), 102485.
%H A306364 Noah A. Rosenberg, <a href="https://doi.org/10.1016/j.aam.2018.09.001">Enumeration of lonely pairs of gene trees and species trees by means of antipodal cherries</a>, Adv. Appl. Math. 102 (2019), 1-17.
%H A306364 Taoyang Wu and Kwok Pui Choi, <a href="https://doi.org/10.1016/j.tpb.2015.11.004">On joint subtree distributions under two evolutionary models</a>, Theor. Pop. Biol. 108 (2016), 13-23.
%F A306364 T(n,k) = n! (n-2)! / (2^(2k-1) (n-2k)! k! (k-1)! ).
%e A306364 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)).
%e A306364 Triangular array begins:
%e A306364         1;
%e A306364         3;
%e A306364        12,        3;
%e A306364        60,       45;
%e A306364       360,      540,       45;
%e A306364      2520,     6300,     1575;
%e A306364     20160,    75600,    37800,    1575;
%e A306364    181440,   952560,   793800,   99225;
%e A306364   1814400, 12700800, 15876000, 3969000, 99225;
%e A306364   ...
%t A306364 Table[n! (n - 2)!/(2^(2 k - 1) (n - 2 k)! k! (k - 1)!), {n, 2, 15}, {k, 1, Floor[n/2]}]
%Y A306364 Row sums equal A001147(n-1).
%Y A306364 Column k=1 gives A001710.
%Y A306364 T(2n,n) gives A079484(n-1).
%K A306364 nonn,tabf
%O A306364 2,2
%A A306364 _Noah A Rosenberg_, Feb 10 2019