- FindStat

edit this map or download as text // json

Identifier

Mp00297: Parking functions —ordered tree⟶ Ordered trees

Images

[1] => [[]]

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

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

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

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

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

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

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

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

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

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

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

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

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

[1,2,3] => [[[],[]]]

[1,3,2] => [[[[]]]]

[2,1,3] => [[[[]]]]

[2,3,1] => [[[[]]]]

[3,1,2] => [[[[]]]]

[3,2,1] => [[[],[]]]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[1,1,2,3] => [[],[[],[]]]

[1,1,3,2] => [[],[[[]]]]

[1,2,1,3] => [[[[[]]]]]

[1,2,3,1] => [[[],[[]]]]

[1,3,1,2] => [[[[[]]]]]

[1,3,2,1] => [[[[],[]]]]

[2,1,1,3] => [[],[[[]]]]

[2,1,3,1] => [[[[[]]]]]

[2,3,1,1] => [[],[[[]]]]

[3,1,1,2] => [[[]],[[]]]

[3,1,2,1] => [[[[[]]]]]

[3,2,1,1] => [[],[[],[]]]

[1,1,2,4] => [[],[[[]]]]

[1,1,4,2] => [[],[[],[]]]

[1,2,1,4] => [[[[[]]]]]

[1,2,4,1] => [[[[],[]]]]

[1,4,1,2] => [[[[[]]]]]

[1,4,2,1] => [[[],[[]]]]

[2,1,1,4] => [[],[[[]]]]

[2,1,4,1] => [[[[[]]]]]

[2,4,1,1] => [[],[[],[]]]

[4,1,1,2] => [[[]],[[]]]

[4,1,2,1] => [[[[[]]]]]

[4,2,1,1] => [[[]],[[]]]

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

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

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

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

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

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

[1,1,3,4] => [[],[[[]]]]

[1,1,4,3] => [[],[[[]]]]

[1,3,1,4] => [[[[],[]]]]

[1,3,4,1] => [[[],[[]]]]

[1,4,1,3] => [[[[],[]]]]

[1,4,3,1] => [[[],[[]]]]

[3,1,1,4] => [[],[[],[]]]

[3,1,4,1] => [[[],[[]]]]

[3,4,1,1] => [[],[[[]]]]

[4,1,1,3] => [[],[[],[]]]

[4,1,3,1] => [[[],[[]]]]

[4,3,1,1] => [[[]],[[]]]

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

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

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

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

[1,2,2,3] => [[],[[],[]]]

[1,2,3,2] => [[[],[[]]]]

[1,3,2,2] => [[],[[[]]]]

[2,1,2,3] => [[[[],[]]]]

[2,1,3,2] => [[[],[[]]]]

[2,2,1,3] => [[],[[[]]]]

[2,2,3,1] => [[],[[[]]]]

[2,3,1,2] => [[[],[[]]]]

[2,3,2,1] => [[[[],[]]]]

[3,1,2,2] => [[],[[[]]]]

[3,2,1,2] => [[[],[[]]]]

[3,2,2,1] => [[],[[],[]]]

[1,2,2,4] => [[[]],[[]]]

[1,2,4,2] => [[[[[]]]]]

[1,4,2,2] => [[],[[],[]]]

[2,1,2,4] => [[[[[]]]]]

>>> Load all 18248 entries. <<<

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

Description

The ordered tree associated with the parking function by Pollak.
Let $(p_1,\dots,p_n)$ be a parking function. Set $c_i = p_{i+1}-p_i \mod (n+1)$ to obtain a Prüfer code, and return the underlying ordered tree rooted at $0$.

References

[1] Riordan, J. Ballots and trees MathSciNet:0234843

Properties

surjective, graded

Sage code

def pollak_riordan_to_pruefer(p):
    n = len(p)
    return [(p[i+1] - p[i]) % (n+1) for i in range(n-1)]

def pruefer_to_tree(c):
    c = list(c)
    n = len(c)
    V = list(range(n+2))
    G = Graph([V, []])
    for _ in range(n):
        i, u = next((i, u) for i, u in enumerate(V) if u not in c)
        del V[i]
        v = c.pop(0)
        G.add_edge(u, v)
    G.add_edge(V)
    return to_tree(G, 0)

def to_tree(G, r):
    if not G:
        return LabelledRootedTree([], r)
    roots = G[r]
    G.delete_vertex(r)
    return LabelledRootedTree([to_tree(G.subgraph(G.connected_component_containing_vertex(u)), u)
                               for u in roots], r)

def mapping(p):
    return OrderedTree(pruefer_to_tree(pollak_riordan_to_pruefer(p)))

Weight

Created

Jun 16, 2023 at 12:30 by Martin Rubey

Updated

Jun 16, 2023 at 13:38 by Martin Rubey