- FindStat

edit this statistic or download as text // json

Identifier

St000203: Binary trees ⟶ ℤ

Values

[.,.] => 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

>>> Load all 1359 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 external nodes of a binary tree.
That is, the number of nodes that can be reached from the root by only left steps or only right steps, plus $1$ for the root node itself. A counting formula for the number of external node in all binary trees of size $n$ can be found in [1].

References

[1] Expansion of (1+x*C)*C^3, where C = (1-(1-4*x)^(1/2))/(2*x) is g.f. for Catalan numbers, A000108. OEIS:A070031

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 statistic(b):
    """
    sage: [sum(statistic(b) for b in BinaryTrees(n)) for n in range(1,8)]
    [1, 4, 13, 42, 138, 462, 1573]
    """
    return 1 + get_external_node(b, True) + get_external_node(b, False)

Created

May 16, 2014 at 17:26 by Joseph Ching

Updated

Jan 17, 2018 at 23:01 by Martin Rubey