A127301 - OEIS

%I #39 Nov 22 2022 21:38:11

%S 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,

%T 28,20,24,18,28,38,26,20,26,34,22,24,18,18,21,15,28,21,38,53,37,26,37,

%U 43,29,20,15,26,37,23,34,43,67,41,22,29,41,59,31,64,48,48,56,40,48,36

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

%C 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.

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

%C 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).

%C 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.

%C A206487(n) tells how many times n occurs in this sequence. - _Antti Karttunen_, Jan 03 2013

%H Antti Karttunen, <a href="/A127301/b127301.txt">Table of n, a(n) for n = 0..6917</a>

%H OEIS Wiki, <a href="/wiki/Łukasiewicz_words">Łukasiewicz words</a>

%H <a href="/index/Lu#Lukasiewicz">Index entries for sequences related to Łukasiewicz</a>

%H <a href="/index/Mat#matula">Index entries for sequences related to Matula-Goebel numbers</a>

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

%e 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:

%e .....o

%e .....|

%e .o...o

%e ..\./.

%e ...*..

%e Matula-Goebel encoding for this tree gives a code number A000040(1) * A000040(A000040(1)) = 2*3 = 6, thus a(5)=6.

%e Likewise, A014486(6) = 50 (= 110010 in binary = A063171(6)) encodes the plane tree:

%e .o

%e .|

%e .o...o

%e ..\./.

%e ...*..

%e 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.

%t mgnum[t_]:=If[t=={},1,Times@@Prime/@mgnum/@t];

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

%t bint[n_]:=If[n==0,{},ToExpression[StringReplace[StringReplace[ToString[IntegerDigits[n,2]/.{1->"{",0->"}"}],","->""],"} {"->"},{"]]];

%t Table[mgnum[bint[n]],{n,Select[Range[0,1000],binbalQ]}] (* _Gus Wiseman_, Nov 22 2022 *)

%o (Scheme:) (define (A127301 n) (*A127301 (A014486->parenthesization (A014486 n)))) ;; A014486->parenthesization given in A014486.

%o (define (*A127301 s) (if (null? s) 1 (fold-left (lambda (m t) (* m (A000040 (*A127301 t)))) 1 s)))

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

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

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

%Y For standard instead of binary encoding we have A358506.

%Y A000108 counts ordered rooted trees, unordered A000081.

%Y A014486 lists binary encodings of ordered rooted trees.

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

%K nonn

%O 0,2

%A _Antti Karttunen_, Jan 16 2007