I How Many Regular Ternary Ordered Trees with Height 3 Exist?

  • I
  • Thread starter Thread starter fiksx
  • Start date Start date
  • Tags Tags
    Tree
AI Thread Summary
The discussion focuses on calculating the number of regular ternary ordered trees with a height of 3, with participants exploring different combinatorial approaches. One participant suggests that the total number of such trees is 511, derived from the sum of combinations of nodes (9Ck for k from 1 to 9). Another method proposed involves calculating the possibilities in each subtree, resulting in a multiplication of combinations, leading to a similar conclusion of 511 after adjusting for trees of lesser height. The conversation also references resources on k-ary trees for further clarification. The calculations and reasoning provided indicate a strong grasp of combinatorial principles in tree structures.
fiksx
Messages
77
Reaction score
1
TL;DR Summary
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 excercise 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:

Thread 'Deductive proof in logic formal systems'

I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...
View full post »

Similar threads

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

Hot Threads

Recent Insights

Back
Top