Search
Close this search box.

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing

  • Research article

On the Average Number of Nodes Covering a Given Number of Leaves in an Unordered Binary Tree

Nozomu Ochiumi1, Fumiaki Kanazawa1,2, Masahiro Yanagidal2, Yasuichi Horibe1
1Department of Mathematical Information Science, Faculty of Science, Tokyo University of Science,
2Japan Patent Office, 3-4-3 Kasumigaseki, Chiyoda-ku, Tokyo 100-8915, Japan
  • Published: 28/02/2011

Abstract

The covering number for a subset of leaves in a finite rooted tree is defined as the number of subtrees which remain after deleting all the paths connecting the root and the other leaves. We find the formula for the total sum (hence the average) of the covering numbers for a given subset of labeled leaves over all unordered binary trees with \( n \) leaves.

Keywords: covering number, unordered binary tree, recursion, generating function method
Information
Guidelines
CP Initiatives
Follow CP
Facebook Twitter Linkedin
1970-2024 CP (Manitoba, Canada) unless otherwise stated.
Citation
Nozomu Ochiumi, Fumiaki Kanazawa, Masahiro Yanagidal, Yasuichi Horibe. On the Average Number of Nodes Covering a Given Number of Leaves in an Unordered Binary Tree[J], Journal of Combinatorial Mathematics and Combinatorial Computing, Volume 076. 3-9. DOI: .