A306295 - OEIS

%I #18 Jun 03 2022 08:17:11

%S 1,3,10,32,107,359,1234,4274,15032,53242,190588,686272,2490399,

%T 9081375,33312770,122692130,453999656,1685601038,6282014804,

%U 23478897364,88026769844,330831420218,1246635155180,4707414286652,17815452662152,67546709440004,256595322436760

%N Maximal number of coalescent histories among non-matching pairs consisting of a caterpillar gene tree and a caterpillar species tree with n+2 leaves.

%H Z. M. Himwich and N. A. Rosenberg, <a href="https://arxiv.org/abs/1901.04465">Roadblocked monotonic paths and the enumeration of coalescent histories for non-matching caterpillar gene trees and species trees</a>, arXiv:1901.04465 [q-bio.pE] (2019); Adv. Appl. Math. 113 (2020), 101939.

%F a(n) = C(n+1) - C(floor((n+1)/2))*C(ceiling((n+1)/2)), where C(n) is the n-th term in the Catalan sequence A000108.

%e For n=1, a non-matching caterpillar gene tree and species tree with n+2=3 leaves have only one coalescent history: all coalescences must take place above the root of the species tree. Hence, a(1)=1.

%t b[n_] :=

%t Binomial[2 n - 2, n - 1]/

%t    n - (2 Floor[(n - 1)/2])!/(Floor[(n - 1)/2]! Floor[(n + 1)/

%t          2]!) (2 Ceiling[(n - 1)/2])!/(Ceiling[(n - 1)/

%t          2]! Ceiling[(n + 1)/2]!)

%t a[n_] := b[n+2]

%t Table[a[n], {n,1,30}]

%Y A000108 minus A005817.

%K nonn

%O 1,2

%A _Noah A Rosenberg_, Feb 04 2019