RootedForests

The forests of rooted labeled trees on $\{1, \dots, n\}$, each element a length-$n$ parent array (entry $0$ marks a root). Count $(n+1)^{n-1}$.

✓ checked against that system · ! checked, with disagreements (hover a chip)OEISA000272✓↗

RootedForests(n)the rooted forests on $\{1, \dots, n\}$, as parent arrays

Typed signatures

Type	Package	Applies
(integer<0..>) -> indexed_collection<rooted_forest>	combinatorics	always

Domain: Collections

Definition

Epsil, as the implementation runs it.

count(_n)

1 if _n <= 0 else (_n + 1) ^ (_n - 1)

unrank(_n, _r)

Apply((sq: list<integer>) => Drop(Apply(
                                         (us_init: list<integer>) => Fold(
                                                                           (
                                                                             us: list<integer>,
                                                                             ui,
                                                                           ) => Apply(
                                                                                      (us_next: list<integer>) => us_next,
                                                                                      Apply(
                                                                                             (ul: integer) => Apply((ux: integer) => ReplaceAt(
                                                                                                                                                ReplaceAt(ReplaceAt(us, ul, 0), ux, us[ux] - 1),
                                                                                                                                                _n + 1 +
                                                                                                                                                ul,
                                                                                                                                                0 if ux ==
                                                                                                                                                     _n + 1 else ux,
                                                                                                                                              ), sq[ui]),
                                                                                             Fold(
                                                                                                   Function(u_v if u_f == 0 &&
                                                                                                                   us[u_v] == 1 else u_f, u_f, u_v),
                                                                                                   0,
                                                                                                   Range(1, _n + 1, 1),
                                                                                                 ),
                                                                                           ),
                                                                                    ),
                                                                           us_init,
                                                                           Range(
                                                                                  1,
                                                                                  _n + 1 -
                                                                                  2,
                                                                                  1,
                                                                                ),
                                                                         ),
                                         Join(Map(
                                                   Function(1 + Count(Filter(
                                                                              sq,
                                                                              Function(py == pv, py),
                                                                            )), pv),
                                                   Range(1, _n + 1, 1),
                                                 ), Map(
                                                        Function(0, pz),
                                                        Range(1, _n, 1),
                                                      )),
                                       ), _n + 1), Map(Function((_r - _r % (_n +
                                                                           1) ^
                                                                          (_n +
                                                                           1 - 2 -
                                                                           pj)) / (_n +
                                                                               1) ^
                                                                              (_n +
                                                                               1 -
                                                                               2 -
                                                                               pj) %
                                                               (_n + 1) + 1, pj), Range(
                                                                                 1,
                                                                                 _n + 1 -
                                                                                 2,
                                                                                 1,
                                                                               )))

rank(_n, _x)

Apply((rs_init: list<integer>) => Fold(
                                        (rs: list<integer>, ri) => Apply(
                                                                          (rs_next: list<integer>) => rs_next,
                                                                          Apply(
                                                                                 (rl: integer) => Apply(
                                                                                                         (rn: integer) => ReplaceAt(
                                                                                                                                     ReplaceAt(ReplaceAt(rs, rl, 0), rn, rs[rn] - 1),
                                                                                                                                     _n + 1 +
                                                                                                                                     1,
                                                                                                                                     rs[_n + 1 +
                                                                                                                                        1] *
                                                                                                                                     (_n + 1) +
                                                                                                                                     (rn - 1),
                                                                                                                                   ),
                                                                                                         _n + 1 if _x[rl] == 0 else _x[rl],
                                                                                                       ),
                                                                                 Fold(
                                                                                       Function(r_v if r_f == 0 &&
                                                                                                       rs[r_v] == 1 else r_f, r_f, r_v),
                                                                                       0,
                                                                                       Range(1, _n + 1, 1),
                                                                                     ),
                                                                               ),
                                                                        ),
                                        rs_init,
                                        Range(1, _n + 1 - 2, 1),
                                      ), Join(Map(
                                                  Function(Count(Filter(
                                                                         _x,
                                                                         Function(dy == 0, dy),
                                                                       )) if dv ==
                                                                            _n +
                                                                            1 else 1 +
                                                                                  Count(Filter(_x, Function(dy == dv, dy))), dv),
                                                  Range(1, _n + 1, 1),
                                                ), [0]))[_n + 1 + 1]

valid(_n, _x)

Fold(
      Function(ok_vr && Apply((vp_init: integer) => Fold(
                                                          (vp: integer, vk) => Apply(
                                                                                      (vp_next: integer) => vp_next,
                                                                                      0 if vp == 0 else _x[vp],
                                                                                    ),
                                                          vp_init,
                                                          Range(1, _n, 1),
                                                        ), vr) == 0, ok_vr, vr),
      True,
      Range(1, _n, 1),
    ) if Length(_x) == _n && Fold(Function(
                                           ok_vi && 0 <= _x[vi] && _x[vi] <= _n,
                                           ok_vi,
                                           vi,
                                         ), True, Range(1, _n, 1)) else False

Enumeration

Examples

Basic #

$(3+1)^{2} = 16$

live ↗

In$\mathrm{Count}(\mathrm{RootedForests}(3))$Out$16$

Parent arrays; $0$ marks a root

live ↗

In$\mathrm{Take}(\mathrm{RootedForests}(2), 3)$Out$\bigl\lbrack{\operatorname{RootedForest}}([0, 1]), {\operatorname{RootedForest}}([2, 0]), {\operatorname{RootedForest}}([0, 0])\bigr\rbrack$

About

Examples	2
Crosswalk	OEIS