{
  "id": "1412.2796",
  "version": "v1",
  "published": "2014-12-08T22:09:03.000Z",
  "updated": "2014-12-08T22:09:03.000Z",
  "title": "On a random search tree: asymptotic enumeration of vertices by distance from leaves",
  "authors": [
    "Miklos Bona",
    "Boris Pittel"
  ],
  "comment": "27 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "A random binary search tree grown from the uniformly random permutation of $[n]$ is studied. We analyze the exact and asymptotic counts of vertices by rank, the distance from the set of leaves. The asymptotic fraction $c_k$ of vertices of a fixed rank $k\\ge 0$ is shown to decay exponentially with $k$. Notoriously hard to compute, the exact fractions $c_k$ had been determined for $k\\le 3$ only. We computed $c_4$ and $c_5$ as well; both are ratios of enormous integers, denominator of $c_5$ being $274$ digits long. Prompted by the data, we proved that, in sharp contrast, the largest prime divisor of $c_k$'s denominator is $2^{k+1}+1$ at most. We conjecture that, in fact, the prime divisors of every denominator for $k>1$ form a single interval, from $2$ to the largest prime not exceeding $2^{k+1}+1$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-12-08T22:09:03.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A05",
      "05A15",
      "05A16",
      "05C05",
      "06B05",
      "05C80",
      "05D40",
      "60C05"
    ],
    "keywords": [
      "random search tree",
      "asymptotic enumeration",
      "random binary search tree grown",
      "largest prime divisor",
      "denominator"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 27,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1412.2796B"
    }
  }
}