login
Matula-Goebel signatures for plane binary trees encoded by A014486.
17

%I #14 Sep 05 2021 04:28:06

%S 1,4,14,14,86,86,49,86,86,886,886,454,886,886,301,301,301,886,886,301,

%T 454,886,886,13766,13766,6418,13766,13766,3986,3986,3986,13766,13766,

%U 3986,6418,13766,13766,3101,3101,1589,3101,3101,1849,1849,3101,13766

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

%C This sequence maps A000108(n) oriented (plane) rooted binary trees encoded in range [A014137(n-1)..A014138(n-1)] of A014486 to A001190(n+1) non-oriented rooted binary trees, encoded by their Matula-Goebel numbers (when viewed as a subset of non-oriented rooted general trees). See also the comments at A127301.

%C If the signature-permutation of a Catalan automorphism SP satisfies the condition A127302(SP(n)) = A127302(n) for all n, then it preserves the non-oriented form of a binary tree. Examples of such automorphisms include A069770, A057163, A122351, A069767/A069768, A073286-A073289, A089854, A089859/A089863, A089864, A122282, A123492-A123494, A123715/A123716, A127377-A127380, A127387 and A127388.

%C A153835 divides natural numbers to same equivalence classes, i.e. a(i) = a(j) <=> A153835(i) = A153835(j) - _Antti Karttunen_, Jan 03 2013

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

%F a(n) = A127301(A057123(n)).

%F Can be also computed directly as a fold, see the Scheme-program. - _Antti Karttunen_, Jan 03 2013

%e A001190(n+1) distinct values occur each range [A014137(n-1)..A014138(n-1)]. As an example, terms A014486(4..8) encode the following five plane binary trees:

%e ........\/.....\/.................\/.....\/...

%e .......\/.......\/.....\/.\/.....\/.......\/..

%e ......\/.......\/.......\_/.......\/.......\/.

%e n=.....4........5........6........7........8..

%e The trees in positions 4, 5, 7 and 8 all produce Matula-Goebel number A000040(1)*A000040(A000040(1)*A000040(A000040(1)*A000040(1))) = 2*A000040(2*A000040(2*2)) = 2*A000040(14) = 2*43 = 86, as they are just different planar representations of the one and same non-oriented tree. The tree in position 6 produces Matula-Goebel number A000040(A000040(1)*A000040(1)) * A000040(A000040(1)*A000040(1)) = A000040(2*2) * A000040(2*2) = 7*7 = 49. Thus a(4..8) = 86,86,49,86,86.

%o (Scheme with _Antti Karttunen_'s IntSeq-library, definition added here Jan 03 2013):

%o (definec (A127302 n) (*A127302 (A014486->parenthesization (A014486 n))))

%o (define (*A127302 s) (fold-right (lambda (t m) (* (A000040 (*A127302 t)) (A000040 m))) 1 s))

%Y Cf A127301, A153835, A153829.

%K nonn

%O 0,2

%A _Antti Karttunen_, Jan 16 2007