cp's OEIS Frontend

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

%I A355108 #25 Jun 25 2022 12:54:35
%S A355108 0,1,2,4,6,10,15,25,35,55,80,130,182,286,416,676,936,1456,2106,3406,
%T A355108 4758,7462,10842,17602,24372,37912,54837,88687,123891,194299,282309,
%U A355108 458329,634349,986389,1426439,2306539,3221843,5052451,7340711,11917231,16500521
%N A355108 Maximal number of root ancestral configurations among matching gene trees and species trees with n leaves.
%C A355108 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.
%H A355108 F. Disanto and N. A. Rosenberg, <a href="https://doi.org/10.1089/cmb.2016.0159">Enumeration of ancestral configurations for matching gene trees and species trees</a>, J. Comput. Biol. 24 (2017), 831-850.
%F A355108 a(n) = max_{i=1..floor(n/2)} (a(i)+1)*(a(n-i)+1), with a(1)=0.
%F A355108 a(n) = A091980(n) - 1.
%F A355108 a(2^n) = A004019(n) = A003095(n)^2.
%p A355108 a:= proc(n) option remember; `if`(n=1, 0, (g-> (f->
%p A355108      (1+a(f))*(1+a(n-f)))(min(g, n-g/2)))(2^ilog2(n)))
%p A355108     end:
%p A355108 seq(a(n), n=1..42);  # _Alois P. Heinz_, Jun 19 2022
%t A355108 b[n_] := b[n] = If[n == 1, 1, 1+Max[Table[b[i] b[n-i], {i, n-1}]]];
%t A355108 a[n_] := b[n]-1;
%t A355108 Array[a, 42] (* _Jean-François Alcover_, Jun 25 2022 *)
%Y A355108 Cf. A003095, A004019, A091980, A306390.
%K A355108 nonn
%O A355108 1,3
%A A355108 _Noah A Rosenberg_, Jun 19 2022