RecursiveTrees

A name from the enumeratio catalogue with no kernel of its own yet; this page carries its crosswalk only.

Increasing trees on n labeled vertices — (n−1)! of them.

RecursiveTrees(...)Increasing trees on n labeled vertices — (n−1)! of them.

Typed signatures

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

Domain: Combinatorics

Definition

Epsil, as the implementation runs it.

count(_n)

Fold(Function(cp * cj, cp, cj), 1, Range(1, _n - 1, 1))

unrank(_n, _r)

Map(
     Function(0 if i == 1 else (_r - _r % Fold(
                                                Function(rw * (rj - 1), rw, rj),
                                                1,
                                                Range(i + 1, _n, 1),
                                              )) / Fold(
                                                        Function(
                                                                  rw * (rj - 1),
                                                                  rw,
                                                                  rj,
                                                                ),
                                                        1,
                                                        Range(i + 1, _n, 1),
                                                      ) % (i - 1) + 1, i),
     Range(1, _n, 1),
   )

rank(_n, _x)

Fold(Function(acc * (i - 1) + (_x[i] - 1), acc, i), 0, Range(2, _n, 1))

valid(_n, _x)

Length(_x) == _n && (True if _n == 0 else _x[1] == 0 && Fold(
                                                              Function(ok_i && 1 <=
                                                                               _x[i] &&
                                                                               _x[i] <=
                                                                               i -
                                                                               1, ok_i, i),
                                                              True,
                                                              Range(2, _n, 1),
                                                            ))

Enumeration

Examples

Basic #

$(n-1)!$ recursive trees on $n$ vertices

live ↗

In$\mathrm{Count}(\mathrm{RecursiveTrees}(5))$Out$24$

The recursive trees on $3$ vertices, as parent lists

live ↗

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

About

Examples	2