<?xml version='1.0' encoding='utf-8'?>
<oai_dc:dc xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:oai_dc="http://www.openarchives.org/OAI/2.0/oai_dc/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/oai_dc/ http://www.openarchives.org/OAI/2.0/oai_dc.xsd">
  <dc:contributor>Michael R. Karlinger</dc:contributor>
  <dc:creator>Brent M. Troutman</dc:creator>
  <dc:date>1993</dc:date>
  <dc:description>&lt;p&gt;&lt;span&gt;Let&amp;nbsp;&lt;/span&gt;&lt;i&gt;F&lt;sub&gt;n&lt;/sub&gt;&lt;/i&gt;&lt;span&gt;&amp;nbsp;denote the set of rooted binary plane trees with&amp;nbsp;&lt;/span&gt;&lt;i&gt;n&lt;/i&gt;&lt;span&gt;&amp;nbsp;external nodes, for given&amp;nbsp;&lt;/span&gt;&lt;i&gt;T&lt;/i&gt;&lt;span&gt;∈&lt;/span&gt;&lt;i&gt;F&lt;/i&gt;&lt;sub&gt;&lt;i&gt;n&lt;/i&gt;&lt;/sub&gt;&lt;span&gt;&amp;nbsp;let&amp;nbsp;&lt;/span&gt;&lt;i&gt;u&lt;/i&gt;&lt;sub&gt;&lt;i&gt;i&lt;/i&gt;&lt;/sub&gt;&lt;span&gt;(&lt;/span&gt;&lt;i&gt;T&lt;/i&gt;&lt;span&gt;) be the altitude&amp;nbsp;&lt;/span&gt;&lt;i&gt;i&lt;/i&gt;&lt;span&gt;&amp;nbsp;node along the primary path of&amp;nbsp;&lt;/span&gt;&lt;i&gt;T&lt;/i&gt;&lt;span&gt;, and let&amp;nbsp;&lt;/span&gt;&lt;i&gt;δ&lt;/i&gt;&lt;sub&gt;&lt;i&gt;i&lt;/i&gt;&lt;/sub&gt;&lt;span&gt;(&lt;/span&gt;&lt;i&gt;T&lt;/i&gt;&lt;span&gt;) denote the number of external nodes in the induced subtree rooted at&amp;nbsp;&lt;/span&gt;&lt;i&gt;u&lt;/i&gt;&lt;sub&gt;&lt;i&gt;i&lt;/i&gt;&lt;/sub&gt;&lt;span&gt;(&lt;/span&gt;&lt;i&gt;T&lt;/i&gt;&lt;span&gt;). We set&amp;nbsp;&lt;/span&gt;&lt;i&gt;δ&lt;/i&gt;&lt;sub&gt;&lt;i&gt;i&lt;/i&gt;&lt;/sub&gt;&lt;span&gt;(&lt;/span&gt;&lt;i&gt;T&lt;/i&gt;&lt;span&gt;) = 0 if&amp;nbsp;&lt;/span&gt;&lt;i&gt;i&lt;/i&gt;&lt;span&gt;&amp;nbsp;is greater than the length of the primary path of&amp;nbsp;&lt;/span&gt;&lt;i&gt;T&lt;/i&gt;&lt;span&gt;. We prove lim&lt;/span&gt;&lt;sub&gt;&lt;i&gt;n&lt;/i&gt;→∞&lt;/sub&gt;&lt;span&gt;&amp;nbsp;∑&lt;/span&gt;&lt;sub&gt;&lt;i&gt;i&lt;/i&gt;≤&lt;i&gt;x&lt;/i&gt;/&lt;i&gt;n&lt;/i&gt;&lt;/sub&gt;&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;i&gt;E&lt;/i&gt;&lt;sub&gt;&lt;i&gt;n&lt;/i&gt;&lt;/sub&gt;&lt;span&gt;{&lt;/span&gt;&lt;i&gt;δ&lt;/i&gt;&lt;sub&gt;&lt;i&gt;i&lt;/i&gt;&lt;/sub&gt;&lt;span&gt;}/∑&lt;/span&gt;&lt;sub&gt;&lt;i&gt;i&lt;/i&gt;&amp;lt;∞&lt;/sub&gt;&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;i&gt;E&lt;/i&gt;&lt;sub&gt;&lt;i&gt;n&lt;/i&gt;&lt;/sub&gt;&lt;span&gt;{&lt;/span&gt;&lt;i&gt;δ&lt;/i&gt;&lt;sub&gt;&lt;i&gt;i&lt;/i&gt;&lt;/sub&gt;&lt;span&gt;} =&amp;nbsp;&lt;/span&gt;&lt;i&gt;G&lt;/i&gt;&lt;span&gt;(&lt;/span&gt;&lt;i&gt;x&lt;/i&gt;&lt;span&gt;), where&amp;nbsp;&lt;/span&gt;&lt;i&gt;E&lt;sub&gt;n&lt;/sub&gt;&lt;/i&gt;&lt;span&gt;&amp;nbsp;denotes the average over trees&amp;nbsp;&lt;/span&gt;&lt;i&gt;T&lt;/i&gt;&lt;span&gt;∈&lt;/span&gt;&lt;i&gt;F&lt;/i&gt;&lt;sub&gt;&lt;i&gt;n&lt;/i&gt;&lt;/sub&gt;&lt;span&gt;&amp;nbsp;and where the distribution function&amp;nbsp;&lt;/span&gt;&lt;i&gt;G&lt;/i&gt;&lt;span&gt;&amp;nbsp;is determined by its moments, for which we present an explicit expression.&lt;/span&gt;&lt;/p&gt;</dc:description>
  <dc:format>application/pdf</dc:format>
  <dc:identifier>10.1016/0166-218X(93)90181-M</dc:identifier>
  <dc:language>en</dc:language>
  <dc:publisher>Elsevier</dc:publisher>
  <dc:title>A note on subtrees rooted along the primary path of a binary tree</dc:title>
  <dc:type>article</dc:type>
</oai_dc:dc>