A358373 Triangle read by rows where row n lists the sorted standard ordered rooted tree-numbers of all unlabeled ordered rooted trees with n vertices.

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 25, 33, 65, 129, 257, 19, 20, 21, 22, 23, 24, 26, 27, 28, 29, 30, 31, 32, 34, 35, 36, 41, 49, 50, 57, 66, 97, 130, 193, 258, 385, 513, 514, 769, 1025, 2049, 4097, 8193, 16385, 32769, 65537, 131073

Offset: 1

Author

Gus Wiseman, Nov 14 2022

Keywords

• nonn
• tabf

Comments

We define the standard ordered rooted tree (SORT)-number of an unlabeled ordered rooted tree to be one plus the standard composition number (A066099) of the SORT-numbers of the branches, or 1 if there are no branches. This ranking is an ordered variation of Matula-Goebel numbers, giving a bijective correspondence between positive integers and unlabeled ordered rooted trees.

Examples

			Triangle begins:
   1
   2
   3   4
   5   6   7   8   9
  10  11  12  13  14  15  16  17  18  25  33  65 129 257
For example, the tree t = ((o,o),o) has branches (o,o) and o with SORT-numbers 4 and 1, and the standard composition number of (4,1) is 17, so t has SORT-number 18 and is found in row 5.
		

Links

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

Crossrefs

The version for compositions is A000027.

Row-lengths are A000108.

The unordered version (using Matula-Goebel numbers) is A061773.

The version for Heinz numbers of partitions is A215366.

The row containing n is A358372(n).

A000081 counts unlabeled rooted trees, ranked by A358378.

A001263 counts unlabeled ordered rooted trees by nodes and leaves.

A358371 counts leaves in standard ordered rooted trees.

Cf. A004249, A005043, A061775, A109129, A284778, A358376, A358377.

Programs

Mathematica

stcinv[q_]:=Total[2^(Accumulate[Reverse[q]])]/2;
aotrank[t_]:=If[t=={},1,1+stcinv[aotrank/@t]];
aot[n_]:=If[n==1,{{}},Join@@Table[Tuples[aot/@c],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];
Table[Sort[aotrank/@aot[n]],{n,6}]