cp's OEIS Frontend

A264868 Number of rooted tandem duplication trees on n gene segments.

%I A264868 #37 Jan 26 2024 10:18:42
%S A264868 1,1,2,6,22,92,420,2042,10404,54954,298648,1660714,9410772,54174212,
%T A264868 316038060,1864781388,11111804604,66782160002,404392312896,
%U A264868 2465100947836,15116060536540,93184874448186,577198134479356,3590697904513792,22425154536754776
%N A264868 Number of rooted tandem duplication trees on n gene segments.
%C A264868 Apparently a(n) is the number of words [d(0)d(1)d(2)...d(n)] where d(k) <= k (so d(0)=0) and if w(k-1) > w(k) then w(k-1) - w(k) = 1 (that is, descents by 2 or more are forbidden). - _Joerg Arndt_, Jan 26 2024
%D A264868 Mathematics of Evolution and Phylogeny, O. Gascuel (ed.), Oxford University Press, 2005
%H A264868 Alois P. Heinz, <a href="/A264868/b264868.txt">Table of n, a(n) for n = 1..1000</a>
%H A264868 O. Gascuel, M. Hendy, A. Jean-Marie and R. McLachlan, <a href="http://www.massey.ac.nz/~rmclachl/duplications.pdf">The combinatorics of tandem duplication trees</a>, Systematic Biology 52, (2003), 110-118.
%H A264868 J. Yang and L. Zhang, <a href="http://dx.doi.org/10.1093/molbev/msh115">Letter. On Counting Tandem Duplication Trees</a>, Molecular Biology and Evolution, Volume 21, Issue 6, (2004) 1160-1163.
%F A264868 a(n) = Sum_{k = 1..floor((n + 1)/3)} (-1)^(k + 1)*binomial(n + 1 - 2*k,k)*a(n-k) with a(1) = a(2) = 1 (Yang and Zhang).
%F A264868 For n >= 3, (1/2)*a(n) = A086521(n) is the number of tandem duplication trees on n gene segments.
%F A264868 Main diagonal and row sums of A264869.
%F A264868 a(n) = Sum_{k=0..n-1} A291680(n-1,k). - _Alois P. Heinz_, Aug 29 2017
%e A264868 Form _Joerg Arndt_, Jan 26 2024: (Start)
%e A264868 The a(5) = 22 words as described in the comment are (dots denote zeros, leading zeros omitted):
%e A264868     1:  [ . . . ]
%e A264868     2:  [ . . 1 ]
%e A264868     3:  [ . . 2 ]
%e A264868     4:  [ . . 3 ]
%e A264868     5:  [ . 1 . ]
%e A264868     6:  [ . 1 1 ]
%e A264868     7:  [ . 1 2 ]
%e A264868     8:  [ . 1 3 ]
%e A264868     9:  [ . 2 1 ]
%e A264868    10:  [ . 2 2 ]
%e A264868    11:  [ . 2 3 ]
%e A264868    12:  [ 1 . . ]
%e A264868    13:  [ 1 . 1 ]
%e A264868    14:  [ 1 . 2 ]
%e A264868    15:  [ 1 . 3 ]
%e A264868    16:  [ 1 1 . ]
%e A264868    17:  [ 1 1 1 ]
%e A264868    18:  [ 1 1 2 ]
%e A264868    19:  [ 1 1 3 ]
%e A264868    20:  [ 1 2 1 ]
%e A264868    21:  [ 1 2 2 ]
%e A264868    22:  [ 1 2 3 ]
%e A264868 (End)
%p A264868 a:= proc(n) option remember;
%p A264868        if n = 1 then 1 elif n = 2 then 1 else add((-1)^(k+1)*
%p A264868           binomial(n+1-2*k, k)*a(n-k), k = 1..floor((n+1)/3))
%p A264868        end if;
%p A264868     end proc:
%p A264868 seq(a(n), n = 1..24);
%t A264868 a[n_] := a[n] = If[n == 1, 1, If[n == 2, 1, Sum[(-1)^(k+1) Binomial[n+1-2k, k] a[n-k], {k, 1, Floor[(n+1)/3]}]]]; Array[a, 25] (* _Jean-François Alcover_, May 29 2019 *)
%o A264868 (Python)
%o A264868 from sympy.core.cache import cacheit
%o A264868 from sympy import binomial
%o A264868 @cacheit
%o A264868 def a(n):
%o A264868     return 1 if n<3 else sum([(-1)**(k + 1)*binomial(n + 1 - 2*k, k)*a(n - k) for k in range(1, (n + 1)//3 + 1)])
%o A264868 print([a(n) for n in range(1, 26)]) # _Indranil Ghosh_, Aug 30 2017
%Y A264868 Cf. A086521, A264869, A264870, A291680.
%Y A264868 Cf. A005773.
%K A264868 nonn,easy
%O A264868 1,3
%A A264868 _Peter Bala_, Nov 27 2015