- FindStat

edit this statistic or download as text // json

Identifier

St000398: Binary trees ⟶ ℤ

Values

[.,.] => 0

[.,[.,.]] => 1

[[.,.],.] => 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[[.,.],[.,[.,[.,.]]]] => 7

[[.,.],[.,[[.,.],.]]] => 7

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

[[.,.],[[.,[.,.]],.]] => 7

[[.,.],[[[.,.],.],.]] => 7

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

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

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

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

[[.,[.,[.,.]]],[.,.]] => 7

[[.,[[.,.],.]],[.,.]] => 7

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

[[[.,[.,.]],.],[.,.]] => 7

[[[[.,.],.],.],[.,.]] => 7

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[.,[[.,.],[[.,.],[.,.]]]] => 11

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

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

[.,[[.,[.,.]],[.,[.,.]]]] => 11

[.,[[.,[.,.]],[[.,.],.]]] => 11

[.,[[[.,.],.],[.,[.,.]]]] => 11

[.,[[[.,.],.],[[.,.],.]]] => 11

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

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

[.,[[[.,.],[.,.]],[.,.]]] => 11

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

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

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

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

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

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

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

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

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

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

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

>>> Load all 1200 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 sum of the depths of the vertices (or total internal path length) of a binary tree.
The depth of a vertex is the number of edges to the tree's root, see Section 2.3.4.5 of [1] and [3].
This statistic is the very first entry of the OEIS, see [2]. Observe that there the term height is used instead.

References

[1] Knuth, D. E. The art of computer programming. Vol. 1 MathSciNet:3077152
[2] Normalized total height of all nodes in all rooted trees with n labeled nodes. OEIS:A000435
[3] wikipedia:Tree (data_structure)

Code

def statistic(T):
    return path_length_aux(T, 0)

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 15:54 by Martin Rubey

Updated

Aug 10, 2016 at 11:38 by Christian Stump