- FindStat

edit this statistic or download as text // json

Identifier

St000204: Binary trees ⟶ ℤ

Values

[.,.] => 0

[.,[.,.]] => 0

[[.,.],.] => 0

[.,[.,[.,.]]] => 0

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

[[.,.],[.,.]] => 0

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

[[[.,.],.],.] => 0

[.,[.,[.,[.,.]]]] => 0

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

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

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

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

[[.,.],[.,[.,.]]] => 0

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

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

[[[.,.],.],[.,.]] => 0

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

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

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

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

[[[[.,.],.],.],.] => 0

[.,[.,[.,[.,[.,.]]]]] => 0

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

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

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

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

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

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

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

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

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

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

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

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

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

[[.,.],[.,[.,[.,.]]]] => 0

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

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

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

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

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

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

[[[.,.],.],[.,[.,.]]] => 0

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

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

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

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

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

[[[[.,.],.],.],[.,.]] => 0

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

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

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

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

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

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

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

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

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

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

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

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

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

[[[[[.,.],.],.],.],.] => 0

[.,[.,[.,[.,[.,[.,.]]]]]] => 0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

>>> Load all 625 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 internal nodes of a binary tree.
That is, the total number of nodes of the tree minus St000203The number of external nodes of a binary tree.. A counting formula for the total number of internal nodes across all binary trees of size $n$ is given in [1]. This is equivalent to the number of internal triangles in all triangulations of an $(n+1)$-gon.

References

[1] Number of internal triangles in all triangulations of an (n+1)-gon. OEIS:A002058

Code

# BinaryTree -> Bool
def is_leaf(b):
    return b == BinaryTree('.')

# BinaryTree -> Int
def get_external_node(b, flag):
    count = 0;
    if is_leaf(b):
        return 0
    else:
        if (flag): # True counts the left side
            if not is_leaf(b[0]):
                return 1 + get_external_node(b[0], True)
        else: # False counts the right side
            if not is_leaf(b[1]):
                return 1 + get_external_node(b[1], False)
    return count

# BinaryTree -> Int
def external_node_count(b):
    return 1 + get_external_node(b, True) + get_external_node(b, False)

def size(b):
     if not b:
         return 1
     else:
         return size(b[0])+size(b[1])

def statistic(b):
    return size(b)-1-external_node_count(b)

Created

May 16, 2014 at 20:57 by Joseph Ching

Updated

Dec 30, 2016 at 10:54 by Christian Stump