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

Offset: 1

Author

Noah A Rosenberg, Jun 19 2022

Keywords

• nonn

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

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

Crossrefs

Cf. A003095, A004019, A091980, A306390.

Programs

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

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;
Array[a, 42] (* Jean-François Alcover, Jun 25 2022 *)

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.