A127301 Matula-Goebel signatures for plane general trees encoded by A014486.

1, 2, 4, 3, 8, 6, 6, 7, 5, 16, 12, 12, 14, 10, 12, 9, 14, 19, 13, 10, 13, 17, 11, 32, 24, 24, 28, 20, 24, 18, 28, 38, 26, 20, 26, 34, 22, 24, 18, 18, 21, 15, 28, 21, 38, 53, 37, 26, 37, 43, 29, 20, 15, 26, 37, 23, 34, 43, 67, 41, 22, 29, 41, 59, 31, 64, 48, 48, 56, 40, 48, 36

Offset

0,2

Comments

This sequence maps A000108(n) oriented (plane) rooted general trees encoded in range [A014137(n-1)..A014138(n)] of A014486 to A000081(n+1) distinct non-oriented rooted general trees, encoded by their Matula-Goebel numbers. The latter encoding is explained in A061773.

A005517 and A005518 give the minimum and maximum value occurring in each such range.

Primes occur at positions given by A057548 (not in order, and with duplicates), and similarly, semiprimes, A001358, occur at positions given by A057518, and in general, A001222(a(n)) = A057515(n).

If the signature-permutation of a Catalan automorphism SP satisfies the condition A127301(SP(n)) = A127301(n) for all n, then it preserves the non-oriented form of a general tree, which implies also that it is Łukasiewicz-word permuting, satisfying A129593(SP(n)) = A129593(n) for all n >= 0. Examples of such automorphisms include A072796, A057508, A057509/A057510, A057511/A057512, A057164, A127285/A127286 and A127287/A127288.

A206487(n) tells how many times n occurs in this sequence. - Antti Karttunen, Jan 03 2013

Links

Antti Karttunen, Table of n, a(n) for n = 0..6917

OEIS Wiki, Łukasiewicz words

Index entries for sequences related to Łukasiewicz

Index entries for sequences related to Matula-Goebel numbers

Formula

A001222(a(n)) = A057515(n) for all n.

Example

A000081(n+1) distinct values occur each range [A014137(n-1)..A014138(n-1)]. As an example, A014486(5) = 44 (= 101100 in binary = A063171(5)), encodes the following plane tree:
.....o
.....|
.o...o
..\./.
...*..
Matula-Goebel encoding for this tree gives a code number A000040(1) * A000040(A000040(1)) = 2*3 = 6, thus a(5)=6.
Likewise, A014486(6) = 50 (= 110010 in binary = A063171(6)) encodes the plane tree:
.o
.|
.o...o
..\./.
...*..
Matula-Goebel encoding for this tree gives a code number A000040(A000040(1)) * A000040(1) = 3*2 = 6, thus a(6) is also 6, which shows these two trees are identical if one ignores their orientation.

Mathematica

mgnum[t_]:=If[t=={}, 1, Times@@Prime/@mgnum/@t];
binbalQ[n_]:=n==0||With[{dig=IntegerDigits[n, 2]}, And@@Table[If[k==Length[dig], SameQ, LessEqual][Count[Take[dig, k], 0], Count[Take[dig, k], 1]], {k, Length[dig]}]];
bint[n_]:=If[n==0, {}, ToExpression[StringReplace[StringReplace[ToString[IntegerDigits[n, 2]/.{1->"{", 0->"}"}], ", "->""], "} {"->"}, {"]]];
Table[mgnum[bint[n]], {n, Select[Range[0, 1000], binbalQ]}] (* Gus Wiseman, Nov 22 2022 *)

Prog

(Scheme:) (define (A127301 n) (*A127301 (A014486->parenthesization (A014486 n)))) ;; A014486->parenthesization given in A014486.
(define (*A127301 s) (if (null? s) 1 (fold-left (lambda (m t) (* m (A000040 (*A127301 t)))) 1 s)))

Crossrefs

a(A014138(n)) = A007097(n+1), a(A014137(n)) = A000079(n+1) for all n.

a(|A106191(n)|) = A033844(n-1) for all n >= 1.

Cf. A001222, A005517, A005518, A057515, A057518, A057548, A127302, A129593, A153826, A209638, A243491, A243492, A243494, A243496.

For standard instead of binary encoding we have A358506.

A000108 counts ordered rooted trees, unordered A000081.

A014486 lists binary encodings of ordered rooted trees.

Cf. A001263, A061775, A196050, A206487, A358505.

Sequence in context: A334437 A264802 A243493 * A209636 A243491 A271863

Adjacent sequences: A127298 A127299 A127300 * A127302 A127303 A127304

Keyword

nonn

Author

Antti Karttunen, Jan 16 2007

Status

approved