cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-4 of 4 results.

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

Original entry on oeis.org

1, 1, 2, 6, 22, 92, 420, 2042, 10404, 54954, 298648, 1660714, 9410772, 54174212, 316038060, 1864781388, 11111804604, 66782160002, 404392312896, 2465100947836, 15116060536540, 93184874448186, 577198134479356, 3590697904513792, 22425154536754776
Offset: 1

Views

Author

Peter Bala, Nov 27 2015

Keywords

Comments

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

Examples

			Form _Joerg Arndt_, Jan 26 2024: (Start)
The a(5) = 22 words as described in the comment are (dots denote zeros, leading zeros omitted):
    1:  [ . . . ]
    2:  [ . . 1 ]
    3:  [ . . 2 ]
    4:  [ . . 3 ]
    5:  [ . 1 . ]
    6:  [ . 1 1 ]
    7:  [ . 1 2 ]
    8:  [ . 1 3 ]
    9:  [ . 2 1 ]
   10:  [ . 2 2 ]
   11:  [ . 2 3 ]
   12:  [ 1 . . ]
   13:  [ 1 . 1 ]
   14:  [ 1 . 2 ]
   15:  [ 1 . 3 ]
   16:  [ 1 1 . ]
   17:  [ 1 1 1 ]
   18:  [ 1 1 2 ]
   19:  [ 1 1 3 ]
   20:  [ 1 2 1 ]
   21:  [ 1 2 2 ]
   22:  [ 1 2 3 ]
(End)

References

  • Mathematics of Evolution and Phylogeny, O. Gascuel (ed.), Oxford University Press, 2005

Links

Crossrefs

Cf. A086521, A264869, A264870, A291680.
Cf. A005773.

Programs

  • Maple
    a:= proc(n) option remember;
       if n = 1 then 1 elif n = 2 then 1 else add((-1)^(k+1)*
          binomial(n+1-2*k, k)*a(n-k), k = 1..floor((n+1)/3))
       end if;
    end proc:
seq(a(n), n = 1..24);
  • Mathematica
    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 *)
  • Python
    from sympy.core.cache import cacheit
from sympy import binomial
@cacheit
def a(n):
    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)])
print([a(n) for n in range(1, 26)]) # Indranil Ghosh, Aug 30 2017

Formula

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).
For n >= 3, (1/2)*a(n) = A086521(n) is the number of tandem duplication trees on n gene segments.
Main diagonal and row sums of A264869.
a(n) = Sum_{k=0..n-1} A291680(n-1,k). - Alois P. Heinz, Aug 29 2017

A206464 Number of length-n Catalan-RGS (restricted growth strings) such that the RGS is a valid mixed-radix number in falling factorial basis.

Original entry on oeis.org

1, 1, 2, 4, 10, 26, 74, 218, 672, 2126, 6908, 22876, 77100, 263514, 911992, 3189762, 11261448, 40083806, 143713968, 518594034, 1882217168, 6867064856, 25172021144, 92666294090, 342467464612, 1270183943200, 4726473541216, 17640820790092, 66025467919972
Offset: 0

Views

Author

Joerg Arndt, Feb 08 2012

Keywords

Comments

Catalan-RGS are strings with first digit d(0)=zero, and d(k+1) <= d(k)+1, falling factorial mixed-radix numbers have last digit <= 1, second last <= 2, etc.
The digits of the RGS are <= floor(n/2).
The first few terms are the same as for A089429.
Column k=0 of A264869. - Peter Bala, Nov 27 2015
a(n) = A291680(n+1,n+1). - Alois P. Heinz, Aug 29 2017

Examples

			The a(5)=26 strings for n=5 are (dots for zeros):
   1:  [ . . . . . ]
   2:  [ . . . . 1 ]
   3:  [ . . . 1 . ]
   4:  [ . . . 1 1 ]
   5:  [ . . 1 . . ]
   6:  [ . . 1 . 1 ]
   7:  [ . . 1 1 . ]
   8:  [ . . 1 1 1 ]
   9:  [ . . 1 2 . ]
  10:  [ . . 1 2 1 ]
  11:  [ . 1 . . . ]
  12:  [ . 1 . . 1 ]
  13:  [ . 1 . 1 . ]
  14:  [ . 1 . 1 1 ]
  15:  [ . 1 1 . . ]
  16:  [ . 1 1 . 1 ]
  17:  [ . 1 1 1 . ]
  18:  [ . 1 1 1 1 ]
  19:  [ . 1 1 2 . ]
  20:  [ . 1 1 2 1 ]
  21:  [ . 1 2 . . ]
  22:  [ . 1 2 . 1 ]
  23:  [ . 1 2 1 . ]
  24:  [ . 1 2 1 1 ]
  25:  [ . 1 2 2 . ]
  26:  [ . 1 2 2 1 ]

Links

Crossrefs

Cf. A080935, A080936, A264869, A291680.

Programs

  • Maple
    b:= proc(i, l) option remember;
      `if`(i<=0, 1, add(b(i-1, j), j=0..min(l+1, i)))
    end:
a:= n-> b(n-1, 0):
seq(a(n), n=0..40);  # Alois P. Heinz, Feb 08 2012
  • Mathematica
    b[i_, l_] := b[i, l] = If[i <= 0, 1, Sum[b[i-1, j], {j, 0, Min[l+1, i]}]];
a[n_] := b[n-1, 0];
a /@ Range[0, 40] (* Jean-François Alcover, Nov 07 2020, after Alois P. Heinz *)

Formula

Conjecture: a(n) = Sum_{k = 0..floor(n/4)} (-1)^k * C(floor(n/2) + 1 - k, k + 1) * a(n - 1 - k), a(0) = 1. - Gionata Neri, Jun 17 2018

A086521 Number of tandem duplication trees on n duplicated gene segments.

Original entry on oeis.org

1, 1, 3, 11, 46, 210, 1021, 5202, 27477, 149324, 830357, 4705386, 27087106, 158019030, 932390694, 5555902302, 33391080001, 202196156448, 1232550473918, 7558030268270, 46592437224093, 288599067239678, 1795348952256896
Offset: 2

Views

Author

Michael D Hendy (m.hendy(AT)massey.ac.nz), Sep 10 2003

Keywords

Comments

For n > 2, 2*a(n) is the number of rooted tandem duplication trees. See A264869.

Examples

			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.

References

  • O. Gascuel (Ed.), Mathematics of Evolution and Phylogeny, Oxford University Press, 2005

Links

Crossrefs

Cf. A264868, A264869, A264870.

Programs

  • Maple
    with(combinat):
b := proc (n) option remember;
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:
seq(b(n)/2, n = 2..24); # Peter Bala, Nov 27 2015

Formula

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

Extensions

More terms from David Wasserman, Mar 11 2005

A264870 Triangular array: For n >= 2 and 0 < k <= n - 2, T(n, k) equals the number of (unrooted) duplication trees on n gene segments that are canonical and whose leftmost visible duplication event is (k, r), for 1 <= r <= (n - k)/2.

Original entry on oeis.org

1, 0, 1, 1, 1, 1, 2, 3, 3, 3, 5, 8, 11, 11, 11, 13, 24, 35, 46, 46, 46, 37, 72, 118, 164, 210, 210, 210, 109, 227, 391, 601, 811, 1021, 1021, 1021, 336, 727, 1328, 2139, 3160, 4181, 5202, 5202, 5202, 1063, 2391, 4530, 7690, 11871, 17073, 22275, 27477, 27477, 27477
Offset: 0

Views

Author

Peter Bala, Nov 27 2015

Keywords

Comments

See Figure 3(b) in Gascuel et al. (2003).
From row 4 onwards, the entries are one-half the corresponding entries in A264879.
Row sums give the number of unrooted duplication trees on n gene segments, A086521.

Examples

			Triangle begins
n\k|   0    1    2    3    4     5     6     7
----------------------------------------------
.2.|   1
.3.|   0    1
.4.|   1    1    1
.5.|   2    3    3    3
.6.|   5    8   11   11   11
.7.|  13   24   35   46   46    46
.8.|  37   72  118  164  210   210   210
.9.| 109  227  391  601  811  1021  1021  1021
...

References

  • O. Gascuel (Ed.), Mathematics of Evolution and Phylogeny, Oxford University Press, 2005

Links

Crossrefs

Cf. A086521 (row sums), A264868, A264869.

Programs

  • Maple
    A264870 := proc (n, k) option remember;
`if`(n = 3 and k = 0, 0, `if`(n <= 4 and k <= n-2, 1, `if`(k > n - 2, 0, add(A264870(n-1, j), j = 0..min(k+1, n))))) end proc:
seq(seq(A264870(n, k), k = 0..n-2), n = 2..11);

Formula

T(n,k) = Sum_{j = 0..k+1} T(n-1,j) for n >= 4, 0 <= k <= n - 2, with T(2,0) = T(3,1) = 1, T(3,0) = 0 and T(n,k) = 0 for k >= n - 1.
T(n,k) = T(n,k-1) + T(n-1,k+1) for n >= 4, 1 <= k <= n - 2.
Showing 1-4 of 4 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.