- FindStat

edit this statistic or download as text // json

Identifier

St000523: Ordered trees ⟶ ℤ

Values

[[]] => 0

[[],[]] => 0

[[[]]] => 1

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

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

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

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

[[[[]]]] => 1

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

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

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

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

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

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

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

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

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

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

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

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

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

[[[[[]]]]] => 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[[[[[[]]]]]] => 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

>>> Load all 1404 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 2-protected nodes of a rooted tree.
This is the number of nodes with minimal distance two to a leaf. The number of trees with no 2-protected nodes is oeis:A143363.

References

[1] Copenhaver, K. $k$-protected vertices in unlabeled rooted plane trees arXiv:1606.00083

Code

def protection_aux(T, k):
    """Return the number of nodes whose minimal distance to a leaf is k
    and the minimal distance of the root to a leaf.

    """
    children = [protection_aux(t, k) for t in T]
    if len(children) == 0:
        if k == 0:
            return (1, 0)
        else:
            return (0, 0)

    kids = sum(num for num, _ in children)
    root = 1 + min(p for _, p in children)
    if root == k:
        return (1 + kids, root)
    else:
        return (kids, root)

def statistic(T):
    """Return the number of nodes whose minimal distance to a leaf is k"""
    return protection_aux(T, 2)[0]

Created

Jun 02, 2016 at 09:40 by Martin Rubey

Updated

Dec 26, 2017 at 10:04 by Martin Rubey