Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Is there any result known about counting the number of (unlabeled) ordered trees which follow a given unordered degree sequence?

Here an ordered tree is understood as a rooted tree in which the order of the subtrees is significant.

share|improve this question
    
Ordered in what sense? Gerhard "Ask Me About System Design" Paseman, 2012.03.18 –  Gerhard Paseman Mar 19 '12 at 1:22
    
@Gerhard Paseman An ordered tree is a rooted tree in which the order of the subtrees is significant. –  marc Mar 19 '12 at 1:24
    
And how is the degree sequence given? is it ordered as well? Or is it just a multiset? Gerhard "Ask Me About System Design" Paseman, 2012.03.18 –  Gerhard Paseman Mar 19 '12 at 3:35
    
@Gerhard Paseman sorry for the unclear specification: The degree sequence is ordered as well –  marc Mar 19 '12 at 4:10
1  
so would degree sequence 2,1,3,4,5,1,1,1,1,1,1,1 mean the root has two children, the one on the left is a leaf and the one on the right has two children , one with 3 leaves on it and one with 4? That would uniquely specify the tree so it must not be that. Can you give an example? –  Aaron Meyerowitz Mar 19 '12 at 6:03
show 3 more comments

2 Answers 2

up vote 1 down vote accepted

Is Theorem 6.4 of http://people.brandeis.edu/~gessel/homepage/papers/enum.pdf what you want?

share|improve this answer
add comment

See Theorem 4.3 on page 12 here.

share|improve this answer
    
@GH Thank you for your answer. But this formula counts the number of labeled trees, whereas ordered trees are considered unlabeled. –  marc Mar 19 '12 at 4:57
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.