|
%I #13 Nov 29 2015 14:03:02
%S 1,1,3,11,46,210,1021,5202,27477,149324,830357,4705386,27087106,
%T 158019030,932390694,5555902302,33391080001,202196156448,
%U 1232550473918,7558030268270,46592437224093,288599067239678,1795348952256896
%N Number of tandem duplication trees on n duplicated gene segments.
%C For n > 2, 2*a(n) is the number of rooted tandem duplication trees. See A264869.
%D O. Gascuel (Ed.), Mathematics of Evolution and Phylogeny, Oxford University Press, 2005
%H O. Gascuel, M. Hendy, A. Jean-Marie and R. McLachlan, (2003) <a href="http://www.massey.ac.nz/~rmclachl/duplications.pdf">The combinatorics of tandem duplication trees</a>, Systematic Biology 52, 110-118.
%H J. Yang and L. Zhang, <a href="http://dx.doi.org/10.1093/molbev/msh115">On Counting Tandem Duplication Trees</a>, Molecular Biology and Evolution, Volume 21, Issue 6, (2004) 1160-1163.
%F a(n) = b(n+1, n-1), where b(n, 0) = b(n-1, 0) + b(n-1, 1); b(n, k) = b(n-1, k+1) + b(n, k-1), for k = 1, ..., n-2; with initial values b(2, 0) = 1, b(3, 0) = 0, b(3, 1) = 1.
%F For n >= 2, a(n) = b(n)/2, where b(n) = Sum_{k = 1..floor((n + 1)/3)} (-1)^(k + 1)*binomial(n + 1 - 2*k,k)*b(n-k) with b(1) = b(2) = 1 (Yang and Zhang). - _Peter Bala_, Nov 27 2015
%e a(5) = 11, so there are 11 binary leaf labeled trees on 5 duplicate genes. As there are 15 binary leaf labeled trees, this means not all binary leaf labeled trees can represent a gene duplication tree.
%p with(combinat):
%p b := proc (n) option remember;
%p if n = 2 then 2 elif n = 3 then 2 else add((-1)^(k+1)*binomial(n+1-2*k, k)*b(n-k), k = 1..floor((n+1)/3)) end if; end proc:
%p seq(b(n)/2, n = 2..24); # _Peter Bala_, Nov 27 2015
%Y Cf. A264868, A264869, A264870.
%K nonn,easy
%O 2,3
%A Michael D Hendy (m.hendy(AT)massey.ac.nz), Sep 10 2003
%E More terms from _David Wasserman_, Mar 11 2005
|
