DROPS

Document

DOI: 10.4230/LIPIcs.AofA.2024.18

Periodic Behavior of the Minimal Colijn-Plazzotta Rank for Trees with a Fixed Number of Leaves

Authors: Michael R. Doboli, Hsien-Kuei Hwang, and Noah A. Rosenberg

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract

The Colijn-Plazzotta ranking is a certain bijection between the unlabeled binary rooted trees and the positive integers, such that the integer associated with a tree is determined from the integers associated with the two immediate subtrees of its root. Letting a_n denote the minimal Colijn-Plazzotta rank among all trees with a specified number of leaves n, the sequence {a_n} begins 1, 2, 3, 4, 6, 7, 10, 11, 20, 22, 28, 29, 53, 56, 66, 67 (OEIS A354970). Here we show that a_n ∼ 2 [2^{P(log₂ n)}]ⁿ, where P varies as a periodic function dependent on {log₂ n} and satisfies 1.24602 < 2^{P(log₂ n)} < 1.33429.

Cite as

Michael R. Doboli, Hsien-Kuei Hwang, and Noah A. Rosenberg. Periodic Behavior of the Minimal Colijn-Plazzotta Rank for Trees with a Fixed Number of Leaves. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{doboli_et_al:LIPIcs.AofA.2024.18,
  author =	{Doboli, Michael R. and Hwang, Hsien-Kuei and Rosenberg, Noah A.},
  title =	{{Periodic Behavior of the Minimal Colijn-Plazzotta Rank for Trees with a Fixed Number of Leaves}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{18:1--18:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.18},
  URN =		{urn:nbn:de:0030-drops-204530},
  doi =		{10.4230/LIPIcs.AofA.2024.18},
  annote =	{Keywords: Colijn-Plazzotta ranking, recurrences, unlabeled trees}
}

Search Results

Documents authored by Doboli, Michael R.

Periodic Behavior of the Minimal Colijn-Plazzotta Rank for Trees with a Fixed Number of Leaves

Abstract

Cite as

Thanks for your feedback!

Could not send message