- FindStat

edit this map or download as text // json

Identifier

Mp00139: Ordered trees —Zeilberger's Strahler bijection⟶ Binary trees

Images

[] => .

[[]] => [.,.]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

>>> Load all 2500 entries. <<<

click to show experimental identities (only identities of compositions of up to three maps are shown)

Description

Zeilberger's Strahler bijection between ordered and binary trees.
This is a bijection sending the pruning number of the ordered tree to the Strahler number of the binary tree.

References

[1] Zeilberger, D. A bijection from ordered trees to binary trees that sends the pruning order to the Strahler number MathSciNet:1058712

Properties

bijective, graded

Sage code

def mapping(t):
    """
    sage: mapping([])
    .

    sage: mapping([[]])
    [., .]

    sage: [mapping(t) for t in OrderedTrees(3)]
    [[., [., .]], [[., .], .]]
    """
    def prune(t):
        def is_branch(b):
            n = len(b)
            return n == 0 or (n == 1 and is_branch(b[0]))

        if len(t) == 0:
            return []
        else:
            return [prune(b) for b in t if not is_branch(b) ]

    def pruning_order(t):
        o = 0
        while len(t) > 0:
            t = prune(t)
            o += 1
        return o

    def below(t):
        t1 = t[0]
        t2 = t[1:]

        k = pruning_order(t)
        k1 = pruning_order(t1)
        k2 = pruning_order(t2)
        if (k1 <= k-1 and k2 == k) or (k1 == k-1 and k2 == k-1):
            return (t1, t2)
        elif k1 == k-1 and k2 <= k-2:
            i = 0
            while pruning_order(t1[:i+1]) <= k-2:
                i += 1
            f1 = t1[:i]
            s1 = t1[i]
            j = i+1
            while pruning_order(t1[i+1:j+1]) <= k-2:
                j += 1
            f2 = t1[i+1:j]
            return (f1+[s1]+f2, t2+t1[j:])
        elif k1 == k:
            i = 0
            while pruning_order(t1[:i+1]) <= k-1:
                i += 1
            f1 = t1[:i]
            s1 = t1[i]
            f2 = t1[i+1:]
            return (f1+[s1]+t2, f2)

    if len(t) == 0:
        return BinaryTree()
    else:
        u1, u2 = below(t)
        return BinaryTree([mapping(u1), mapping(u2)])

Weight

Created

Jan 29, 2020 at 13:27 by FindStatCrew

Updated

Jan 29, 2020 at 13:27 by Martin Rubey