A358372 -id:A358372 - cp's OEIS frontend

A358506 Matula-Goebel number of the n-th standard ordered rooted tree.

1, 2, 3, 4, 5, 6, 6, 8, 7, 10, 9, 12, 10, 12, 12, 16, 11, 14, 15, 20, 15, 18, 18, 24, 14, 20, 18, 24, 20, 24, 24, 32, 13, 22, 21, 28, 25, 30, 30, 40, 21, 30, 27, 36, 30, 36, 36, 48, 22, 28, 30, 40, 30, 36, 36, 48, 28, 40, 36, 48, 40, 48, 48, 64, 13, 26, 33, 44

Offset: 1

Gus Wiseman, Nov 20 2022

nonn

First differs from A333219 at a(65) = 13, A333219(65) = 17.
The Matula-Goebel number of a rooted tree is the product of primes indexed by the Matula-Goebel numbers of the branches of its root, which gives a bijective correspondence between positive integers and unlabeled rooted trees.
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.

			The first eight standard ordered trees are: o, (o), ((o)), (oo), (((o))), ((o)o), (o(o)), (ooo), with Matula-Goebel numbers: 1, 2, 3, 4, 5, 6, 6, 8.

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

For binary instead of standard encoding we have A127301.
There are exactly A206487(n) appearances of n.
For binary instead of Matula-Goebel encoding we have A358505.
Positions of first appearances are A358522, sorted A358521.
A000108 counts ordered rooted trees, unordered A000081.
A214577 and A358377 rank trees with no permutations.
Cf. A001263, A014486, A061775, A196050, A358371, A358372, A358378, A358379, A358507, A358508.

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
srt[n_]:=If[n==1,{},srt/@stc[n-1]];
mgnum[t_]:=If[t=={},1,Times@@Prime/@mgnum/@t];
Table[mgnum[srt[n]],{n,100}]

A358523 Standard ordered tree numbers of ordered trees in order of their binary encodings (A014486).

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Nov 21 2022

nonn

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.

The binary encoding of an ordered tree (A014486) is obtained by replacing the internal left and right brackets with 0's and 1's, thus forming a binary number.

			The first six binary encodings are: 0, 2, 10, 12, 42, 44, and the corresponding trees have standard ranks: 1, 2, 4, 3, 8, 7.

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

A dual sequence is A358505.
A000108 counts ordered rooted trees, unordered A000081.
A014486 lists all binary encodings.
Cf. A001263, A014221, A057122, A358371, A358372, A358373, A358379.

stcinv[q_]:=Total[2^Accumulate[Reverse[q]]]/2;
srtinv[t_]:=If[t=={},1,stcinv[srtinv/@t]+1];
binbalQ[n_]:=n==0||Count[IntegerDigits[n,2],0]==Count[IntegerDigits[n,2],1]&&And@@Table[Count[Take[IntegerDigits[n,2],k],0]<=Count[Take[IntegerDigits[n,2],k],1],{k,IntegerLength[n,2]}];
bint[n_]:=If[n==0,{},ToExpression[StringReplace[StringReplace[ToString[IntegerDigits[n,2]/.{1->"{",0->"}"}],","->""],"} {"->"},{"]]]
Table[srtinv[bint[n]],{n,Select[Range[0,100],binbalQ]}]

A358521 Sorted list of positions of first appearances in the sequence of Matula-Goebel numbers of standard ordered trees (A358506).

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 16, 17, 18, 19, 20, 22, 24, 32, 33, 34, 35, 36, 37, 38, 40, 43, 44, 48, 64, 66, 67, 68, 69, 70, 72, 74, 75, 76, 80, 86, 88, 96, 128, 129, 131, 132, 133, 134, 136, 137, 138, 139, 140, 144, 147, 148, 150, 152, 160, 171, 172

Offset: 1

Gus Wiseman, Nov 20 2022

nonn

The Matula-Goebel number of a rooted tree is the product of primes indexed by the Matula-Goebel numbers of the branches of its root, which gives a bijective correspondence between positive integers and unlabeled rooted trees.

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.

			The terms together with their standard ordered trees begin:
   1: o
   2: (o)
   3: ((o))
   4: (oo)
   5: (((o)))
   6: ((o)o)
   8: (ooo)
   9: ((oo))
  10: (((o))o)
  11: ((o)(o))
  12: ((o)oo)
  16: (oooo)
  17: ((((o))))
  18: ((oo)o)
  19: (((o))(o))
  20: (((o))oo)

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

Positions of first appearances in A358506.
The unsorted version is A358522.
A000108 counts ordered rooted trees, unordered A000081.
A214577 and A358377 rank trees with no permutations.
Cf. A001263, A014486, A061775, A127301, A196050, A206487, A358371, A358372, A358378, A358379, A358505.

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
srt[n_]:=If[n==1,{},srt/@stc[n-1]];
mgnum[t_]:=If[t=={},1,Times@@Prime/@mgnum/@t];
fir[q_]:=Select[Range[Length[q]],!MemberQ[Take[q,#-1],q[[#]]]&];
fir[Table[mgnum[srt[n]],{n,100}]]

A358522 Least number k such that the k-th standard ordered tree has Matula-Goebel number n, i.e., A358506(k) = n.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 9, 8, 11, 10, 17, 12, 33, 18, 19, 16, 257, 22, 129, 20, 35, 34, 1025, 24, 37, 66, 43, 36, 513, 38, 65537, 32, 67, 514, 69, 44, 2049, 258, 131, 40

Offset: 1

Gus Wiseman, Nov 20 2022

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.

The Matula-Goebel number of a rooted tree is the product of primes indexed by the Matula-Goebel numbers of the branches of its root, which gives a bijective correspondence between positive integers and unlabeled rooted trees.

			The terms together with their standard ordered trees begin:
    1: o
    2: (o)
    3: ((o))
    4: (oo)
    5: (((o)))
    6: ((o)o)
    9: ((oo))
    8: (ooo)
   11: ((o)(o))
   10: (((o))o)
   17: ((((o))))
   12: ((o)oo)
   33: (((o)o))
   18: ((oo)o)
   19: (((o))(o))
   16: (oooo)
  257: (((oo)))
   22: ((o)(o)o)
  129: ((ooo))
   20: (((o))oo)
   35: ((oo)(o))
   34: ((((o)))o)

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

Position of first appearance of n in A358506.
The sorted version is A358521.
A000108 counts ordered rooted trees, unordered A000081.
A214577 and A358377 rank trees with no permutations.
Cf. A001263, A014486, A061775, A127301, A196050, A206487, A358371, A358372, A358378, A358379, A358505.

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
srt[n_]:=If[n==1,{},srt/@stc[n-1]];
mgnum[t_]:=If[t=={},1,Times@@Prime/@mgnum/@t];
uv=Table[mgnum[srt[n]],{n,10000}];
Table[Position[uv,k][[1,1]],{k,Min@@Complement[Range[Max@@uv],uv]-1}]

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

Original entry on oeis.org

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

Gus Wiseman, Nov 26 2022

nonn

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.

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

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.

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}]

A358550 Depth of the ordered rooted tree with binary encoding A014486(n).

Original entry on oeis.org

1, 2, 2, 3, 2, 3, 3, 3, 4, 2, 3, 3, 3, 4, 3, 3, 3, 3, 4, 4, 4, 4, 5, 2, 3, 3, 3, 4, 3, 3, 3, 3, 4, 4, 4, 4, 5, 3, 3, 3, 3, 4, 3, 3, 3, 3, 4, 4, 4, 4, 5, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 2, 3, 3, 3, 4, 3, 3, 3, 3, 4, 4, 4, 4, 5, 3, 3, 3, 3, 4, 3, 3, 3

Offset: 1

Gus Wiseman, Nov 22 2022

nonn

The binary encoding of an ordered tree (A014486) is obtained by replacing the internal left and right brackets with 0's and 1's, thus forming a binary number.

			The first few rooted trees in binary encoding are:
    0: o
    2: (o)
   10: (oo)
   12: ((o))
   42: (ooo)
   44: (o(o))
   50: ((o)o)
   52: ((oo))
   56: (((o)))
  170: (oooo)
  172: (oo(o))
  178: (o(o)o)
  180: (o(oo))
  184: (o((o)))

Positions of first appearances are A014137.
Leaves of the ordered tree are counted by A057514, standard A358371.
Branches of the ordered tree are counted by A057515.
Edges of the ordered tree are counted by A072643.
The Matula-Goebel number of the ordered tree is A127301.
Positions of 2's are A155587, indices of A020988.
The standard ranking of the ordered tree is A358523.
Nodes of the ordered tree are counted by A358551, standard A358372.
For standard instead of binary encoding we have A358379.
A000108 counts ordered rooted trees, unordered A000081.
A014486 lists all binary encodings.
Cf. A001263, A057122, A358373, A358505, A358524.

binbalQ[n_]:=n==0||Count[IntegerDigits[n,2],0]==Count[IntegerDigits[n,2],1]&&And@@Table[Count[Take[IntegerDigits[n,2],k],0]<=Count[Take[IntegerDigits[n,2],k],1],{k,IntegerLength[n,2]}];
bint[n_]:=If[n==0,{},ToExpression[StringReplace[StringReplace[ToString[IntegerDigits[n,2]/.{1->"{",0->"}"}],","->""],"} {"->"},{"]]];
Table[Depth[bint[k]]-1,{k,Select[Range[0,1000],binbalQ]}]

A358551 Number of nodes in the ordered rooted tree with binary encoding A014486(n).

Original entry on oeis.org

1, 2, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7

Offset: 1

Gus Wiseman, Nov 22 2022

nonn

The binary encoding of an ordered tree (A014486) is obtained by replacing the internal left and right brackets with 0's and 1's, thus forming a binary number.

			The first few rooted trees in binary encoding are:
    0: o
    2: (o)
   10: (oo)
   12: ((o))
   42: (ooo)
   44: (o(o))
   50: ((o)o)
   52: ((oo))
   56: (((o)))
  170: (oooo)
  172: (oo(o))
  178: (o(o)o)
  180: (o(oo))
  184: (o((o)))

Run-lengths are A000108.
Binary encodings are listed by A014486.
Leaves of the ordered tree are counted by A057514, standard A358371.
Branches of the ordered tree are counted by A057515.
Edges of the ordered tree are counted by A072643.
The Matula-Goebel number of the ordered tree is A127301.
For standard instead of binary encoding we have A358372.
The standard ranking of the ordered tree is A358523.
Depth of the ordered tree is A358550, standard A358379.
Cf. A000081, A001263, A057122, A358373, A358505, A358524.

binbalQ[n_]:=n==0||Count[IntegerDigits[n,2],0]==Count[IntegerDigits[n,2],1]&&And@@Table[Count[Take[IntegerDigits[n,2],k],0]<=Count[Take[IntegerDigits[n,2],k],1],{k,IntegerLength[n,2]}];
bint[n_]:=If[n==0,{},ToExpression[StringReplace[StringReplace[ToString[IntegerDigits[n,2]/.{1->"{",0->"}"}],","->""],"} {"->"},{"]]];
Table[Count[bint[k],_,{0,Infinity}],{k,Select[Range[0,10000],binbalQ]}]

a(n) = A072643(n) + 1.

A358525 Number of distinct permutations of the n-th composition in standard order.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 1, 3, 2, 3, 3, 1, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 1, 1, 2, 2, 3, 1, 6, 6, 4, 2, 6, 1, 6, 6, 6, 6, 5, 2, 3, 6, 4, 6, 6, 6, 5, 3, 4, 6, 5, 4, 5, 5, 1, 1, 2, 2, 3, 2, 6, 6, 4, 2, 3, 3, 12, 3, 12, 12, 5, 2, 6, 3, 12, 3, 4

Offset: 0

Gus Wiseman, Nov 21 2022

nonn

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The a(45) = 6 permutations are: (2121), (2112), (2211), (1221), (1212), (1122).

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

See link for sequences related to standard compositions.
Positions of 1's are A272919.
Cf. A000120, A048896, A070939, A329395, A333766, A358371, A358372, A358379, A358505, A358507, A358508.

stc[n_]:=Reverse[Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]];
Table[Length[Permutations[stc[n]]],{n,0,100}]

cp's OEIS Frontend

A358506 Matula-Goebel number of the n-th standard ordered rooted tree.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A358523 Standard ordered tree numbers of ordered trees in order of their binary encodings (A014486).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A358521 Sorted list of positions of first appearances in the sequence of Matula-Goebel numbers of standard ordered trees (A358506).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A358522 Least number k such that the k-th standard ordered tree has Matula-Goebel number n, i.e., A358506(k) = n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A358550 Depth of the ordered rooted tree with binary encoding A014486(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A358551 Number of nodes in the ordered rooted tree with binary encoding A014486(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A358525 Number of distinct permutations of the n-th composition in standard order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica