- FindStat

edit this statistic or download as text // json

Identifier

St000399: Binary trees ⟶ ℤ

Values

[.,.] => 2

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

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

[.,[.,[.,.]]] => 9

[.,[[.,.],.]] => 9

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

[[.,[.,.]],.] => 9

[[[.,.],.],.] => 9

[.,[.,[.,[.,.]]]] => 14

[.,[.,[[.,.],.]]] => 14

[.,[[.,.],[.,.]]] => 13

[.,[[.,[.,.]],.]] => 14

[.,[[[.,.],.],.]] => 14

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

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

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

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

[[.,[.,[.,.]]],.] => 14

[[.,[[.,.],.]],.] => 14

[[[.,.],[.,.]],.] => 13

[[[.,[.,.]],.],.] => 14

[[[[.,.],.],.],.] => 14

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

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

[.,[.,[[.,.],[.,.]]]] => 19

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

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

[.,[[.,.],[.,[.,.]]]] => 18

[.,[[.,.],[[.,.],.]]] => 18

[.,[[.,[.,.]],[.,.]]] => 18

[.,[[[.,.],.],[.,.]]] => 18

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

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

[.,[[[.,.],[.,.]],.]] => 19

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

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

[[.,.],[.,[.,[.,.]]]] => 17

[[.,.],[.,[[.,.],.]]] => 17

[[.,.],[[.,.],[.,.]]] => 16

[[.,.],[[.,[.,.]],.]] => 17

[[.,.],[[[.,.],.],.]] => 17

[[.,[.,.]],[.,[.,.]]] => 16

[[.,[.,.]],[[.,.],.]] => 16

[[[.,.],.],[.,[.,.]]] => 16

[[[.,.],.],[[.,.],.]] => 16

[[.,[.,[.,.]]],[.,.]] => 17

[[.,[[.,.],.]],[.,.]] => 17

[[[.,.],[.,.]],[.,.]] => 16

[[[.,[.,.]],.],[.,.]] => 17

[[[[.,.],.],.],[.,.]] => 17

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

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

[[.,[[.,.],[.,.]]],.] => 19

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

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

[[[.,.],[.,[.,.]]],.] => 18

[[[.,.],[[.,.],.]],.] => 18

[[[.,[.,.]],[.,.]],.] => 18

[[[[.,.],.],[.,.]],.] => 18

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

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

[[[[.,.],[.,.]],.],.] => 19

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

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

[.,[.,[.,[.,[.,[.,.]]]]]] => 27

[.,[.,[.,[.,[[.,.],.]]]]] => 27

[.,[.,[.,[[.,.],[.,.]]]]] => 26

[.,[.,[.,[[.,[.,.]],.]]]] => 27

[.,[.,[.,[[[.,.],.],.]]]] => 27

[.,[.,[[.,.],[.,[.,.]]]]] => 25

[.,[.,[[.,.],[[.,.],.]]]] => 25

[.,[.,[[.,[.,.]],[.,.]]]] => 25

[.,[.,[[[.,.],.],[.,.]]]] => 25

[.,[.,[[.,[.,[.,.]]],.]]] => 27

[.,[.,[[.,[[.,.],.]],.]]] => 27

[.,[.,[[[.,.],[.,.]],.]]] => 26

[.,[.,[[[.,[.,.]],.],.]]] => 27

[.,[.,[[[[.,.],.],.],.]]] => 27

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

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

[.,[[.,.],[[.,.],[.,.]]]] => 23

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

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

[.,[[.,[.,.]],[.,[.,.]]]] => 23

[.,[[.,[.,.]],[[.,.],.]]] => 23

[.,[[[.,.],.],[.,[.,.]]]] => 23

[.,[[[.,.],.],[[.,.],.]]] => 23

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

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

[.,[[[.,.],[.,.]],[.,.]]] => 23

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

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

[.,[[.,[.,[.,[.,.]]]],.]] => 27

[.,[[.,[.,[[.,.],.]]],.]] => 27

[.,[[.,[[.,.],[.,.]]],.]] => 26

[.,[[.,[[.,[.,.]],.]],.]] => 27

[.,[[.,[[[.,.],.],.]],.]] => 27

[.,[[[.,.],[.,[.,.]]],.]] => 25

[.,[[[.,.],[[.,.],.]],.]] => 25

[.,[[[.,[.,.]],[.,.]],.]] => 25

[.,[[[[.,.],.],[.,.]],.]] => 25

>>> Load all 1883 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 external path length of a binary tree.
This is the sum of the lengths of all paths from the root to an external node, see Section 2.3.4.5 of [1].
This is also called the Sackin balance index of a rooted binary tree, see [2].

References

[1] Knuth, D. E. The art of computer programming. Vol. 1 MathSciNet:3077152
[2] Fischer, M. Extremal values of the Sackin balance index for rooted binary trees arXiv:1801.10418

Code

def statistic(T):
    return path_length_aux(T, 0) + 2*T.node_number()

def path_length_aux(T, n):
    return n+sum(path_length_aux(S, n+1) for S in T if not S.is_empty())

Created

Feb 22, 2016 at 16:02 by Martin Rubey

Updated

Mar 28, 2019 at 11:15 by Martin Rubey