Welcome to MathOverflow

Question

1

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.

edited Mar 24 2012 at 21:04

asked Mar 19 2012 at 0:23

marc
27●4

Ordered in what sense? Gerhard "Ask Me About System Design" Paseman, 2012.03.18 – Gerhard Paseman Mar 19 2012 at 1:22

@Gerhard Paseman An ordered tree is a rooted tree in which the order of the subtrees is significant. – marc Mar 19 2012 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 2012 at 3:35

@Gerhard Paseman sorry for the unclear specification: The degree sequence is ordered as well – marc Mar 19 2012 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 2012 at 6:03

show 3 more comments

Ira Gessel · Accepted Answer · 2012-03-19 20:37:55Z UTC

1

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

answered Mar 19 2012 at 20:37

Ira Gessel
2,361●5●15

GH · Answer 2 · 2012-03-19 04:36:44Z UTC

0

See Theorem 4.3 on page 12 here.

answered Mar 19 2012 at 4:36

GH
15k●1●31●53

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

Number of Ordered Trees of given degree sequence

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.