There are 4 pending maps:
Identifier
Name
ones to leading
Diff Name
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 Mp00299ones to leading restricted to permutations.
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 Mp00299ones to leading restricted to permutations.
Diff 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 isthe same as Map299 for parking functions, which is closed under[[Mp00299]] restricted to permutations.
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
References
[1] Foata, D., Riordan, J. Mappings of acyclic and parking functions MathSciNet:0335294
Sage code
def mapping(p):
if not p:
return p
return permutation_to_pruefer_foata_riordan_circular(p)
def permutation_to_pruefer_foata_riordan_circular(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 Permutation(c1)
Properties
bijective, graded
Created
Aug 21, 2024 at 02:31 by Cyrus Young
Updated
Feb 01, 2025 at 16:18 by Martin Rubey
Identifier
Name
ones to leading
Description
The unique parking function obtained by applying the Foata-Riordan map to obtain a Prüfer code, then prepending 0 and cyclically shifting.
Let $c_1,\dots,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 unique parking function $(q_1,\dots,q_n)$ such that $q_i-c_{i-1}$ is constant modulo $n+1$, see [2, sec 4].
This map sends the number of ones to the number of occurrences of the first element.
Let $c_1,\dots,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 unique parking function $(q_1,\dots,q_n)$ such that $q_i-c_{i-1}$ is constant modulo $n+1$, see [2, sec 4].
This map sends the number of ones to the number of occurrences of the first element.
Diff Description
The unique parking function obtained by applying the Foata-Riordan map to obtain a Prüfer code, then prepending 0 and cyclically shifting.
Let c_1,\dots,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 thea unique parking function (q_1,\dots,q_n) such that q_i-c_{i-1} is constant modulo n+1, see [2, sec 4].
This map sends the number of ones to the number of occurrences of the first element.
Let c_1,\dots,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
This map sends the number of ones to the number of occurrences of the first element.
References
[1] Foata, D., Riordan, J. Mappings of acyclic and parking functions MathSciNet:0335294
Sage code
def mapping(p):
if not p:
return p
return pruefer_to_parking_circular(parking_to_pruefer_foata_riordan(p))
def pruefer_to_parking_circular(c):
pc = [0] + list(c)
n = len(pc)
P = ParkingFunctions(n)
for i in range(n):
if pc in P:
break
pc = [(e + 1) % (n+1) for e in pc]
return ParkingFunction(pc)
def parking_to_pruefer_foata_riordan(p):
n = len(p)
tau = Permutation([sum(1 for j in range(n)
if p[j] < p[i] or (p[j] == p[i] and j <= i))
for i in range(n)])
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
return c
Properties
bijective, graded
Created
Jun 16, 2023 at 15:26 by Martin Rubey
Updated
Feb 01, 2025 at 16:08 by Martin Rubey
Identifier
Mp00000:
Dyck paths
—inverse Kreweras complement⟶
Dyck paths
Name
inverse Kreweras complement
Description
Return the inverse of the Kreweras complement of a Dyck path, regarded as a noncrossing set partition.
To identify Dyck paths and noncrossing set partitions, this maps uses the following classical bijection. The number of down steps after the $i$-th up step of the Dyck path is the size of the block of the set partition whose maximal element is $i$. If $i$ is not a maximal element of a block, the $(i+1)$-st step is also an up step.
To identify Dyck paths and noncrossing set partitions, this maps uses the following classical bijection. The number of down steps after the $i$-th up step of the Dyck path is the size of the block of the set partition whose maximal element is $i$. If $i$ is not a maximal element of a block, the $(i+1)$-st step is also an up step.
Diff Description
Return the inverse of the Kreweras complement of a Dyck path, regarded as a noncrossing set partition.
To identify Dyck paths and noncrossing set partitions, this maps uses the following classical bijection. The number of down steps after the i-th up step of the Dyck path is the size of the block of the set partition whose maximal element is i. If i is not a maximal element of a block, the (i+1)-st step is also an up step.
To identify Dyck paths and noncrossing set partitions, this maps uses the following classical bijection. The number of down steps after the i-th up step of the Dyck path is the size of the block of the set partition whose maximal element is i. If i is not a maximal element of a block, the (i+1)-st step is also an up step.
Sage code
def mapping(d):
r"""
Compute the Kreweras complement of a Dyck path, regarded as a
noncrossing partition.
"""
n = len(d) / 2
if not n:
return d
D = DyckWords(n)
pi = D(d).to_noncrossing_partition().to_permutation()
c = Permutation(list(range(2,n+1))+[1])
p = SetPartition((c*pi.inverse()).to_cycles())
return D.from_noncrossing_partition(p)
Properties
bijective, graded
Created
Jan 25, 2025 at 18:37 by Martin Rubey
Updated
Jan 26, 2025 at 17:20 by Martin Rubey
3 Comments (hide)
Christian Stump
26 Jan 16:24
26 Jan 16:24
one cannot regard a dyck path as a noncrossing set partition in a canonical way. könntest du das präzisieren, welche bijektion du meinst?
Martin Rubey
26 Jan 17:22
26 Jan 17:22
Good point, I agree. The reason for this choice is that it gives rowmotion on the Stanley lattice of Dyck paths, but I don't think that I can make this precise right now.
Sam Hopkins
30 Jan 0:51
30 Jan 0:51
A simpler thing to do is view the Dyck path as a noncrossing perfect matching of [2n], where we draw open parentheses for up steps and close parentheses for down steps and match in the natural way, and then rotate the noncrossing matching, and then apply the same bijection in reverse to get a Dyck path. This will have the same orbit structure of Kreweras complementation.
Identifier
Mp00000:
Ordered trees
—DeBruijn-Morselt plane tree automorphism⟶
Ordered trees
Description
This automorphism on the set of plane trees with a given number of vertices is the combination of the two "canonical" bijections between plane trees and binary trees, using either the left or right branches. In [3] Shapiro essentially attributes this automorphism to DeBruijn and Morselt [1], hence the name I chose. Shapiro shows in that paper that for a large subset of plane trees (those corresponding to compositions), the sixth power of the automorphism acts as the identity on this subset. However, its behavior in general is quite chaotic. In [2] Donaghey studies this automorphism further and shows that its behavior on all trees can be reduced to its behavior on certain "primitive" trees.
References
[1] de Bruijn, N. G. and Morselt, B. J. M. "A note on plane trees." J. Combinatorial Theory 2 (1967), 27–34. MR0205872
[2] Donaghey, Robert. "Automorphisms on Catalan trees and bracketings." J. Combin. Theory Ser. B 29 (1980), no. 1, 75–90. MR0584162
[3] Shapiro, Louis W. "The cycle of six." Fibonacci Quart. 17 (1979), no. 3, 253–259. MR0549808
[2] Donaghey, Robert. "Automorphisms on Catalan trees and bracketings." J. Combin. Theory Ser. B 29 (1980), no. 1, 75–90. MR0584162
[3] Shapiro, Louis W. "The cycle of six." Fibonacci Quart. 17 (1979), no. 3, 253–259. MR0549808
Sage code
def mapping(T):
return T.to_binary_tree_right_branch().to_ordered_tree_left_branch()
Properties
bijective, graded
Created
Jul 01, 2024 at 02:15 by Sam Hopkins
Updated
Jul 01, 2024 at 02:15 by Sam Hopkins
