NonCrossingTrees
The spanning trees on circle-labeled points whose edges, drawn as chords, never cross.
NonCrossingTrees(n)every spanning tree on points around a circle with no two edges crossing.Typed signatures
| Type | Package | Applies |
|---|---|---|
(integer<0..>) -> indexed_collection<non_crossing_tree> | combinatorics | always |
Details
- A lazy indexed collection; the count is the Fuss–Catalan number — has elements. See Binomial.
- In bijection (Flajolet & Noy 1999) with the ternary trees on internal nodes; each element reuses that encoding as its flat preorder arity word — entries, each (leaf) or (internal node, followed in preorder by its three children).
- The glyph draws an element directly from this word, since it is already a preorder child-count sequence.
Definition
Epsil, as the implementation runs it.
count(_n)
0 if _n < 0 else 0 if _n < 0 else _tables[1 * (Max(_n, 0) + 1) + _n + 1]unrank(_n, _r)
Apply(
(ufinal: list<integer>) => Map(
Function(ufinal[uv + 1], uv),
Range(1, 3 * _n + 1, 1),
),
Fold(
Function(Apply((ut: integer) => Apply((um: integer) => Apply(
(uk: integer) => Apply(
(ufound: list<integer>) => Apply((usz: integer) => Apply(
(urest: integer) => ReplaceAt(ReplaceAt(
ReplaceAt(ReplaceAt(
ReplaceAt(ReplaceAt(
ReplaceAt(ReplaceAt(us, 1, ut - 1 +
(1 if 1 < uk else 0) +
(1 if 0 < usz else 0)), ustep + 2, 3 if 0 < usz else 0),
3 * _n +
1 +
1 +
3 *
(ut - 1) +
1,
um - usz,
), 3 * _n +
1 +
1 +
3 *
(ut - 1) +
2, uk - 1),
3 * _n +
1 +
1 +
3 *
(ut - 1) +
3,
ufound[1] % urest,
), 3 * _n +
1 +
1 +
3 *
(ut +
(1 if 1 < uk else 0) -
1) +
1, usz - 1),
3 * _n +
1 +
1 +
3 *
(ut +
(1 if 1 < uk else 0) -
1) +
2,
3,
), 3 * _n +
1 +
1 +
3 *
(ut +
(1 if 1 < uk else 0) -
1) +
3, (ufound[1] -
ufound[1] % urest) /
urest),
0 if um - ufound[2] <
0 else _tables[(uk - 1) *
(Max(_n, 0) +
1) +
(um - ufound[2]) +
1],
), ufound[2]),
Fold(
Function(ua if ua[3] == 1 else [ua[1], ush, 1] if ua[1] <
(0 if ush < 0 else _tables[1 *
(Max(_n, 0) +
1) + ush + 1]) *
(0 if um - ush <
0 else _tables[(uk - 1) *
(Max(_n, 0) +
1) +
(um - ush) +
1]) else [ua[1] -
(0 if ush < 0 else _tables[1 *
(Max(_n, 0) +
1) + ush + 1]) *
(0 if um - ush <
0 else _tables[(uk - 1) *
(Max(_n, 0) +
1) +
(um - ush) +
1]), ush, 0], ua, ush),
[us[3 * _n +
1 +
1 +
3 *
(ut - 1) +
3], 0, 0],
Range(0, um, 1),
),
),
us[3 *
_n +
1 +
1 +
3 *
(ut -
1) +
2],
), us[3 *
_n +
1 +
1 +
3 *
(ut -
1) +
1]), us[1]), us, ustep),
Join(
[1, 3 if 0 < _n else 0],
Map(Function(0, pz), Range(1, 3 * _n, 1)),
[_n - 1, 3, _r],
Map(Function(0, pz), Range(1, 3 * (2 * _n + 4), 1)),
),
Range(1, 3 * _n, 1),
),
)rank(_n, _x)
Fold(
Function(Apply((rt: integer) => Apply((rm: integer) => Apply(
(rk: integer) => Apply((rmult: integer) => Apply(
(rsub: list<integer>) => Apply((rsz: integer) => Apply(
(rfit: integer) => Apply(
(rbefore: integer) => ReplaceAt(
ReplaceAt(ReplaceAt(
ReplaceAt(ReplaceAt(
ReplaceAt(ReplaceAt(ReplaceAt(rs, 1, rt - 1 +
(1 if 1 < rk else 0) +
(1 if 0 < rsz else 0)), 2, rs[2] +
rmult * rbefore), 2 +
3 *
(rt - 1) +
1, rm - rsz),
2 +
3 *
(rt - 1) +
2,
rk - 1,
), 2 +
3 *
(rt - 1) +
3, rmult),
2 +
3 *
(rt +
(1 if 1 < rk else 0) -
1) +
1,
rsz - 1,
), 2 +
3 *
(rt +
(1 if 1 < rk else 0) -
1) +
2, 3),
2 +
3 *
(rt +
(1 if 1 < rk else 0) -
1) +
3,
rmult * rfit,
),
Fold(Function(rc +
(0 if rq < 0 else _tables[1 *
(Max(_n, 0) +
1) + rq + 1]) *
(0 if rm - rq <
0 else _tables[(rk - 1) *
(Max(_n, 0) +
1) +
(rm - rq) +
1]), rc, rq), 0, Range(0, rsz - 1, 1)),
),
0 if rm - rsz <
0 else _tables[(rk - 1) *
(Max(_n, 0) +
1) +
(rm - rsz) +
1],
), rsub[2]),
Fold(
Function(rb if rb[1] == 0 else [rb[1] + _x[rj] -
1, rb[2] +
(1 if _x[rj] == 3 else 0)], rb, rj),
[1, 0],
Range(rstep + 1, Length(_x), 1),
),
), rs[2 +
3 *
(rt - 1) +
3]),
rs[2 + 3 *
(rt -
1) + 2],
), rs[2 + 3 *
(rt -
1) + 1]), rs[1]), rs, rstep),
Join(
[1, 0, _n - 1, 3, 1],
Map(Function(0, pz), Range(1, 3 * (2 * _n + 4), 1)),
),
Range(1, 3 * _n, 1),
)[2]valid(_n, _x)
Apply(
(wend: list<integer>) => wend[1] == 0 && wend[3] == 0 && wend[2] == _n,
Fold(Function([
wa[1] + _x[wj] - 1,
wa[2] + (1 if _x[wj] == 3 else 0),
0 if wa[3] == 0 && 0 < wa[1] && (_x[wj] == 0 || _x[wj] ==
3) else 1,
], wa, wj), [1, 0, 0], Range(1, Length(_x), 1)),
)tables(_n)
Fold(Function(Apply(
(fa: list<integer>) => Fold(
Function(Apply((fc: list<integer>) => ReplaceAt(
fb,
fj *
(Max(_n, 0) +
1) + fm + 1,
Fold(Function(fs +
fc[1 *
(Max(_n, 0) +
1) + fi + 1] *
fc[(fj - 1) *
(Max(_n, 0) +
1) +
(fm - fi) +
1], fs, fi), 0, Range(0, fm, 1)),
), fb), fb, fj),
fa,
Range(2, 3, 1),
),
ReplaceAt(
ft,
1 * (Max(_n, 0) + 1) + fm + 1,
1 if fm == 0 else ft[3 * (Max(_n, 0) + 1) +
(fm - 1) + 1],
),
), ft, fm), ReplaceAt(Map(
Function(0, pz),
Range(
1,
(Max(3, 1) + 1) * (Max(
_n,
0,
) + 1),
1,
),
), 1, 1), Range(0, Max(_n, 0), 1))Enumeration
Examples
1 more kept as data, checked against the oraclesAbout
| Examples | 2 |
|---|
See also: Binomial, CatalanNumber, Count, At