A355108 - OEIS

The OEIS is supported by the many generous donors to the OEIS Foundation.

A355108

Maximal number of root ancestral configurations among matching gene trees and species trees with n leaves.

0, 1, 2, 4, 6, 10, 15, 25, 35, 55, 80, 130, 182, 286, 416, 676, 936, 1456, 2106, 3406, 4758, 7462, 10842, 17602, 24372, 37912, 54837, 88687, 123891, 194299, 282309, 458329, 634349, 986389, 1426439, 2306539, 3221843, 5052451, 7340711, 11917231, 16500521

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

COMMENTS

An ancestral configuration is a set of gene lineages present immediately before a node of a species tree is reached, looking backward in time, and a root ancestral configuration is an ancestral configuration at the root node. The term a(n) gives the largest number of root ancestral configurations among pairs (G,S) where G is a labeled gene tree topology, S is a bijectively labeled species tree topology, G and S have n leaves, and G=S.

LINKS

Table of n, a(n) for n=1..41.

F. Disanto and N. A. Rosenberg, Enumeration of ancestral configurations for matching gene trees and species trees, J. Comput. Biol. 24 (2017), 831-850.

FORMULA

a(n) = max_{i=1..floor(n/2)} (a(i)+1)*(a(n-i)+1), with a(1)=0.

a(n) = A091980(n) - 1.

a(2^n) = A004019(n) = A003095(n)^2.

MAPLE

a:= proc(n) option remember; `if`(n=1, 0, (g-> (f->

(1+a(f))*(1+a(n-f)))(min(g, n-g/2)))(2^ilog2(n)))

end:

seq(a(n), n=1..42); # Alois P. Heinz, Jun 19 2022