PruningNumber

The number of prunings, each deleting every maximal hanging branch (a path of single-child vertices to a leaf), that reduce the tree to a single vertex.

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

PruningNumber(tree)The number of prunings, each deleting every maximal hanging branch (a path of single-child vertices to a leaf), that reduce the tree to a single vertex.

Typed signatures

Type	Package	Applies
(ordered_tree) -> number	combinatorics	always

Domain: Tree statistics

Details

• Defined over OrderedTree as an expression in _x, evaluated by compute-engine — the definition IS the implementation.
• Takes a OrderedTree and nothing else — it reads values against their positions, or walks the orbits, so it needs the bijection. Applying it to a bare list is a type error, not a wrong answer.

Definition

Epsil, as the implementation runs it.

on OrderedTree, over _x

Apply(
       (p: collection) => 0 if Length(_x) == 0 else 1 + p[3],
       Apply(
              Function([1, 0, 0] if Length(t) == 0 else Apply(
                                                               (r: collection) => [
                                                                                    1 if r[3] == 1 &&
                                                                                         r[4] == 1 else 0,
                                                                                    0 if r[3] == 1 &&
                                                                                         r[4] == 1 else Max(1, r[1], r[2] + 1),
                                                                                    r[1],
                                                                                  ],
                                                               Fold(
                                                                     Function([
                                                                                Max(a[1], b[2]) if b[1] == 0 else a[1],
                                                                                Max(a[2], Min(a[1], b[2])) if b[1] == 0 else a[2],
                                                                                a[3] + 1,
                                                                                b[1],
                                                                              ], a, b),
                                                                     [
                                                                       0,
                                                                       0,
                                                                       0,
                                                                       1,
                                                                     ],
                                                                     Map(Function(
                                                                                   self(self, c),
                                                                                   c,
                                                                                 ), t),
                                                                   ),
                                                             ), self, t),
              Function([1, 0, 0] if Length(t) == 0 else Apply(
                                                               (r: collection) => [
                                                                                    1 if r[3] == 1 &&
                                                                                         r[4] == 1 else 0,
                                                                                    0 if r[3] == 1 &&
                                                                                         r[4] == 1 else Max(1, r[1], r[2] + 1),
                                                                                    r[1],
                                                                                  ],
                                                               Fold(
                                                                     Function([
                                                                                Max(a[1], b[2]) if b[1] == 0 else a[1],
                                                                                Max(a[2], Min(a[1], b[2])) if b[1] == 0 else a[2],
                                                                                a[3] + 1,
                                                                                b[1],
                                                                              ], a, b),
                                                                     [
                                                                       0,
                                                                       0,
                                                                       0,
                                                                       1,
                                                                     ],
                                                                     Map(Function(
                                                                                   self(self, c),
                                                                                   c,
                                                                                 ), t),
                                                                   ),
                                                             ), self, t),
              _x,
            ),
     )

Examples

Basic #

the ordered tree $[[],[[]],[]]$

live ↗

In$\mathrm{PruningNumber}({\operatorname{OrderedTree}}(\bigl\lbrack\bigl\lbrack\bigr\rbrack, \bigl\lbrack\bigl\lbrack\bigr\rbrack\bigr\rbrack, \bigl\lbrack\bigr\rbrack\bigr\rbrack))$Out$1$

Properties #

FindStat's value for [[]]

live ↗

In$\mathrm{CombinatorialStat}({\operatorname{OrderedTree}}(\bigl\lbrack\bigl\lbrack\bigr\rbrack\bigr\rbrack), \text{PruningNumber})$Out$1$

Known value · FindStat St000679

FindStat's value for [[[]]]

live ↗

In$\mathrm{CombinatorialStat}({\operatorname{OrderedTree}}(\bigl\lbrack\bigl\lbrack\bigl\lbrack\bigr\rbrack\bigr\rbrack\bigr\rbrack), \text{PruningNumber})$Out$1$

Known value · FindStat St000679

FindStat's value for [[],[]]

live ↗

In$\mathrm{CombinatorialStat}({\operatorname{OrderedTree}}(\bigl\lbrack\bigl\lbrack\bigr\rbrack, \bigl\lbrack\bigr\rbrack\bigr\rbrack), \text{PruningNumber})$Out$1$

Known value · FindStat St000679

About

Examples	4
Crosswalk	FindStat