- FindStat

edit this statistic or download as text // json

Identifier

St000196: Binary trees ⟶ ℤ (values match St000201The number of leaf nodes in a binary tree.)

Values

[.,.] => 0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

>>> 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 occurrences of the contiguous pattern [[.,.],[.,.]] in a binary tree.
Equivalently, this is the number of branches in the tree, i.e. the number of nodes with two children. Binary trees avoiding this pattern are counted by $2^{n-2}$.

Code

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

# BinaryTree -> Int
def hat_count(b):
    if is_leaf(b):
        return 0
    if not is_leaf(b[0]) and not is_leaf(b[1]):
        return 1
    return 0

# (a -> a -> a) -> (BinaryTree -> a) -> BinaryTree -> a
def fold_tree(f, g, b):
    if is_leaf(b):
        return g(b)
    else:
        return f(g(b), f(fold_tree(f, g, b[0]), fold_tree(f, g, b[1])))

def statistic(b):
    return fold_tree(lambda a,b: a+b, hat_count, b)

Created

May 15, 2014 at 08:57 by Joseph Ching

Updated

May 30, 2016 at 11:58 by Christian Stump