IncreasingBinaryTrees
A name from the enumeratio catalogue with no kernel of its own yet; this page carries its crosswalk only.
Binary trees on n labeled nodes, heap-ordered by label — n! of them.
IncreasingBinaryTrees(...)Binary trees on n labeled nodes, heap-ordered by label — n! of them.Typed signatures
| Type | Package | Applies |
|---|---|---|
(integer<0..>) -> indexed_collection<increasing_binary_tree> | combinatorics | always |
Definition
Epsil, as the implementation runs it.
count(_n)
_n!unrank(_n, _r)
Apply(
(ip: list<integer>) => Fold(Function(Fold(
Function(Apply((ct: list<any>) => Apply(
(cm: integer) => ReplaceAt(
ci,
(co - 1) *
(_n + 1) +
(co + cl -
1) +
1,
[
ip[cm],
ct[(co - 1) *
(_n + 1) +
(cm - 1) +
1],
ct[(cm + 1 -
1) *
(_n + 1) +
(co + cl -
1) +
1],
],
),
Apply((cb_init: integer) => Fold(
(cb: integer, cx) => Apply((cb_next: integer) => cb_next, cx if ip[cx] < ip[cb] else cb),
cb_init,
Range(co + 1, co + cl -
1, 1),
), co),
), ci), ci, co),
cs,
Range(1, _n - cl + 1, 1),
), cs, cl), Map(
Function(0, nz),
Range(
1,
(_n + 1) *
(_n + 1),
1,
),
), Range(1, _n, 1))[(1 - 1) *
(_n + 1) +
_n +
1],
Map(Function(Fold(
Function(
v + 1 if v >= (_r - _r % (_n - i)!) / (_n -
i)! %
(_n - i + 1) + 1 else v,
v,
i,
),
(_r - _r % (_n - j)!) / (_n - j)! % (_n - j + 1) + 1,
Range(j - 1, 1, -1),
), j), Range(1, _n, 1)),
)rank(_n, _x)
Apply((it: list<any>) => -1 if Length(it) != 2 * _n + 1 else Apply(
(ir: list<integer>) => Apply(
(ip: list<integer>) => Fold(Function(Apply(
(lb: integer) => lr *
(_n - lj +
1) +
(ip[lj] - 1 -
lb),
Fold(
Function(lc +
(1 if ip[li] < ip[lj] else 0), lc, li),
0,
Range(1, lj - 1, 1),
),
), lr, lj), 0, Range(1, _n, 1)),
Fold(
Function(ReplaceAt(ia, ik, ir[2 +
2 * _n +
1 +
ik]), ia, ik),
Map(Function(0, nz), Range(1, _n, 1)),
Range(1, _n, 1),
),
),
Fold(
Function(Apply(
(fe: integer) => (ReplaceAt(
ReplaceAt(ReplaceAt(ft, 1, ft[1] - 1), 2, ft[2] + 1),
2 +
2 * _n +
1 +
ft[2] + 1,
ft[2 + ft[1]],
) if 0 < ft[1] else ft) if fe == 0 else ReplaceAt(ReplaceAt(ft, 1, ft[1] + 1), 2 +
ft[1] + 1, fe),
it[fj] if it[fj] in Integers else -1,
), ft, fj),
Map(
Function(0, nz),
Range(
1,
2 +
2 *
(2 * _n +
1),
1,
),
),
Range(
1,
2 * _n +
1,
1,
),
),
), Flatten([_x]))valid(_n, _x)
Apply((it: list<any>) => False if Length(it) != 2 * _n + 1 else Apply(
(fz: list<any>) => Length(fz) == 0,
Fold(
Function(Apply((fl: list<any>) => Apply(
(fb: integer) => Filter(Flatten(fl, 1), Function(!(fe in Numbers), fe)) if fb == 0 else [[-1]],
Fold(Function(fa +
Apply(
(fn: list<any>) => ((1 if fn[1] == 0 else (0 if (fn[3] == 0 if fn[3] in Integers else True) else 1) if (fn[2] == 0 if fn[2] in Integers else True) else 1) if fn[1] in Integers else 1) if Length(fn) == 3 else 1,
fl[fi],
), fa, fi), 0, Range(1, Length(fl), 1)),
), fs), fs, fk),
[] if _x in Numbers else [_x],
Range(
1,
_n + 1,
1,
),
),
) if Apply(
(hs: list<integer>) => hs[1] == 0 &&
hs[2] == 0,
Fold(
Function(Apply(
(he: integer) => ht if ht[1] != 0 else ReplaceAt(ht, 1, 1) if ht[2] == 0 else ReplaceAt(ht, 2, ht[2] - 1) if he == 0 else ReplaceAt(ht, 1, 1) if !(he >
ht[2 + ht[2]]) else ReplaceAt(ht, 1, 1) if he > _n else ReplaceAt(ht, 1, 1) if ht[2 +
2 * _n +
1 +
2 +
he] !=
0 else ReplaceAt(ReplaceAt(ReplaceAt(ReplaceAt(ht, 2 +
2 * _n +
1 +
2 +
he, 1), 2 + ht[2], he), 2 +
ht[2] + 1, he), 2, ht[2] + 1),
it[hj] if it[hj] in Integers else -1,
), ht, hj),
Join(
[0, 1],
Map(
Function(0, nz),
Range(1, 2 * _n +
1 +
2 +
_n, 1),
),
),
Range(1, 2 * _n +
1, 1),
),
) else False, Flatten([_x]))Maps
Into and out of IncreasingBinaryTree, called as CombinatorialMap(x, "Name"). Properties are the laws we state and what FindStat records.
To IncreasingBinaryTree
- FromPermutationPermutation → IncreasingBinaryTreeThe increasing binary tree built by minimum-splitting recursion: the position of the smallest value roots the tree, everything before it recurses to the left, everything after it to the right.
Enumeration
Examples
Basic #
About
| Examples | 3 |
|---|