- FindStat

edit this statistic or download as text // json

Identifier

St000085: Ordered trees ⟶ ℤ

Values

[[]] => 1

[[],[]] => 2

[[[]]] => 1

[[],[],[]] => 6

[[],[[]]] => 3

[[[]],[]] => 3

[[[],[]]] => 2

[[[[]]]] => 1

[[],[],[],[]] => 24

[[],[],[[]]] => 12

[[],[[]],[]] => 12

[[],[[],[]]] => 8

[[],[[[]]]] => 4

[[[]],[],[]] => 12

[[[]],[[]]] => 6

[[[],[]],[]] => 8

[[[[]]],[]] => 4

[[[],[],[]]] => 6

[[[],[[]]]] => 3

[[[[]],[]]] => 3

[[[[],[]]]] => 2

[[[[[]]]]] => 1

[[],[],[],[],[]] => 120

[[],[],[],[[]]] => 60

[[],[],[[]],[]] => 60

[[],[],[[],[]]] => 40

[[],[],[[[]]]] => 20

[[],[[]],[],[]] => 60

[[],[[]],[[]]] => 30

[[],[[],[]],[]] => 40

[[],[[[]]],[]] => 20

[[],[[],[],[]]] => 30

[[],[[],[[]]]] => 15

[[],[[[]],[]]] => 15

[[],[[[],[]]]] => 10

[[],[[[[]]]]] => 5

[[[]],[],[],[]] => 60

[[[]],[],[[]]] => 30

[[[]],[[]],[]] => 30

[[[]],[[],[]]] => 20

[[[]],[[[]]]] => 10

[[[],[]],[],[]] => 40

[[[[]]],[],[]] => 20

[[[],[]],[[]]] => 20

[[[[]]],[[]]] => 10

[[[],[],[]],[]] => 30

[[[],[[]]],[]] => 15

[[[[]],[]],[]] => 15

[[[[],[]]],[]] => 10

[[[[[]]]],[]] => 5

[[[],[],[],[]]] => 24

[[[],[],[[]]]] => 12

[[[],[[]],[]]] => 12

[[[],[[],[]]]] => 8

[[[],[[[]]]]] => 4

[[[[]],[],[]]] => 12

[[[[]],[[]]]] => 6

[[[[],[]],[]]] => 8

[[[[[]]],[]]] => 4

[[[[],[],[]]]] => 6

[[[[],[[]]]]] => 3

[[[[[]],[]]]] => 3

[[[[[],[]]]]] => 2

[[[[[[]]]]]] => 1

[[],[],[],[],[],[]] => 720

[[],[],[],[],[[]]] => 360

[[],[],[],[[]],[]] => 360

[[],[],[],[[],[]]] => 240

[[],[],[],[[[]]]] => 120

[[],[],[[]],[],[]] => 360

[[],[],[[]],[[]]] => 180

[[],[],[[],[]],[]] => 240

[[],[],[[[]]],[]] => 120

[[],[],[[],[],[]]] => 180

[[],[],[[],[[]]]] => 90

[[],[],[[[]],[]]] => 90

[[],[],[[[],[]]]] => 60

[[],[],[[[[]]]]] => 30

[[],[[]],[],[],[]] => 360

[[],[[]],[],[[]]] => 180

[[],[[]],[[]],[]] => 180

[[],[[]],[[],[]]] => 120

[[],[[]],[[[]]]] => 60

[[],[[],[]],[],[]] => 240

[[],[[[]]],[],[]] => 120

[[],[[],[]],[[]]] => 120

[[],[[[]]],[[]]] => 60

[[],[[],[],[]],[]] => 180

[[],[[],[[]]],[]] => 90

[[],[[[]],[]],[]] => 90

[[],[[[],[]]],[]] => 60

[[],[[[[]]]],[]] => 30

[[],[[],[],[],[]]] => 144

[[],[[],[],[[]]]] => 72

[[],[[],[[]],[]]] => 72

[[],[[],[[],[]]]] => 48

[[],[[],[[[]]]]] => 24

[[],[[[]],[],[]]] => 72

[[],[[[]],[[]]]] => 36

[[],[[[],[]],[]]] => 48

[[],[[[[]]],[]]] => 24

>>> Load all 438 entries. <<<

search for individual values

searching the database for the individual values of this statistic

/ search for generating function

searching the database for statistics with the same generating function

click to show known generating functions

Description

The number of linear extensions of the tree.
We use Knuth's hook length formula for trees [pg.70, 1]. For an ordered tree $T$ on $n$ vertices, the number of linear extensions is
$$ \frac{n!}{\prod_{v\in T}|T_v|}, $$
where $T_v$ is the number of vertices of the subtree rooted at $v$.

References

[1] Knuth, D. E. The art of computer programming. Volume 3 MathSciNet:0445948

Code

def tree_hook_product(tree):
    hook_products = [tree_hook_product(t) for t in tree]
    return prod(hook_products)*tree.node_number()
    
def tree_hook_formula(tree):
    return factorial(tree.node_number())/tree_hook_product(tree)

def statistic(t):
    return tree_hook_formula(t)

Created

Jun 13, 2013 at 10:24 by Viviane Pons

Updated

Mar 20, 2019 at 00:53 by Martin Rubey