OrderedTrees
A name from the enumeratio catalogue with no kernel of its own yet; this page carries its crosswalk only.
Catalogued in the enumeratio database, with crosswalk rows in oeis, sage; not yet written up here.
✓ checked against that system · ! checked, with disagreements (hover a chip)OEIS
A000108✓A120588✓SageMathsage.combinat.ordered_tree.OrderedTrees(size)OrderedTrees(...)Catalogued in the enumeratio database, with crosswalk rows in oeis, sage; not yet written up here.Typed signatures
| Type | Package | Applies |
|---|---|---|
(integer<0..>) -> indexed_collection<ordered_tree> | combinatorics | always |
Definition
Epsil, as the implementation runs it.
count(_n)
Apply((bd: integer) => 0 if 2 * _n < 0 || (2 * _n - 0) % 2 == 1 else Binomial(2 *
_n, bd) -
(0 if bd ==
0 else Binomial(2 * _n, bd - 1)), (2 * _n -
0 - (2 *
_n - 0) %
2) / 2)unrank(_n, _r)
Apply(
(op: list<integer>) => Fold(Function(Apply(
(ot: list<any>) => ReplaceAt(
ReplaceAt(os, 1, ot[1] + 1),
ot[1] + 2,
[],
) if op[oj] == 1 else Apply((oc: list<any>) => ReplaceAt(
ReplaceAt(os, 1, ot[1] - 1),
ot[1],
Join(oc, [ot[ot[1] + 1]]),
), ot[ot[1]]),
os,
), os, oj), Join(
[1, []],
Map(
Function(0, nz),
Range(
1,
2 *
_n,
1,
),
),
), Range(1, 2 *
_n, 1))[2],
Drop(Fold(Function(us if us[3] == 0 else Apply(
(uc0: integer) => Join(
[
us[1] - 0,
us[2] + 1,
us[3] - 1,
1,
],
Drop(us, 4),
[1],
) if us[1] < uc0 else Join([
us[1] - uc0,
us[2] - 1,
us[3] - 1,
1,
], Drop(us, 4), [0]),
Apply(
(bd: integer) => 0 if us[3] - 1 <
us[2] + 1 ||
(us[3] - 1 -
(us[2] + 1)) %
2 ==
1 else Binomial(us[3] - 1, bd) -
(0 if bd == 0 else Binomial(us[3] - 1, bd - 1)),
(us[3] - 1 - (us[2] +
1) - (us[3] - 1 -
(us[2] + 1)) %
2) /
2,
) if 1 <= us[3] && us[2] +
1 >=
0 else 0,
), us, ui), [
_r,
0,
2 * _n,
1,
], Range(1, 2 *
_n, 1)), 4),
)rank(_n, _x)
Apply(
(or: list<any>) => Apply((op: list<integer>) => Fold(
Function(Apply(
(rc0: integer) => [
rs[1] + 0,
rs[2] + 1,
rs[3] - 1,
1,
] if rx == 1 else [
rs[1] + rc0,
rs[2] - 1,
rs[3] - 1,
1,
],
Apply(
(bd: integer) => 0 if rs[3] - 1 <
rs[2] + 1 ||
(rs[3] - 1 -
(rs[2] + 1)) %
2 ==
1 else Binomial(rs[3] - 1, bd) -
(0 if bd == 0 else Binomial(rs[3] - 1, bd - 1)),
(rs[3] - 1 -
(rs[2] + 1) -
(rs[3] - 1 -
(rs[2] + 1)) %
2) /
2,
) if 1 <= rs[3] &&
rs[2] + 1 >=
0 else 0,
), rs, rx),
[0, 0, 2 * _n, 1],
op,
)[1], Take(
Drop(
or,
4,
),
2 * _n,
)),
Fold(
Function(Apply((ft: list<any>) => ft if ft[1] == 0 else ReplaceAt(
ReplaceAt(
ReplaceAt(ft, 1, ft[1] - 1),
2,
ft[2] + 1,
),
ft[2] + 4,
0,
) if ft[2 *
(_n + 1) + 3 + ft[1]] ==
0 else ReplaceAt(ReplaceAt(ft, 1, ft[1] - 1), 3, 1) if ft[2 *
(_n + 1) +
3 +
2 * _n +
4 +
ft[1]] in
Integers else ReplaceAt(ReplaceAt(ft, 1, ft[1] - 1), 3, 1) if ft[1] +
Length(ft[2 *
(_n + 1) +
3 +
2 * _n +
4 +
ft[1]]) >
2 * _n +
4 else Fold(
Function(ReplaceAt(ReplaceAt(fa, 2 *
(_n + 1) +
3 +
2 * _n +
4 +
ft[1] + fi, ft[2 *
(_n + 1) +
3 +
2 * _n +
4 +
ft[1]][Length(ft[2 *
(_n + 1) +
3 +
2 * _n +
4 +
ft[1]]) +
1 -
fi]), 2 *
(_n + 1) +
3 +
ft[1] + fi, 1), fa, fi),
ReplaceAt(
ReplaceAt(ReplaceAt(ReplaceAt(ft, 1, ft[1] +
Length(ft[2 *
(_n + 1) +
3 +
2 * _n +
4 +
ft[1]])), 2, ft[2] + 1), ft[2] + 4, 1),
2 *
(_n + 1) + 3 + ft[1],
0,
),
Range(1, Length(ft[2 *
(_n + 1) +
3 +
2 * _n +
4 +
ft[1]]), 1),
), fs), fs, fj),
Join(
[1, 0, 0],
Map(Function(0, nz), Range(1, 2 * (_n + 1), 1)),
[1],
Map(Function(0, nz), Range(1, 2 * _n + 4 - 1, 1)),
[_x],
Map(Function(0, nz), Range(1, 2 * _n + 4 - 1, 1)),
),
Range(1, 2 * (_n + 1), 1),
),
)valid(_n, _x)
Apply(
(or: list<any>) => or[1] == 0 && or[2] == 2 * (_n + 1) && or[3] == 0,
Fold(
Function(Apply((ft: list<any>) => ft if ft[1] == 0 else ReplaceAt(
ReplaceAt(
ReplaceAt(ft, 1, ft[1] - 1),
2,
ft[2] + 1,
),
ft[2] + 4,
0,
) if ft[2 *
(_n + 1) + 3 + ft[1]] ==
0 else ReplaceAt(ReplaceAt(ft, 1, ft[1] - 1), 3, 1) if ft[2 *
(_n + 1) +
3 +
2 * _n +
4 +
ft[1]] in
Integers else ReplaceAt(ReplaceAt(ft, 1, ft[1] - 1), 3, 1) if ft[1] +
Length(ft[2 *
(_n + 1) +
3 +
2 * _n +
4 +
ft[1]]) >
2 * _n +
4 else Fold(
Function(ReplaceAt(ReplaceAt(fa, 2 *
(_n + 1) +
3 +
2 * _n +
4 +
ft[1] + fi, ft[2 *
(_n + 1) +
3 +
2 * _n +
4 +
ft[1]][Length(ft[2 *
(_n + 1) +
3 +
2 * _n +
4 +
ft[1]]) +
1 -
fi]), 2 *
(_n + 1) +
3 +
ft[1] + fi, 1), fa, fi),
ReplaceAt(
ReplaceAt(ReplaceAt(ReplaceAt(ft, 1, ft[1] +
Length(ft[2 *
(_n + 1) +
3 +
2 * _n +
4 +
ft[1]])), 2, ft[2] + 1), ft[2] + 4, 1),
2 *
(_n + 1) + 3 + ft[1],
0,
),
Range(1, Length(ft[2 *
(_n + 1) +
3 +
2 * _n +
4 +
ft[1]]), 1),
), fs), fs, fj),
Join(
[1, 0, 0],
Map(Function(0, nz), Range(1, 2 * (_n + 1), 1)),
[1],
Map(Function(0, nz), Range(1, 2 * _n + 4 - 1, 1)),
[_x],
Map(Function(0, nz), Range(1, 2 * _n + 4 - 1, 1)),
),
Range(1, 2 * (_n + 1), 1),
),
)Statistics
On OrderedTree, called as CombinatorialStat(x, "Name").
- AutomorphismGroupSizeSt000417The number of ways to permute identical children, at every vertex at once: the product, over the vertices, of the factorials of how many times each child tree occurs.
- BoundaryLengthSt000973The edges on the leftmost path from the root plus those on the rightmost.
- BoundaryLengthBeyondTrunkSt000975The edges on the leftmost path or the rightmost path from the root, less the trunk they share.
- BreadthSt001058The most vertices at any one depth.
- DistinctSubtreesSt000521The number of different subtrees.
- HeightSt000166The height: the most edges on a path from the root.
- InequivalentIncreasingTreeCountSt000416The number of increasing labelings of the tree up to its automorphisms: n! over the tree factorial and the automorphism group size.
- LargestOutDegreeSt000328The most children any vertex has.
- LeavesSt000167The number of vertices with no children.
- LinearExtensionCountSt000085The number of linear extensions of the tree as a poset: n! over the tree factorial.
- LongestPathVertexCountSt000094The most vertices on a path from the root: the height plus one.
- NonRootInternalNodesSt000168The number of vertices that are neither the root nor a leaf.
- OneProtectedNodeCountSt000522The number of vertices whose nearest leaf is exactly one edge away.
- PathLengthSt000400The sum of the depths of the vertices, the root's being 0.
- ProtectionNumberSt000700The edges from the root to the nearest leaf.
- PruningNumberSt000679The number of prunings, each deleting every maximal hanging branch (a path of single-child vertices to a leaf), that reduce the tree to a single vertex.
- RootDegreeSt000084The number of children of the root.
- StrahlerNumberSt000397The Strahler number: a leaf is 1, a vertex takes its largest child's, plus one if that value occurs twice.
- TreeFactorialSt000410The product, over the vertices, of the number of vertices at or below each.
- TrunkLengthSt000974The edges from the root to the first vertex that does not have exactly one child.
- TwoProtectedNodeCountSt000523The number of vertices whose nearest leaf is exactly two edges away.
Maps
Into and out of OrderedTree, called as CombinatorialMap(x, "Name"). Properties are the laws we state and what FindStat records.
From OrderedTree
- BinaryTreeOrderedTree → BinaryTreeinverseBijectionGraded mapMp00049An ordered tree as a binary tree with one fewer node: a vertex's left brother becomes its left child, its last child its right child, and the root goes.
- DeBruijnMorseltOrderedTree → OrderedTreebijectionBijectionGraded mapMp00328The right-branch bijection to binary trees followed by the left-branch bijection back: the de Bruijn-Morselt automorphism of the ordered trees.
- DyckPathOrderedTree → DyckPathinverseBijectionGraded mapMp00051An ordered tree as the Dyck path of its depth-first contour: an up step into each child, a down step out.
- MirrorOrderedTree → OrderedTreeinvolutionBijectionGraded mapInvolutionMp00048The left-right symmetry of an ordered tree: every node's children in the opposite order.
- RightBranchBinaryTreeOrderedTree → BinaryTreeinverseBijectionGraded mapMp00050An ordered tree as a binary tree with one fewer node: a vertex's right brother becomes its right child, its first child its left child, and the root goes.
- RotationOrderedTree → OrderedTreebijectionBijectionGraded mapMp00246Attach a leaf to the root, remove the leftmost leaf, and let the vertex it hung from become the root.
To OrderedTree
- OrderedTreeBinaryTree → OrderedTreeinverseBijectionGraded mapMp00010A binary tree as an ordered tree with one more vertex: a left child becomes its parent's left brother, a right child its parent's last child.
- OrderedTreeDyckPath → OrderedTreeinverseBijectionGraded mapMp00026A Dyck path as the ordered tree whose depth-first contour it is: an up step opens a child, a down step closes it.
- RightBranchOrderedTreeBinaryTree → OrderedTreeinverseBijectionGraded mapMp00015A binary tree as an ordered tree with one more vertex: a right child becomes its parent's right brother, a left child its parent's first child.
5 more in FindStat, not implemented here
- Mp00008BinaryTree → OrderedTreeInjectionGraded mapto complete tree
- Mp00046OrderedTree → LabeledGraphGraded mapto graph
- Mp00047OrderedTree → PosetsGraded mapto poset
- Mp00139OrderedTree → BinaryTreeBijectionGraded mapZeilberger's Strahler bijection
- Mp00297ParkingFunction → OrderedTreeSurjectionGraded mapordered tree