2
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • $\begingroup$ Ordered in what sense? Gerhard "Ask Me About System Design" Paseman, 2012.03.18 $\endgroup$
    – Gerhard Paseman
    Commented Mar 19, 2012 at 1:22
  • $\begingroup$ @Gerhard Paseman An ordered tree is a rooted tree in which the order of the subtrees is significant. $\endgroup$
    – marc
    Commented Mar 19, 2012 at 1:24
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Mar 19, 2012 at 3:35
  • $\begingroup$ @Gerhard Paseman sorry for the unclear specification: The degree sequence is ordered as well $\endgroup$
    – marc
    Commented Mar 19, 2012 at 4:10
  • 1
    $\begingroup$ 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? $\endgroup$
    – Aaron Meyerowitz
    Commented Mar 19, 2012 at 6:03

2 Answers 2

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
0
$\begingroup$

See Theorem 4.3 on page 12 here.

Improve this answer
$\endgroup$
1
  • $\begingroup$ @GH Thank you for your answer. But this formula counts the number of labeled trees, whereas ordered trees are considered unlabeled. $\endgroup$
    – marc
    Commented Mar 19, 2012 at 4:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .