A358553 Number of internal (non-leaf) nodes in the n-th standard ordered rooted tree.

0, 1, 2, 1, 3, 2, 2, 1, 2, 3, 3, 2, 3, 2, 2, 1, 4, 2, 4, 3, 4, 3, 3, 2, 2, 3, 3, 2, 3, 2, 2, 1, 3, 4, 3, 2, 5, 4, 4, 3, 3, 4, 4, 3, 4, 3, 3, 2, 4, 2, 4, 3, 4, 3, 3, 2, 2, 3, 3, 2, 3, 2, 2, 1, 3, 3, 5, 4, 4, 3, 3, 2, 4, 5, 5, 4, 5, 4, 4, 3, 5, 3, 5, 4, 5, 4, 4

Offset

1,3

Comments

We define the n-th standard ordered rooted tree to be obtained by taking the (n-1)-th composition in standard order (graded reverse-lexicographic, A066099) as root and replacing each part with its own standard ordered rooted tree. This ranking is an ordered variation of Matula-Goebel numbers, giving a bijective correspondence between positive integers and unlabeled ordered rooted trees.

Links

Table of n, a(n) for n=1..87.

Example

The 89-th standard rooted tree is ((o)o(oo)), and it has 3 internal nodes, so a(89) = 3.

Mathematica

stc[n_]:=Reverse[Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n, 2]], 1], 0]]];
srt[n_]:=If[n==1, {}, srt/@stc[n-1]];
Table[Count[srt[n], _[__], {0, Infinity}], {n, 100}]

Crossrefs

This statistic is counted by A001263, unordered A358575 (reverse A055277).

The unordered version is A342507, firsts A358554.

Other statistics: A358371 (leaves), A358372 (nodes), A358379 (edge-height).

A000081 counts rooted trees, ordered A000108.

Cf. A000891, A014221, A358373, A358585, A358586, A358588.

Sequence in context: A096852 A096857 A358379 * A303639 A090000 A109082

Adjacent sequences: A358550 A358551 A358552 * A358554 A358555 A358556

Keyword

nonn

Author

Gus Wiseman, Nov 26 2022

Status

approved