The following bijection on rooted plane trees arises in the following context : the counting sequence of (rooted plane) trees with $n$ edges ($n+1$ vertices) and $k$ leaves is given by:

$$\frac{1}{n} {n \choose k} {n \choose k-1}$$

a sequence of numbers called the Narayana numbers, and they help to answer a question asked on math.SE to understand their symmetry in the number of leaves (replacing $k$ by $n-k-1$ in the above formula does not change its value).

The map is defined as follows (take your pencil !) : to a (rooted plane) tree on $n$ vertices, we will associate another (rooted plane) tree with $n$ vertices, by keeping the same vertex set (also the same root) and changing the edge set. To that end, it is enough to define the father of every vertex distinct from the root in the new tree, let's call it the new father.

Define a brother of a (non-root) vertex as a child of the same father. Consider a non-root vertex and look for the most recent ancestor of that vertex that has a brother to its right : this will the vertex itself if it has a brother to its right, or the father of this vertex if the vertex itself has no brother to its right but its father has, and so on...

  • In case there is such an ancestor : the new father is the brother immediately to the right of that ancestor.

  • In case there is no such ancestor : the new father is the root of the tree.

The root is left unchanged.

The reciprocal map is obtained by replacing the word "right" by the word "left" in the above description.

The map sends a tree on $n$ edges and $k$ leaves to a tree with the same number of edges but $n-k-1$ leaves.

(This is closely related, but distinct from what is called rotation bijection in computer science, see Flajolet and Sedgewick on p.73.)

Question : Has anyone already seen this map (or a close relative of it) in the literature ? For what use ?


As I mentioned in https://math.stackexchange.com/a/3328519/79593, Panyushev constructed a bijection between antichains of size $k$ and size $n-k$ for the Type $A_{n}$ root poset in Theorem 4.2 of "Ad-nilpotent ideals of a Borel subalgebra: generators and duality" (see citation below, also on arxiv at https://arxiv.org/abs/math/0303107). This is the same as a bijection on Dyck paths with $k$ peaks and $n-k$ peaks (up to indexing correctly). The tree bijection you describe is meant to accomplish the same thing. It would be worth checking if your bijection is the same as Panyushev's. (He came up with this bijection in a more general root system-theoretic context; it is the Type A version of a conjectured duality for "ad-nilpotent ideals of Borel subalgebras of simple Lie algebras.")

Panyushev, Dmitri I., ad-nilpotent ideals of a Borel subalgebra: generators and duality, J. Algebra 274, No. 2, 822-846 (2004). ZBL1067.17005.

EDIT: As pointed out in the comments, it appears this map is not the same one discussed by the OP. But I am leaving this answer as it still may be useful for context.

  • $\begingroup$ By the way, I vaguely remember hearing that via FindStat it was discovered that this bijection of Panyushev's was the same as a known bijection, maybe the rotation bijection, perhaps up to some simple change. But maybe I am misremembering the story and that was about some other bijection. $\endgroup$ – Sam Hopkins Aug 20 '19 at 2:35
  • 1
    $\begingroup$ I am guessing that you are thinking of the FPSAC preentation, where I demonstrated that FindStat indicates that Panyushev's map is the same as the Lalanne-Kreweras complement (findstat.org/Mp00120). However, the composition of this map with the classical bijection to ordered trees is different from Olivier's, for example for trees on 4 nodes. $\endgroup$ – Martin Rubey Aug 20 '19 at 6:16
  • 1
    $\begingroup$ After checking the reference : as far as the symmetry is concerned, it is indeed simpler to think in terms of Ferrers diagrams...Thanks to both of you for quick and precise answers ! $\endgroup$ – Olivier Aug 20 '19 at 10:18
  • $\begingroup$ @MartinRubey: thanks for those clarifications. (Btw I can confirm that the "Mp" FindStat links take a very very long time for my computer to load.) $\endgroup$ – Sam Hopkins Aug 20 '19 at 14:17

The following is only half of an answer, but maybe useful nevertheless:

Plugging in the images of the trees on 4 vertices at http://www.findstat.org/MapFinder/OrderedTrees/OrderedTrees you obtain http://www.findstat.org/MapsDatabase/Mp00049/Mp00015.

(Warning: this page takes a very long time to render! There is no need for worry though, only a few kb of data are actually transferred.)

  • 1
    $\begingroup$ Thanks for your interest; I do not manage to load the result though. Would it be possible to display the pictures directly in the answer ? $\endgroup$ – Olivier Aug 19 '19 at 20:41
  • $\begingroup$ @Olivier: in what way does it fail? There is currently a big problem with findstat's performance, which we are trying to figure out. Currently it takes minutes, once the problem is fixed it should be microseconds again. I am very sorry for the inconvenience. $\endgroup$ – Martin Rubey Aug 20 '19 at 6:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.