view pending changes or download as text // json
Identifier
Mp00325: Permutations —Ones-to-Leading⟶ Permutations
Images
=>
click to show experimental identities (only identities of compositions of up to three maps are shown)
Description
The unique permutation obtained by applying the Foata-Riordan map to obtain a Prüfer code, then prepending 0 and cyclically shifting.
Let $c_1, ..., c_{n-1}$ be the Prüfer code obtained via the Foata-Riordan map described in [1, eq (1.2)] and let $c_0 = 0$.
This map returns the a unique permutation $q_1, ..., q_n$ such that $q_i - c_{i-1}$ is constant modulo $n+1$.
This map is the same as Map299 for parking functions, which is closed under permutations.
References
[1] Foata, D., Riordan, J. Mappings of acyclic and parking functions MathSciNet:0335294
Properties
bijective, graded
Sage code
def mapping(p):
    if not p:
        return p
    return perm_to_pruefer_foata_riordan_circ(p)


def perm_to_pruefer_foata_riordan_circ(p):
    n = len(p)
    tau = Permutation(p)
    pi = tau.inverse()
    E = [(0, i) if c == 1 else (i, pi(c-1)) for i, c in enumerate(p, 1)]
    V = list(range(n+1))
    G = Graph([V, E])
    c = []
    for _ in range(n-1):
        for u in V:
            if G.degree(u) == 1:
                c.append(G[u][0])
                G.delete_vertex(u)
                V.remove(u)
                break
    
    c = [0] + c
    c1 = [(e - pi(n)) % (n+1) for e in c]

    return c1
Weight
51
Created
Aug 21, 2024 at 02:31 by Cyrus Young
Updated
Aug 21, 2024 at 02:31 by Cyrus Young