FullKAryTrees
A name from the enumeratio catalogue with no kernel of its own yet; this page carries its crosswalk only.
Trees where every internal node has exactly k children — the Fuss-Catalan count.
FullKAryTrees(...)Trees where every internal node has exactly k children — the Fuss-Catalan count.Typed signatures
| Type | Package | Applies |
|---|---|---|
(integer<0..>, integer<0..>) -> indexed_collection<full_k_ary_tree> | combinatorics | always |
Definition
Epsil, as the implementation runs it.
count(_n, _k)
0 if _k < 1 else 0 if _n < 0 else 0 if _n < 0 else _tables[1 * (Max(_n, 0) + 1) +
_n + 1]unrank(_n, _k, _r)
Apply(
(kw: list<integer>) => Fold(
Function(Apply((bt: list<any>) => Apply((ba: integer) => ReplaceAt(
ReplaceAt(bs, 1, bt[1] - ba +
1),
bt[1] - ba +
2,
0 if ba == 0 else Fold(
Function(Apply((bc: list<any>) => Join(bc, [bt[bt[1] + 2 -
bi]]), bl), bl, bi),
[],
Range(1, ba, 1),
),
), kw[bj]), bs), bs, bj),
Join([0], Map(
Function(0, nz),
Range(1, _k * _n + 1, 1),
)),
Range(_k * _n + 1, 1, -1),
)[2],
Apply(
(ufinal: list<integer>) => Map(
Function(ufinal[uv + 1], uv),
Range(1, _k * _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, _k if 0 < usz else 0),
_k * _n +
1 +
1 +
3 *
(ut - 1) +
1,
um - usz,
), _k * _n +
1 +
1 +
3 *
(ut - 1) +
2, uk - 1),
_k * _n +
1 +
1 +
3 *
(ut - 1) +
3,
ufound[1] % urest,
), _k * _n +
1 +
1 +
3 *
(ut +
(1 if 1 < uk else 0) -
1) +
1, usz - 1),
_k * _n +
1 +
1 +
3 *
(ut +
(1 if 1 < uk else 0) -
1) +
2,
_k,
), _k * _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[_k * _n +
1 +
1 +
3 *
(ut - 1) +
3], 0, 0],
Range(0, um, 1),
),
),
us[_k * _n +
1 +
1 +
3 *
(ut - 1) +
2],
), us[_k * _n +
1 +
1 +
3 *
(ut - 1) +
1]), us[1]), us, ustep),
Join(
[1, _k if 0 < _n else 0],
Map(Function(0, pz), Range(1, _k * _n, 1)),
[_n - 1, _k, _r],
Map(Function(0, pz), Range(1, 3 * (2 * _n + 4), 1)),
),
Range(1, _k * _n, 1),
),
),
)rank(_n, _k, _x)
Apply(
(kr: list<any>) => Apply((kw: list<integer>) => 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,
_k,
), 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] + kw[rj] -
1, rb[2] +
(1 if kw[rj] == _k else 0)], rb, rj),
[1, 0],
Range(rstep + 1, Length(kw), 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,
_k,
1,
],
Map(
Function(0, pz),
Range(
1,
3 *
(2 * _n +
4),
1,
),
),
),
Range(
1,
_k * _n,
1,
),
)[2], Take(
Drop(
kr,
3,
),
_k * _n +
1,
)),
Fold(
Function(Apply((ft: list<any>) => ft if ft[1] == 0 else ReplaceAt(
ReplaceAt(
ReplaceAt(
ReplaceAt(ft, 1, ft[1] - 1),
2,
ft[2] + 1,
),
3,
ft[3] if ft[_k * _n +
1 + 3 + ft[1]] ==
0 else 1,
),
ft[2] + 4,
0,
) if ft[_k * _n +
1 + 3 + ft[1]] in
Integers else Fold(
Function(ReplaceAt(
fa,
_k * _n +
1 +
3 +
(ft[1] + fi -
1),
ft[_k * _n +
1 + 3 + ft[1]][_k + 1 -
fi],
), fa, fi),
ReplaceAt(
ReplaceAt(ReplaceAt(ReplaceAt(ft, 1, ft[1] + _k -
1), 2, ft[2] + 1), 3, ft[3]),
ft[2] + 4,
_k,
),
Range(1, _k, 1),
) if Length(ft[_k * _n +
1 + 3 + ft[1]]) ==
_k else ReplaceAt(
ReplaceAt(ReplaceAt(ReplaceAt(ft, 1, ft[1] - 1), 2, ft[2] + 1), 3, 1),
ft[2] + 4,
_k,
), fs), fs, fj),
Join(
[1, 0, 0],
Map(Function(0, nz), Range(1, _k * _n + 1, 1)),
[_x],
Map(Function(0, nz), Range(1, _k * (_k * _n + 1), 1)),
),
Range(1, _k * _n + 1, 1),
),
)valid(_n, _k, _x)
False if _k < 1 else Apply(
(kr: list<any>) => kr[1] == 0 && kr[2] == _k * _n +
1 && kr[3] ==
0,
Fold(
Function(Apply((ft: list<any>) => ft if ft[1] ==
0 else ReplaceAt(ReplaceAt(
ReplaceAt(
ReplaceAt(ft, 1, ft[1] - 1),
2,
ft[2] + 1,
),
3,
ft[3] if ft[_k * _n +
1 + 3 + ft[1]] ==
0 else 1,
), ft[2] + 4, 0) if ft[_k * _n +
1 + 3 + ft[1]] in
Integers else Fold(
Function(ReplaceAt(fa, _k * _n +
1 +
3 +
(ft[1] + fi -
1), ft[_k * _n +
1 + 3 + ft[1]][_k + 1 -
fi]), fa, fi),
ReplaceAt(
ReplaceAt(ReplaceAt(ReplaceAt(ft, 1, ft[1] + _k -
1), 2, ft[2] + 1), 3, ft[3]),
ft[2] + 4,
_k,
),
Range(1, _k, 1),
) if Length(ft[_k * _n +
1 + 3 + ft[1]]) ==
_k else ReplaceAt(
ReplaceAt(ReplaceAt(ReplaceAt(ft, 1, ft[1] - 1), 2, ft[2] + 1), 3, 1),
ft[2] + 4,
_k,
), fs), fs, fj),
Join(
[1, 0, 0],
Map(Function(0, nz), Range(1, _k * _n +
1, 1)),
[_x],
Map(
Function(0, nz),
Range(1, _k * (_k * _n + 1), 1),
),
),
Range(1, _k * _n + 1, 1),
),
)tables(_n, _k)
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, _k, 1),
),
ReplaceAt(
ft,
1 * (Max(_n, 0) + 1) + fm + 1,
1 if fm == 0 else ft[_k * (Max(_n, 0) + 1) +
(fm - 1) + 1],
),
), ft, fm),
ReplaceAt(Map(Function(0, pz), Range(1, (Max(_k, 1) + 1) *
(Max(_n, 0) + 1), 1)), 1, 1),
Range(0, Max(_n, 0), 1),
)