A354690 Number of unrooted labeled binary trees satisfying a path-length criterion concerning three labeled leaves.

1, 2, 8, 54, 468, 4950, 62640, 920430, 15373260, 287746830, 5965860600, 135691860150, 3359026786500, 89901262801350, 2586669802516800, 79617014497770750, 2610359828029453500, 90821198300068986750, 3342059240460417477000, 129683329092674014407750

Offset

3,2

Comments

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).

Links

Alois P. Heinz, Table of n, a(n) for n = 3..406

Jaehee Kim, Filippo Disanto, Naama M. Kopelman, and Noah A. Rosenberg, Mathematical and simulation-based analysis of the behavior of admixed taxa in the neighbor-joining algorithm, Bull. Math. Biol. 81 (2019), 452-493.

Formula

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).

Example

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.

Maple

a:= proc(n) option remember; add(add(add(
      b(n, i, j, k), i=k..n-2), j=k..n-2), k=1..n-2)
    end:
b:= proc(n, i, j, k) option remember; `if`(n=3, `if`({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))
    end:
seq(a(n), n=3..25);  # Alois P. Heinz, Jun 12 2022
# second Maple program:
a:= proc(n) option remember; `if`(n<5, (5-n)*(n-1)*(n-2)*n/12, (
      (78*n^2-619*n+1197)*a(n-1)-12*(3*n-11)*(n-4)*(2*n-9)*a(n-2)+
      8*(3*n-14)*(n-3)*(n-4)*(n-5)*a(n-3)-8*(3*n-11)*(n-4)*(n-5)
       *(n-6)*(2*n-9)*a(n-4))/(21*n-98))
    end:
seq(a(n), n=3..25);  # Alois P. Heinz, Jun 12 2022

Mathematica

a[n_] := a[n] = Sum[Sum[Sum[b[n, i, j, k], {i, k, n-2}], {j, k, n-2}], {k, 1, n-2}];
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]];
Table[a[n], {n, 3, 25}] (* Jean-François Alcover, Sep 10 2022, after Alois P. Heinz *)

Crossrefs

Cf. A001147.

Sequence in context: A052694 A069729 A346647 * A052599 A352648 A052662

Adjacent sequences: A354687 A354688 A354689 * A354691 A354692 A354693

Keyword

nonn

Author

Noah A Rosenberg, Jun 03 2022

Extensions

a(17)-a(22) from Alois P. Heinz, Jun 12 2022

Status

approved