A358375 Numbers k such that the k-th standard ordered rooted tree is binary.

1, 4, 18, 25, 137, 262146, 393217, 2097161, 2228225

Offset

1,2

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..9.

Gus Wiseman, Statistics, classes, and transformations of standard compositions

Example

The initial terms and their corresponding trees:
       1: o
       4: (oo)
      18: ((oo)o)
      25: (o(oo))
     137: ((oo)(oo))
  262146: (((oo)o)o)
  393217: (o((oo)o))

Mathematica

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n, 2]], 1], 0]]//Reverse;
srt[n_]:=If[n==1, {}, srt/@stc[n-1]];
Select[Range[1000], FreeQ[srt[#], _[__]?(Length[#]!=2&)]&]

Crossrefs

The unordered version is A111299, counted by A001190

These trees are counted by A126120.

A000081 counts unlabeled rooted trees, ranked by A358378.

A358371 and A358372 count leaves and nodes in standard ordered rooted trees.

Cf. A001263, A004249, A005043, A063895, A245824, A284778, A358373, A358374, A358376, A358377.

Sequence in context: A099565 A063563 A323848 * A166749 A370406 A378667

Adjacent sequences: A358372 A358373 A358374 * A358376 A358377 A358378

Keyword

nonn,more

Author

Gus Wiseman, Nov 14 2022

Status

approved