How Many Regular Ternary Ordered Trees with Height 3 Exist?

  • Context: Undergrad 
  • Thread starter Thread starter fiksx
  • Start date Start date
  • Tags Tags
    Tree
Click For Summary
SUMMARY

The discussion centers on calculating the number of regular ternary ordered trees with a height of 3. The conclusion reached is that there are 511 distinct trees, derived from the combination of nodes using the formula 9Ck for k ranging from 1 to 9. Additionally, the calculation considers the multiplication of possibilities in each subtree, where the first subtree contributes 8 possibilities, leading to a total of 512, minus 1 to exclude the case where the tree height is 2. This confirms the total count of 511 trees.

PREREQUISITES
  • Understanding of combinatorial mathematics, specifically binomial coefficients.
  • Familiarity with tree data structures, particularly ordered trees.
  • Knowledge of k-ary trees and their properties.
  • Basic principles of graph theory related to tree height and radius.
NEXT STEPS
  • Study the properties of k-ary trees and their height calculations.
  • Learn about combinatorial counting techniques, focusing on binomial coefficients.
  • Explore the concept of tree radius and its implications in graph theory.
  • Review algorithms for generating and traversing ordered trees.
USEFUL FOR

Students and professionals in computer science, particularly those focusing on data structures, algorithms, and combinatorial mathematics.

fiksx
Messages
77
Reaction score
1
TL;DR
I’m not too familiar with ordered tree. I’m solving excercise about tree but i’m not sure it is right or wrong
Summary: I’m not too familiar with ordered tree. I’m solving exercise about tree but i’m not sure it is right or wrong

How many regular ternary ordered tree with height 3 (ordered tree means children of each vertex are assigned a fixed ordering)? What is the smallest and biggest radius for tree with height k?

Attempt: For regular ternary ordered tree with height 3 There will be 9 node that will have children 9C1 +9C2+9C3+9C4+9C4+9C5+9C6+9C7+9C8+9C9

And smallest and biggest radius for tree with height
 
Physics news on Phys.org
jedishrfu said:
Here's some discussion on k-ary trees that might help you check your answer:

https://cs.lmu.edu/~ray/notes/orderedtrees/

Thankyou but for ordered tree with height of 3 is the total possibility tree are 511? Because all sum possible combination of 9Ck (1<=k<=9) =511
Or other way multiplication of possibility in each subtree. First subtree will be 3C0 +3C1+3C2+3C3= 8 , because there are 3 subtree in height 1 so 8x8x8=512-1=511 , why substract 1 because 9C0 makes tree height 2 . Is this quite right?
 
Last edited:

Similar threads

Upper bound height and lower bound height of a 3-ary ordered tree
  • · Replies 13 ·
Replies
13
Views
3K