- FindStat

edit this statistic or download as text // json

Identifier

St000201: Binary trees ⟶ ℤ (values match St000196The number of occurrences of the contiguous pattern [[.,.],[.,.)

Values

[.,.] => 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[.,[[[.,.],[.,[.,.]]],.]] => 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 leaf nodes in a binary tree.
Equivalently, the number of cherries [1] in the complete binary tree.
The number of binary trees of size $n$, at least $1$, with exactly one leaf node for is $2^{n-1}$, see [2].
The number of binary tree of size $n$, at least $3$, with exactly two leaf nodes is $n(n+1)2^{n-2}$, see [3].

References

[1] Billey, S., Konvalinka, M., Matsen, F. A. I. On the enumeration of tanglegrams and tangled chains arXiv:1507.04976
[2] Powers of 2: a(n) = 2^n. OEIS:A000079
[3] a(n) = n*(n+1)*2^(n-2). OEIS:A001788

Code

def statistic(B):
    if B == BinaryTree():
        return 0
    if B == BinaryTree([]):
        return 1
    return sum(statistic(S) for S in B)

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

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

# (Num a) => a -> a -> a
def add(a, b):
    return a + b

# (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])))

for n in [0..7]:
    for b in BinaryTrees(n):
        indiv_count = fold_tree(add, leaf_count, b)
        print b, '=>', indiv_count

Created

May 16, 2014 at 09:02 by Joseph Ching

Updated

Mar 31, 2019 at 22:07 by Martin Rubey