|
|
A355108
|
|
Maximal number of root ancestral configurations among matching gene trees and species trees with n leaves.
|
|
3
|
|
|
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
|
|
|
FORMULA
|
a(n) = max_{i=1..floor(n/2)} (a(i)+1)*(a(n-i)+1), with a(1)=0.
|
|
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:
|
|
MATHEMATICA
|
b[n_] := b[n] = If[n == 1, 1, 1+Max[Table[b[i] b[n-i], {i, n-1}]]];
a[n_] := b[n]-1;
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|