Identifier
Mp00008: Binary trees —to complete tree⟶ Ordered trees
Mp00051: Ordered trees —to Dyck path⟶ Dyck paths
Mp00120: Dyck paths —Lalanne-Kreweras involution⟶ Dyck paths
Mp00100: Dyck paths —touch composition⟶ Integer compositions
Images
=>
Cc0010;cc-rep-0Cc0021;cc-rep-1Cc0005;cc-rep-2Cc0005;cc-rep-3
[.,.]=>[[],[]]=>[1,0,1,0]=>[1,1,0,0]=>[2] [.,[.,.]]=>[[],[[],[]]]=>[1,0,1,1,0,1,0,0]=>[1,1,1,0,0,1,0,0]=>[4] [[.,.],.]=>[[[],[]],[]]=>[1,1,0,1,0,0,1,0]=>[1,1,0,1,1,0,0,0]=>[4] [.,[.,[.,.]]]=>[[],[[],[[],[]]]]=>[1,0,1,1,0,1,1,0,1,0,0,0]=>[1,1,1,1,0,0,1,0,0,1,0,0]=>[6] [.,[[.,.],.]]=>[[],[[[],[]],[]]]=>[1,0,1,1,1,0,1,0,0,1,0,0]=>[1,1,1,0,0,1,1,0,1,0,0,0]=>[6] [[.,.],[.,.]]=>[[[],[]],[[],[]]]=>[1,1,0,1,0,0,1,1,0,1,0,0]=>[1,1,0,1,1,1,0,0,0,1,0,0]=>[6] [[.,[.,.]],.]=>[[[],[[],[]]],[]]=>[1,1,0,1,1,0,1,0,0,0,1,0]=>[1,1,1,0,1,0,0,1,1,0,0,0]=>[6] [[[.,.],.],.]=>[[[[],[]],[]],[]]=>[1,1,1,0,1,0,0,1,0,0,1,0]=>[1,1,0,1,1,0,1,1,0,0,0,0]=>[6] [.,[.,[.,[.,.]]]]=>[[],[[],[[],[[],[]]]]]=>[1,0,1,1,0,1,1,0,1,1,0,1,0,0,0,0]=>[1,1,1,1,1,0,0,1,0,0,1,0,0,1,0,0]=>[8] [.,[.,[[.,.],.]]]=>[[],[[],[[[],[]],[]]]]=>[1,0,1,1,0,1,1,1,0,1,0,0,1,0,0,0]=>[1,1,1,1,0,0,1,1,0,0,1,0,1,0,0,0]=>[8] [.,[[.,.],[.,.]]]=>[[],[[[],[]],[[],[]]]]=>[1,0,1,1,1,0,1,0,0,1,1,0,1,0,0,0]=>[1,1,1,0,0,1,1,1,0,1,0,0,0,1,0,0]=>[8] [.,[[.,[.,.]],.]]=>[[],[[[],[[],[]]],[]]]=>[1,0,1,1,1,0,1,1,0,1,0,0,0,1,0,0]=>[1,1,1,1,0,0,1,0,1,1,0,0,1,0,0,0]=>[8] [.,[[[.,.],.],.]]=>[[],[[[[],[]],[]],[]]]=>[1,0,1,1,1,1,0,1,0,0,1,0,0,1,0,0]=>[1,1,1,0,0,1,1,0,1,1,0,1,0,0,0,0]=>[8] [[.,.],[.,[.,.]]]=>[[[],[]],[[],[[],[]]]]=>[1,1,0,1,0,0,1,1,0,1,1,0,1,0,0,0]=>[1,1,0,1,1,1,1,0,0,0,1,0,0,1,0,0]=>[8] [[.,.],[[.,.],.]]=>[[[],[]],[[[],[]],[]]]=>[1,1,0,1,0,0,1,1,1,0,1,0,0,1,0,0]=>[1,1,0,1,1,1,0,0,0,1,1,0,1,0,0,0]=>[8] [[.,[.,.]],[.,.]]=>[[[],[[],[]]],[[],[]]]=>[1,1,0,1,1,0,1,0,0,0,1,1,0,1,0,0]=>[1,1,1,0,1,0,0,1,1,1,0,0,0,1,0,0]=>[8] [[[.,.],.],[.,.]]=>[[[[],[]],[]],[[],[]]]=>[1,1,1,0,1,0,0,1,0,0,1,1,0,1,0,0]=>[1,1,0,1,1,0,1,1,1,0,0,0,0,1,0,0]=>[8] [[.,[.,[.,.]]],.]=>[[[],[[],[[],[]]]],[]]=>[1,1,0,1,1,0,1,1,0,1,0,0,0,0,1,0]=>[1,1,1,1,0,1,0,0,1,0,0,1,1,0,0,0]=>[8] [[.,[[.,.],.]],.]=>[[[],[[[],[]],[]]],[]]=>[1,1,0,1,1,1,0,1,0,0,1,0,0,0,1,0]=>[1,1,1,0,1,1,0,0,1,0,1,1,0,0,0,0]=>[8] [[[.,.],[.,.]],.]=>[[[[],[]],[[],[]]],[]]=>[1,1,1,0,1,0,0,1,1,0,1,0,0,0,1,0]=>[1,1,0,1,1,1,0,1,0,0,0,1,1,0,0,0]=>[8] [[[.,[.,.]],.],.]=>[[[[],[[],[]]],[]],[]]=>[1,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0]=>[1,1,1,0,1,0,1,1,0,0,1,1,0,0,0,0]=>[8] [[[[.,.],.],.],.]=>[[[[[],[]],[]],[]],[]]=>[1,1,1,1,0,1,0,0,1,0,0,1,0,0,1,0]=>[1,1,0,1,1,0,1,1,0,1,1,0,0,0,0,0]=>[8]
Map
to complete tree
Description
Return the same tree seen as an ordered tree. By default, leaves are transformed into actual nodes.
Map
to Dyck path
Description
Return the Dyck path of the corresponding ordered tree induced by the recurrence of the Catalan numbers, see wikipedia:Catalan_number.
This sends the maximal height of the Dyck path is the depth of the tree.
Map
Lalanne-Kreweras involution
Description
The Lalanne-Kreweras involution on Dyck paths.
Label the upsteps from left to right and record the labels on the first up step of each double rise. Do the same for the downsteps. Then form the Dyck path whose ascent lengths and descent lengths are the consecutives differences of the labels.
Map
touch composition
Description
Sends a Dyck path to its touch composition given by the composition of lengths of its touch points.