|
%I #31 Sep 10 2022 06:00:32
%S 1,2,8,54,468,4950,62640,920430,15373260,287746830,5965860600,
%T 135691860150,3359026786500,89901262801350,2586669802516800,
%U 79617014497770750,2610359828029453500,90821198300068986750,3342059240460417477000,129683329092674014407750
%N Number of unrooted labeled binary trees satisfying a path-length criterion concerning three labeled leaves.
%C a(n) is the number of unrooted labeled binary trees with n leaves in which, for three fixed labeled leaves A, B, and C, the path lengths from A and B to the unique internal node X that places A, B, and C into distinct subtrees are each greater than or equal to the path length from X to C. The probability that an unrooted labeled binary tree chosen uniformly at random from the A001147(n-2) unrooted labeled binary trees on n leaves satisfies the path-length criterion is a(n)/A001147(n-2).
%H Alois P. Heinz, <a href="/A354690/b354690.txt">Table of n, a(n) for n = 3..406</a>
%H Jaehee Kim, Filippo Disanto, Naama M. Kopelman, and Noah A. Rosenberg, <a href="https://doi.org/10.1007/s11538-018-0444-0">Mathematical and simulation-based analysis of the behavior of admixed taxa in the neighbor-joining algorithm</a>, Bull. Math. Biol. 81 (2019), 452-493.
%F a(n) = Sum_{k=1..n-2} Sum_{j=k..n-2} Sum_{i=k..n-2} b(n,i,j,k), where b(n,i,j,k) = (i-1)*b(n-1,i-1,j,k) + (j-1)*b(n-1,i,j-1,k) + (k-1)*b(n-1,i,j,k-1) + (2*n-5-i-j-k) * b(n-1,i,j,k) for n>2 with base cases b(3,1,1,1)=1 and b(3,i,j,k)=0 for all other (i,j,k).
%e For n=4, the a(2)=2 trees enumerated are ((A,C),(B,D)), with path length 1 for A to X, 2 for B to X, and 1 for C to X; and ((A,D),(B,C)), with path length 2 for A to X, 1 for B to X, and 1 for C to X; tree ((A,B),(C,D)) fails, as the path length 2 for C to X exceeds the path lengths of 1 for A to X and B to X.
%p a:= proc(n) option remember; add(add(add(
%p b(n, i, j, k), i=k..n-2), j=k..n-2), k=1..n-2)
%p end:
%p b:= proc(n, i, j, k) option remember; `if`(n=3, `if`({i, j, k}={1},
%p 1, 0), (i-1)*b(n-1, i-1, j, k)+(j-1)*b(n-1, i, j-1, k)+
%p (k-1)*b(n-1, i, j, k-1)+(2*n-5-i-j-k)*b(n-1, i, j, k))
%p end:
%p seq(a(n), n=3..25); # _Alois P. Heinz_, Jun 12 2022
%p # second Maple program:
%p a:= proc(n) option remember; `if`(n<5, (5-n)*(n-1)*(n-2)*n/12, (
%p (78*n^2-619*n+1197)*a(n-1)-12*(3*n-11)*(n-4)*(2*n-9)*a(n-2)+
%p 8*(3*n-14)*(n-3)*(n-4)*(n-5)*a(n-3)-8*(3*n-11)*(n-4)*(n-5)
%p *(n-6)*(2*n-9)*a(n-4))/(21*n-98))
%p end:
%p seq(a(n), n=3..25); # _Alois P. Heinz_, Jun 12 2022
%t a[n_] := a[n] = Sum[Sum[Sum[b[n, i, j, k], {i, k, n-2}], {j, k, n-2}], {k, 1, n-2}];
%t b[n_, i_, j_, k_] := b[n, i, j, k] = If[n == 3, If[Union@{i, j, k} == {1}, 1, 0], (i-1)*b[n-1, i-1, j, k] + (j-1)*b[n-1, i, j-1, k] + (k-1)*b[n-1, i, j, k-1] + (2*n-5-i-j-k)*b[n-1, i, j, k]];
%t Table[a[n], {n, 3, 25}] (* _Jean-François Alcover_, Sep 10 2022, after _Alois P. Heinz_ *)
%Y Cf. A001147.
%K nonn
%O 3,2
%A _Noah A Rosenberg_, Jun 03 2022
%E a(17)-a(22) from _Alois P. Heinz_, Jun 12 2022
|
