Identifier
Mp00026:
Dyck paths
—to ordered tree⟶
Ordered trees
Mp00047: Ordered trees —to poset⟶ Posets
Mp00110: Posets —Greene-Kleitman invariant⟶ Integer partitions
Mp00047: Ordered trees —to poset⟶ Posets
Mp00110: Posets —Greene-Kleitman invariant⟶ Integer partitions
Images
[1,0] => [[]] => ([(0,1)],2) => [2]
[1,0,1,0] => [[],[]] => ([(0,2),(1,2)],3) => [2,1]
[1,1,0,0] => [[[]]] => ([(0,2),(2,1)],3) => [3]
[1,0,1,0,1,0] => [[],[],[]] => ([(0,3),(1,3),(2,3)],4) => [2,1,1]
[1,0,1,1,0,0] => [[],[[]]] => ([(0,3),(1,2),(2,3)],4) => [3,1]
[1,1,0,0,1,0] => [[[]],[]] => ([(0,3),(1,2),(2,3)],4) => [3,1]
[1,1,0,1,0,0] => [[[],[]]] => ([(0,3),(1,3),(3,2)],4) => [3,1]
[1,1,1,0,0,0] => [[[[]]]] => ([(0,3),(2,1),(3,2)],4) => [4]
[1,0,1,0,1,0,1,0] => [[],[],[],[]] => ([(0,4),(1,4),(2,4),(3,4)],5) => [2,1,1,1]
[1,0,1,0,1,1,0,0] => [[],[],[[]]] => ([(0,4),(1,4),(2,3),(3,4)],5) => [3,1,1]
[1,0,1,1,0,0,1,0] => [[],[[]],[]] => ([(0,4),(1,4),(2,3),(3,4)],5) => [3,1,1]
[1,0,1,1,0,1,0,0] => [[],[[],[]]] => ([(0,4),(1,3),(2,3),(3,4)],5) => [3,1,1]
[1,0,1,1,1,0,0,0] => [[],[[[]]]] => ([(0,4),(1,2),(2,3),(3,4)],5) => [4,1]
[1,1,0,0,1,0,1,0] => [[[]],[],[]] => ([(0,4),(1,4),(2,3),(3,4)],5) => [3,1,1]
[1,1,0,0,1,1,0,0] => [[[]],[[]]] => ([(0,3),(1,2),(2,4),(3,4)],5) => [3,2]
[1,1,0,1,0,0,1,0] => [[[],[]],[]] => ([(0,4),(1,3),(2,3),(3,4)],5) => [3,1,1]
[1,1,0,1,0,1,0,0] => [[[],[],[]]] => ([(0,4),(1,4),(2,4),(4,3)],5) => [3,1,1]
[1,1,0,1,1,0,0,0] => [[[],[[]]]] => ([(0,4),(1,2),(2,4),(4,3)],5) => [4,1]
[1,1,1,0,0,0,1,0] => [[[[]]],[]] => ([(0,4),(1,2),(2,3),(3,4)],5) => [4,1]
[1,1,1,0,0,1,0,0] => [[[[]],[]]] => ([(0,4),(1,2),(2,4),(4,3)],5) => [4,1]
[1,1,1,0,1,0,0,0] => [[[[],[]]]] => ([(0,4),(1,4),(2,3),(4,2)],5) => [4,1]
[1,1,1,1,0,0,0,0] => [[[[[]]]]] => ([(0,4),(2,3),(3,1),(4,2)],5) => [5]
[1,0,1,0,1,0,1,0,1,0] => [[],[],[],[],[]] => ([(0,5),(1,5),(2,5),(3,5),(4,5)],6) => [2,1,1,1,1]
[1,0,1,0,1,0,1,1,0,0] => [[],[],[],[[]]] => ([(0,5),(1,5),(2,5),(3,4),(4,5)],6) => [3,1,1,1]
[1,0,1,0,1,1,0,0,1,0] => [[],[],[[]],[]] => ([(0,5),(1,5),(2,5),(3,4),(4,5)],6) => [3,1,1,1]
[1,0,1,0,1,1,0,1,0,0] => [[],[],[[],[]]] => ([(0,5),(1,5),(2,4),(3,4),(4,5)],6) => [3,1,1,1]
[1,0,1,0,1,1,1,0,0,0] => [[],[],[[[]]]] => ([(0,5),(1,5),(2,3),(3,4),(4,5)],6) => [4,1,1]
[1,0,1,1,0,0,1,0,1,0] => [[],[[]],[],[]] => ([(0,5),(1,5),(2,5),(3,4),(4,5)],6) => [3,1,1,1]
[1,0,1,1,0,0,1,1,0,0] => [[],[[]],[[]]] => ([(0,5),(1,4),(2,3),(3,5),(4,5)],6) => [3,2,1]
[1,0,1,1,0,1,0,0,1,0] => [[],[[],[]],[]] => ([(0,5),(1,5),(2,4),(3,4),(4,5)],6) => [3,1,1,1]
[1,0,1,1,0,1,0,1,0,0] => [[],[[],[],[]]] => ([(0,5),(1,5),(2,5),(3,4),(5,4)],6) => [3,1,1,1]
[1,0,1,1,0,1,1,0,0,0] => [[],[[],[[]]]] => ([(0,5),(1,4),(2,3),(3,5),(5,4)],6) => [4,1,1]
[1,0,1,1,1,0,0,0,1,0] => [[],[[[]]],[]] => ([(0,5),(1,5),(2,3),(3,4),(4,5)],6) => [4,1,1]
[1,0,1,1,1,0,0,1,0,0] => [[],[[[]],[]]] => ([(0,5),(1,4),(2,3),(3,5),(5,4)],6) => [4,1,1]
[1,0,1,1,1,0,1,0,0,0] => [[],[[[],[]]]] => ([(0,5),(1,4),(2,4),(3,5),(4,3)],6) => [4,1,1]
[1,0,1,1,1,1,0,0,0,0] => [[],[[[[]]]]] => ([(0,5),(1,4),(2,5),(3,2),(4,3)],6) => [5,1]
[1,1,0,0,1,0,1,0,1,0] => [[[]],[],[],[]] => ([(0,5),(1,5),(2,5),(3,4),(4,5)],6) => [3,1,1,1]
[1,1,0,0,1,0,1,1,0,0] => [[[]],[],[[]]] => ([(0,5),(1,4),(2,3),(3,5),(4,5)],6) => [3,2,1]
[1,1,0,0,1,1,0,0,1,0] => [[[]],[[]],[]] => ([(0,5),(1,4),(2,3),(3,5),(4,5)],6) => [3,2,1]
[1,1,0,0,1,1,0,1,0,0] => [[[]],[[],[]]] => ([(0,4),(1,4),(2,3),(3,5),(4,5)],6) => [3,2,1]
[1,1,0,0,1,1,1,0,0,0] => [[[]],[[[]]]] => ([(0,3),(1,4),(2,5),(3,5),(4,2)],6) => [4,2]
[1,1,0,1,0,0,1,0,1,0] => [[[],[]],[],[]] => ([(0,5),(1,5),(2,4),(3,4),(4,5)],6) => [3,1,1,1]
[1,1,0,1,0,0,1,1,0,0] => [[[],[]],[[]]] => ([(0,4),(1,4),(2,3),(3,5),(4,5)],6) => [3,2,1]
[1,1,0,1,0,1,0,0,1,0] => [[[],[],[]],[]] => ([(0,5),(1,5),(2,5),(3,4),(5,4)],6) => [3,1,1,1]
[1,1,0,1,0,1,0,1,0,0] => [[[],[],[],[]]] => ([(0,5),(1,5),(2,5),(3,5),(5,4)],6) => [3,1,1,1]
[1,1,0,1,0,1,1,0,0,0] => [[[],[],[[]]]] => ([(0,5),(1,5),(2,3),(3,5),(5,4)],6) => [4,1,1]
[1,1,0,1,1,0,0,0,1,0] => [[[],[[]]],[]] => ([(0,5),(1,4),(2,3),(3,5),(5,4)],6) => [4,1,1]
[1,1,0,1,1,0,0,1,0,0] => [[[],[[]],[]]] => ([(0,5),(1,5),(2,3),(3,5),(5,4)],6) => [4,1,1]
[1,1,0,1,1,0,1,0,0,0] => [[[],[[],[]]]] => ([(0,5),(1,4),(2,4),(4,5),(5,3)],6) => [4,1,1]
[1,1,0,1,1,1,0,0,0,0] => [[[],[[[]]]]] => ([(0,5),(1,4),(2,5),(4,2),(5,3)],6) => [5,1]
[1,1,1,0,0,0,1,0,1,0] => [[[[]]],[],[]] => ([(0,5),(1,5),(2,3),(3,4),(4,5)],6) => [4,1,1]
[1,1,1,0,0,0,1,1,0,0] => [[[[]]],[[]]] => ([(0,3),(1,4),(2,5),(3,5),(4,2)],6) => [4,2]
[1,1,1,0,0,1,0,0,1,0] => [[[[]],[]],[]] => ([(0,5),(1,4),(2,3),(3,5),(5,4)],6) => [4,1,1]
[1,1,1,0,0,1,0,1,0,0] => [[[[]],[],[]]] => ([(0,5),(1,5),(2,3),(3,5),(5,4)],6) => [4,1,1]
[1,1,1,0,0,1,1,0,0,0] => [[[[]],[[]]]] => ([(0,4),(1,3),(3,5),(4,5),(5,2)],6) => [4,2]
[1,1,1,0,1,0,0,0,1,0] => [[[[],[]]],[]] => ([(0,5),(1,4),(2,4),(3,5),(4,3)],6) => [4,1,1]
[1,1,1,0,1,0,0,1,0,0] => [[[[],[]],[]]] => ([(0,5),(1,4),(2,4),(4,5),(5,3)],6) => [4,1,1]
[1,1,1,0,1,0,1,0,0,0] => [[[[],[],[]]]] => ([(0,5),(1,5),(2,5),(3,4),(5,3)],6) => [4,1,1]
[1,1,1,0,1,1,0,0,0,0] => [[[[],[[]]]]] => ([(0,5),(1,3),(3,5),(4,2),(5,4)],6) => [5,1]
[1,1,1,1,0,0,0,0,1,0] => [[[[[]]]],[]] => ([(0,5),(1,4),(2,5),(3,2),(4,3)],6) => [5,1]
[1,1,1,1,0,0,0,1,0,0] => [[[[[]]],[]]] => ([(0,5),(1,4),(2,5),(4,2),(5,3)],6) => [5,1]
[1,1,1,1,0,0,1,0,0,0] => [[[[[]],[]]]] => ([(0,5),(1,3),(3,5),(4,2),(5,4)],6) => [5,1]
[1,1,1,1,0,1,0,0,0,0] => [[[[[],[]]]]] => ([(0,5),(1,5),(3,2),(4,3),(5,4)],6) => [5,1]
[1,1,1,1,1,0,0,0,0,0] => [[[[[[]]]]]] => ([(0,5),(2,4),(3,2),(4,1),(5,3)],6) => [6]
[1,0,1,0,1,0,1,0,1,0,1,0] => [[],[],[],[],[],[]] => ([(0,6),(1,6),(2,6),(3,6),(4,6),(5,6)],7) => [2,1,1,1,1,1]
[1,0,1,0,1,0,1,0,1,1,0,0] => [[],[],[],[],[[]]] => ([(0,6),(1,6),(2,6),(3,6),(4,5),(5,6)],7) => [3,1,1,1,1]
[1,0,1,0,1,0,1,1,0,0,1,0] => [[],[],[],[[]],[]] => ([(0,6),(1,6),(2,6),(3,6),(4,5),(5,6)],7) => [3,1,1,1,1]
[1,0,1,0,1,0,1,1,0,1,0,0] => [[],[],[],[[],[]]] => ([(0,6),(1,6),(2,6),(3,5),(4,5),(5,6)],7) => [3,1,1,1,1]
[1,0,1,0,1,0,1,1,1,0,0,0] => [[],[],[],[[[]]]] => ([(0,6),(1,6),(2,6),(3,4),(4,5),(5,6)],7) => [4,1,1,1]
[1,0,1,0,1,1,0,0,1,0,1,0] => [[],[],[[]],[],[]] => ([(0,6),(1,6),(2,6),(3,6),(4,5),(5,6)],7) => [3,1,1,1,1]
[1,0,1,0,1,1,0,0,1,1,0,0] => [[],[],[[]],[[]]] => ([(0,6),(1,6),(2,5),(3,4),(4,6),(5,6)],7) => [3,2,1,1]
[1,0,1,0,1,1,0,1,0,0,1,0] => [[],[],[[],[]],[]] => ([(0,6),(1,6),(2,6),(3,5),(4,5),(5,6)],7) => [3,1,1,1,1]
[1,0,1,0,1,1,0,1,0,1,0,0] => [[],[],[[],[],[]]] => ([(0,6),(1,6),(2,5),(3,5),(4,5),(5,6)],7) => [3,1,1,1,1]
[1,0,1,0,1,1,0,1,1,0,0,0] => [[],[],[[],[[]]]] => ([(0,6),(1,6),(2,5),(3,4),(4,5),(5,6)],7) => [4,1,1,1]
[1,0,1,0,1,1,1,0,0,0,1,0] => [[],[],[[[]]],[]] => ([(0,6),(1,6),(2,6),(3,4),(4,5),(5,6)],7) => [4,1,1,1]
[1,0,1,0,1,1,1,0,0,1,0,0] => [[],[],[[[]],[]]] => ([(0,6),(1,6),(2,5),(3,4),(4,5),(5,6)],7) => [4,1,1,1]
[1,0,1,0,1,1,1,0,1,0,0,0] => [[],[],[[[],[]]]] => ([(0,6),(1,6),(2,5),(3,5),(4,6),(5,4)],7) => [4,1,1,1]
[1,0,1,0,1,1,1,1,0,0,0,0] => [[],[],[[[[]]]]] => ([(0,3),(1,6),(2,6),(3,5),(4,6),(5,4)],7) => [5,1,1]
[1,0,1,1,0,0,1,0,1,0,1,0] => [[],[[]],[],[],[]] => ([(0,6),(1,6),(2,6),(3,6),(4,5),(5,6)],7) => [3,1,1,1,1]
[1,0,1,1,0,0,1,0,1,1,0,0] => [[],[[]],[],[[]]] => ([(0,6),(1,6),(2,5),(3,4),(4,6),(5,6)],7) => [3,2,1,1]
[1,0,1,1,0,0,1,1,0,0,1,0] => [[],[[]],[[]],[]] => ([(0,6),(1,6),(2,5),(3,4),(4,6),(5,6)],7) => [3,2,1,1]
[1,0,1,1,0,0,1,1,0,1,0,0] => [[],[[]],[[],[]]] => ([(0,6),(1,5),(2,5),(3,4),(4,6),(5,6)],7) => [3,2,1,1]
[1,0,1,1,0,0,1,1,1,0,0,0] => [[],[[]],[[[]]]] => ([(0,6),(1,3),(2,4),(3,5),(4,6),(5,6)],7) => [4,2,1]
[1,0,1,1,0,1,0,0,1,0,1,0] => [[],[[],[]],[],[]] => ([(0,6),(1,6),(2,6),(3,5),(4,5),(5,6)],7) => [3,1,1,1,1]
[1,0,1,1,0,1,0,0,1,1,0,0] => [[],[[],[]],[[]]] => ([(0,6),(1,5),(2,5),(3,4),(4,6),(5,6)],7) => [3,2,1,1]
[1,0,1,1,0,1,0,1,0,0,1,0] => [[],[[],[],[]],[]] => ([(0,6),(1,6),(2,5),(3,5),(4,5),(5,6)],7) => [3,1,1,1,1]
[1,0,1,1,0,1,0,1,0,1,0,0] => [[],[[],[],[],[]]] => ([(0,6),(1,6),(2,6),(3,6),(4,5),(6,5)],7) => [3,1,1,1,1]
[1,0,1,1,0,1,0,1,1,0,0,0] => [[],[[],[],[[]]]] => ([(0,6),(1,6),(2,5),(3,4),(4,6),(6,5)],7) => [4,1,1,1]
[1,0,1,1,0,1,1,0,0,0,1,0] => [[],[[],[[]]],[]] => ([(0,6),(1,6),(2,5),(3,4),(4,5),(5,6)],7) => [4,1,1,1]
[1,0,1,1,0,1,1,0,0,1,0,0] => [[],[[],[[]],[]]] => ([(0,6),(1,6),(2,5),(3,4),(4,6),(6,5)],7) => [4,1,1,1]
[1,0,1,1,0,1,1,0,1,0,0,0] => [[],[[],[[],[]]]] => ([(0,4),(1,4),(2,5),(3,6),(4,6),(6,5)],7) => [4,1,1,1]
[1,0,1,1,0,1,1,1,0,0,0,0] => [[],[[],[[[]]]]] => ([(0,6),(1,5),(2,3),(3,4),(4,5),(5,6)],7) => [5,1,1]
[1,0,1,1,1,0,0,0,1,0,1,0] => [[],[[[]]],[],[]] => ([(0,6),(1,6),(2,6),(3,4),(4,5),(5,6)],7) => [4,1,1,1]
[1,0,1,1,1,0,0,0,1,1,0,0] => [[],[[[]]],[[]]] => ([(0,6),(1,3),(2,4),(3,5),(4,6),(5,6)],7) => [4,2,1]
[1,0,1,1,1,0,0,1,0,0,1,0] => [[],[[[]],[]],[]] => ([(0,6),(1,6),(2,5),(3,4),(4,5),(5,6)],7) => [4,1,1,1]
[1,0,1,1,1,0,0,1,0,1,0,0] => [[],[[[]],[],[]]] => ([(0,6),(1,6),(2,5),(3,4),(4,6),(6,5)],7) => [4,1,1,1]
[1,0,1,1,1,0,0,1,1,0,0,0] => [[],[[[]],[[]]]] => ([(0,5),(1,4),(2,3),(3,6),(4,6),(6,5)],7) => [4,2,1]
[1,0,1,1,1,0,1,0,0,0,1,0] => [[],[[[],[]]],[]] => ([(0,6),(1,6),(2,5),(3,5),(4,6),(5,4)],7) => [4,1,1,1]
[1,0,1,1,1,0,1,0,0,1,0,0] => [[],[[[],[]],[]]] => ([(0,4),(1,4),(2,5),(3,6),(4,6),(6,5)],7) => [4,1,1,1]
[1,0,1,1,1,0,1,0,1,0,0,0] => [[],[[[],[],[]]]] => ([(0,6),(1,6),(2,6),(3,5),(4,5),(6,4)],7) => [4,1,1,1]
[1,0,1,1,1,0,1,1,0,0,0,0] => [[],[[[],[[]]]]] => ([(0,6),(1,5),(2,3),(3,6),(4,5),(6,4)],7) => [5,1,1]
>>> Load all 308 entries. <<<Map
to ordered tree
Description
Sends a Dyck path to the ordered tree encoding the heights of the path.
This map is recursively defined as follows: A Dyck path $D$ of semilength $n$ may be decomposed, according to its returns (St000011The number of touch points (or returns) of a Dyck path.), into smaller paths $D_1,\dots,D_k$ of respective semilengths $n_1,\dots,n_k$ (so one has $n = n_1 + \dots n_k$) each of which has no returns.
Denote by $\tilde D_i$ the path of semilength $n_i-1$ obtained from $D_i$ by removing the initial up- and the final down-step.
This map then sends $D$ to the tree $T$ having a root note with ordered children $T_1,\dots,T_k$ which are again ordered trees computed from $D_1,\dots,D_k$ respectively.
The unique path of semilength $1$ is sent to the tree consisting of a single node.
This map is recursively defined as follows: A Dyck path $D$ of semilength $n$ may be decomposed, according to its returns (St000011The number of touch points (or returns) of a Dyck path.), into smaller paths $D_1,\dots,D_k$ of respective semilengths $n_1,\dots,n_k$ (so one has $n = n_1 + \dots n_k$) each of which has no returns.
Denote by $\tilde D_i$ the path of semilength $n_i-1$ obtained from $D_i$ by removing the initial up- and the final down-step.
This map then sends $D$ to the tree $T$ having a root note with ordered children $T_1,\dots,T_k$ which are again ordered trees computed from $D_1,\dots,D_k$ respectively.
The unique path of semilength $1$ is sent to the tree consisting of a single node.
Map
to poset
Description
Return the poset obtained by interpreting the tree as the Hasse diagram of a graph.
Map
Greene-Kleitman invariant
Description
The Greene-Kleitman invariant of a poset.
This is the partition $(c_1 - c_0, c_2 - c_1, c_3 - c_2, \ldots)$, where $c_k$ is the maximum cardinality of a union of $k$ chains of the poset. Equivalently, this is the conjugate of the partition $(a_1 - a_0, a_2 - a_1, a_3 - a_2, \ldots)$, where $a_k$ is the maximum cardinality of a union of $k$ antichains of the poset.
This is the partition $(c_1 - c_0, c_2 - c_1, c_3 - c_2, \ldots)$, where $c_k$ is the maximum cardinality of a union of $k$ chains of the poset. Equivalently, this is the conjugate of the partition $(a_1 - a_0, a_2 - a_1, a_3 - a_2, \ldots)$, where $a_k$ is the maximum cardinality of a union of $k$ antichains of the poset.
searching the database
Sorry, this map was not found in the database.