A335408 Diameter of nearest neighbor interchange distance for free 3-trees.

0, 1, 3, 5, 7, 10, 12, 15, 18, 21

Offset

3,3

Comments

a(n) is the maximum value of the nearest neighbor interchange distance between two unrooted binary trees with n leaves, obtained by evaluating the distance from one tree with each of the unlabeled n-leaf tree shapes (see A000672) to each labeled n-leaf tree (A001147) using the C script described in Li et al. (1996).

The known terms a(3),...,a(12) happen (coincidentally?) to match the first ten terms of A211266. However, it seems unlikely that the sequences will agree for ever.

References

Ming Li, John Tromp, and Louxin Zhang, Some notes on the nearest neighbour interchange distance, in Goos, G., Hartmanis, J., Leeuwen, J., Cai, J.-Y., and Wong, C. K., eds., "Computing and Combinatorics" 1090, Springer (Berlin, Heidelberg) (1996), 343-351. doi:10.1007/3-540-61332-3_168.

Links

Table of n, a(n) for n=3..12.

Ming Li, John Tromp, and Louxin Zhang, Some notes on the nearest neighbour interchange distance, on ResearchGate.

Ming Li, John Tromp, and Louxin Zhang, On the Nearest Neighbour Interchange Distance Between Evolutionary Trees, J. Theoretical Biology, 182 (1996), 463-467.

Crossrefs

Cf. A211266, which happens to have the same initial terms (offset by two). It is not clear whether this correspondence continues for higher terms.

A000672 gives the number of unrooted tree shapes on n leaves; A001147 gives the number of (labeled) unrooted trees.

Sequence in context: A175312 A057640 A182136 * A211266 A394869 A378365

Adjacent sequences: A335405 A335406 A335407 * A335409 A335410 A335411

Keyword

nonn,hard,more

Author

Martin R. Smith, Jun 06 2020

Status

approved