cp's OEIS Frontend

A306402 Number of coalescent histories for a matching completely symmetric gene tree and completely symmetric species tree with 2^n leaves.

%I A306402 #8 Mar 26 2019 11:49:21
%S A306402 1,1,4,169,1020100,270062420147776,686954819460520804489954417158400,
%T A306402 3171571350979001722602021784038902498684386645982829438130935832126653601
%N A306402 Number of coalescent histories for a matching completely symmetric gene tree and completely symmetric species tree with 2^n leaves.
%C A306402 A completely symmetric tree with 2^n leaves is a tree recursively defined by subdividing the root into two descendant branches with equally many leaves. The number of coalescent histories for matching completely symmetric trees with 2^n leaves can be determined from a bivariate recursion that considers completely symmetric trees with 2^(n-1) leaves (Rosenberg 2007, Theorem 3.1).
%H A306402 N. A. Rosenberg, <a href="https://doi.org/10.1089/cmb.2006.0109">Counting coalescent histories</a>, J. Comput. Biol. 14 (2007), 360-377.
%F A306402 a(n) = b(n,1), where b(n,k) is defined for integers n>=0 and k>=1, b(n,k) = Sum_{m=2..k+1} b(n-1,k+1)^2, and b(0,k)=1 for all k.
%e A306402 For n=2, the trees have 2^2=4 leaves. Labeling these leaves A, B, C, and D, suppose the gene tree and species tree have matching labeled topology ((A,B),(C,D)). Denote the species tree edges immediately ancestral to species tree nodes (A,B), (C,D), and ((A,B),(C,D)) by 1, 2, and 3 respectively. The 4 coalescent histories, representing the vector of the images of gene tree nodes ((A,B), (C,D), ((A,B),(C,D)) in the species tree, are (3,3,3), (1,3,3), (3,2,3), and (1,2,3).
%t A306402 b[0, k_] := 1
%t A306402 Do[b[n, k] = Sum[b[n - 1, m]^2, {m, 2, k + 1}], {k, 1, 11}, {n, 1, 10}]
%t A306402 Do[Print[b[n, 1]], {n, 0, 10}]
%t A306402 (* Note: this is a bivariate recursion in which b[n,1] is of interest. The largest value of k required for evaluating b[n,1] increases as n decreases; set the upper limit on k larger than the upper limit on n. *)
%Y A306402 Coalescent histories appear also in A306205, A306295.
%K A306402 nonn
%O A306402 0,3
%A A306402 _Noah A Rosenberg_, Feb 13 2019