A123492 -id:A123492 - cp's OEIS frontend

A069770 Signature permutation of the first non-identity, nonrecursive Catalan automorphism in table A089840: swap the top branches of a binary tree. An involution of nonnegative integers.

0, 1, 3, 2, 7, 8, 6, 4, 5, 17, 18, 20, 21, 22, 16, 19, 14, 9, 10, 15, 11, 12, 13, 45, 46, 48, 49, 50, 54, 55, 57, 58, 59, 61, 62, 63, 64, 44, 47, 53, 56, 60, 42, 51, 37, 23, 24, 38, 25, 26, 27, 43, 52, 39, 28, 29, 40, 30, 31, 32, 41, 33, 34, 35, 36, 129, 130, 132, 133, 134

Offset: 0

Antti Karttunen, Apr 16 2002

nonn

This is the simplest possible Catalan automorphism after the identity bijection (A001477). It effects the following transformation on the unlabeled rooted plane binary trees (letters A and B refer to arbitrary subtrees located on those vectices):
   A   B           B   A
    \ /     -->     \ /
     x               x
  (a . b)  -----> (b . a)
Applying this permutation recursively to the right hand side branch of the binary trees produces permutations A069767 and A069768 (that occur at the same index 1 in tables A122203 and A122204), and applying this recursively to the both branches of binary trees (as in pre- or postorder traversal) produces A057163 (which occurs at the same index 1 in tables A122201 and A122202) that reflects the whole binary tree.
For this permutation, A127302(a(n)) = A127302(n) for all n, [or equally, A153835(a(n)) = A153835(n)], and likewise for all such recursive derivations as mentioned above.

			To obtain the signature permutation, we apply these transformations to the binary trees as encoded and ordered by A014486 and for each n, a(n) will be the position of the tree to which the n-th tree is transformed to, as follows:
.
                   one tree of one internal
  empty tree         (non-leaf) node
      x                      \/
n=    0                      1
a(n)= 0                      1               (both are always fixed)
.
the next 7 trees, with 2-3 internal nodes, in range [A014137(1), A014137(2+1)-1] = [2,8] are:
.
                          \/     \/                 \/     \/
       \/     \/         \/       \/     \/ \/     \/       \/
      \/       \/       \/       \/       \_/       \/       \/
n=     2        3        4        5        6        7        8
.
and the new shapes after swapping their left and right hand subtrees are:
.
                        \/     \/                     \/     \/
     \/         \/     \/       \/       \/ \/       \/       \/
      \/       \/       \/       \/       \_/       \/       \/
a(n)=  3        2        7        8        6        4        5
thus we obtain the first nine terms of this sequence: 0, 1, 3, 2, 7, 8, 6, 4, 5.

Row 1 of A089840.
The number of cycles and the number of fixed points in each subrange limited by terms of A014137 are given by A007595 and A097331.
Other related sequences: A014486, A057163, A069767, A069768, A089864, A123492, A154125, A154126.
Cf. also A127302, A153835.

a(n) = A154125(A154126(n)) = A154126(A154125(n)).

a(n) = A083927(A072796(A057123(n))) = A083927(A057508(A057123(n))) = A083927(A057509(A057123(n))).

Entry revised by Antti Karttunen, Oct 11 2006 and Mar 30 2024

A089840 Signature permutations of non-recursive Catalan automorphisms (i.e., bijections of finite plane binary trees, with no unlimited recursion down to indefinite distances from the root), sorted according to the minimum number of opening nodes needed in their defining clauses.

Original entry on oeis.org

0, 1, 0, 2, 1, 0, 3, 3, 1, 0, 4, 2, 2, 1, 0, 5, 7, 3, 2, 1, 0, 6, 8, 4, 3, 2, 1, 0, 7, 6, 6, 5, 3, 2, 1, 0, 8, 4, 5, 4, 5, 3, 2, 1, 0, 9, 5, 7, 6, 6, 6, 3, 2, 1, 0, 10, 17, 8, 7, 4, 5, 6, 3, 2, 1, 0, 11, 18, 9, 8, 7, 4, 4, 4, 3, 2, 1, 0, 12, 20, 10, 12, 8, 7, 5, 5, 4, 3, 2, 1, 0, 13, 21, 14, 13, 12, 8, 7, 6

Offset: 0

Antti Karttunen, Dec 05 2003; last revised Jan 06 2009

Each row is a permutation of natural numbers and occurs only once. The table is closed with regards to the composition of its rows (see A089839) and it contains the inverse of each (their positions are shown in A089843). The permutations in table form an enumerable subgroup of the group of all size-preserving "Catalan bijections" (bijections among finite unlabeled rooted plane binary trees). The order of each element is shown at A089842.

A. Karttunen, paper in preparation, draft available by e-mail.

A. Karttunen, C-program for computing the terms of this table. Defines also the order of rows.
A. Karttunen, Prolog-program which illustrates the construction of each row

The first 22 rows of this table: row 0 (identity permutation): A001477, 1: A069770, 2: A072796, 3: A089850, 4: A089851, 5: A089852, 6: A089853, 7: A089854, 8: A072797, 9: A089855, 10: A089856, 11: A089857, 12: A074679, 13: A089858, 14: A073269, 15: A089859, 16: A089860, 17: A074680, 18: A089861, 19: A073270, 20: A089862, 21: A089863.
Other rows: row 83: A154125, row 169: A129611, row 183: A154126, row 251: A129612, row 253: A123503, row 258: A123499, row 264: A123500, row 3608: A129607, row 3613: A129605, row 3617: A129606, row 3655: A154121, row 3656: A154123,row 3702: A082354, row 3747: A154122, row 3748: A154124, row 3886: A082353, row 4069: A082351, row 4207: A089865, row 4253: A082352, row 4299: A089866, row 65167: A129609, row 65352: A129610, row 65518: A123495, row 65796: A123496, row 79361: A123492, row 1653002: A123695, row 1653063: A123696, row 1654023: A073281, row 1654249: A123498, row 1654694: A089864, row 1654720: A129604,row 1655089: A123497, row 1783367: A123713, row 1786785: A123714.
Tables A122200, A122201, A122202, A122203, A122204, A122283, A122284, A122285, A122286, A122287, A122288, A122289, A122290, A130400-A130403 give various "recursive derivations" of these non-recursive automorphisms. See also A089831, A073200.
Index sequences to this table, giving various subgroups or other important constructions: A153826, A153827, A153829, A153830, A123694, A153834, A153832, A153833.

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

Original entry on oeis.org

1, 4, 14, 14, 86, 86, 49, 86, 86, 886, 886, 454, 886, 886, 301, 301, 301, 886, 886, 301, 454, 886, 886, 13766, 13766, 6418, 13766, 13766, 3986, 3986, 3986, 13766, 13766, 3986, 6418, 13766, 13766, 3101, 3101, 1589, 3101, 3101, 1849, 1849, 3101, 13766

Offset: 0

Antti Karttunen, Jan 16 2007

nonn

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.
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.
A153835 divides natural numbers to same equivalence classes, i.e. a(i) = a(j) <=> A153835(i) = A153835(j) - Antti Karttunen, Jan 03 2013

			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:
........\/.....\/.................\/.....\/...
.......\/.......\/.....\/.\/.....\/.......\/..
......\/.......\/.......\_/.......\/.......\/.
n=.....4........5........6........7........8..
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.

Index entries for sequences related to Matula-Goebel numbers

Cf A127301, A153835, A153829.

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

Can be also computed directly as a fold, see the Scheme-program. - Antti Karttunen, Jan 03 2013

A123494 Signature permutation of a Catalan automorphism: row 79361 of table A122202.

Original entry on oeis.org

0, 1, 2, 3, 4, 8, 6, 7, 5, 9, 22, 20, 21, 10, 14, 19, 16, 17, 13, 15, 11, 12, 18, 23, 64, 62, 63, 24, 54, 61, 57, 58, 27, 55, 25, 26, 59, 37, 60, 53, 56, 38, 42, 51, 44, 45, 36, 41, 34, 35, 46, 43, 52, 39, 28, 33, 40, 30, 31, 50, 47, 29, 48, 49, 32, 65, 196, 194, 195, 66

Offset: 0

Antti Karttunen, Oct 11 2006

nonn

This is the signature-permutation of Catalan automorphism which is derived from the automorphism *A123492 with the recursion schema KROF (defined in A122202). Like automorphisms *A057163 and *A069767/*A069768 these automorphisms are closed with respect to the subset of "zigzagging" binary trees (i.e., those binary trees where there are no nodes with two nonempty branches, or equivalently, those ones for which Stanley's interpretation (c) forms a non-branching line) and thus induce a permutation of binary strings. That is, starting from the root of such a binary tree, the turns taken by nonempty branches are interpreted as binary digits 0 or 1, depending on whether the tree grows to the left or right. In this manner, the Catalan automorphisms *A123494 and *A123493 induce the Binary Reflected Gray Code (see A003188 and A006068).

Index entries for signature-permutations of Catalan automorphisms

Inverse: A123493. Row 79361 of A122202. See also A123715 and A123716.

A123493 Signature permutation of a Catalan automorphism: row 79361 of table A122201.

Original entry on oeis.org

0, 1, 2, 3, 4, 8, 6, 7, 5, 9, 13, 20, 21, 18, 14, 19, 16, 17, 22, 15, 11, 12, 10, 23, 27, 34, 35, 32, 54, 61, 57, 58, 64, 55, 48, 49, 46, 37, 41, 53, 56, 47, 42, 51, 44, 45, 50, 60, 62, 63, 59, 43, 52, 39, 28, 33, 40, 30, 31, 36, 38, 29, 25, 26, 24, 65, 69, 76, 77, 74, 96

Offset: 0

Antti Karttunen, Oct 11 2006

nonn

This is the signature-permutation of Catalan automorphism which is derived from nonrecursive Catalan automorphism *A123492 with the recursion schema FORK (defined in A122201). See further comments at A123494.

Index entries for signature-permutations of Catalan automorphisms

Inverse: A123494. Row 79361 of A122201.

A123715 Signature permutation of a Catalan automorphism: row 79361 of table A122203.

Original entry on oeis.org

0, 1, 2, 3, 4, 8, 6, 7, 5, 9, 13, 20, 21, 22, 14, 19, 16, 17, 18, 15, 11, 12, 10, 23, 27, 34, 35, 36, 54, 55, 57, 58, 59, 61, 62, 63, 64, 37, 41, 53, 56, 60, 42, 51, 44, 45, 46, 47, 48, 49, 50, 43, 52, 39, 28, 33, 40, 30, 31, 32, 38, 29, 25, 26, 24, 65, 69, 76, 77, 78, 96, 97

Offset: 0

Antti Karttunen, Oct 11 2006

nonn

This is the signature-permutation of Catalan automorphism which is derived from nonrecursive Catalan automorphism *A123492 with the recursion schema SPINE (defined in A122203).

Index entries for signature-permutations of Catalan automorphisms

Inverse: A123716. Row 79361 of A122203.

A123716 Signature permutation of a Catalan automorphism: row 79361 of table A122204.

Original entry on oeis.org

0, 1, 2, 3, 4, 8, 6, 7, 5, 9, 22, 20, 21, 10, 14, 19, 16, 17, 18, 15, 11, 12, 13, 23, 64, 62, 63, 24, 54, 61, 57, 58, 59, 55, 25, 26, 27, 37, 60, 53, 56, 38, 42, 51, 44, 45, 46, 47, 48, 49, 50, 43, 52, 39, 28, 29, 40, 30, 31, 32, 41, 33, 34, 35, 36, 65, 196, 194, 195, 66

Offset: 0

Antti Karttunen, Oct 11 2006

nonn

This is the signature-permutation of Catalan automorphism which is derived from nonrecursive Catalan automorphism *A123492 with the recursion schema ENIPS (defined in A122204).

Index entries for signature-permutations of Catalan automorphisms

Inverse: A123715. Row 79361 of A122204.

cp's OEIS Frontend

A069770 Signature permutation of the first non-identity, nonrecursive Catalan automorphism in table A089840: swap the top branches of a binary tree. An involution of nonnegative integers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A089840 Signature permutations of non-recursive Catalan automorphisms (i.e., bijections of finite plane binary trees, with no unlimited recursion down to indefinite distances from the root), sorted according to the minimum number of opening nodes needed in their defining clauses.

Views

Author

Keywords

Comments

References

Links

Crossrefs

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A123494 Signature permutation of a Catalan automorphism: row 79361 of table A122202.

Views

Author

Keywords

Comments

Links

Crossrefs

A123493 Signature permutation of a Catalan automorphism: row 79361 of table A122201.

Views

Author

Keywords

Comments

Links

Crossrefs

A123715 Signature permutation of a Catalan automorphism: row 79361 of table A122203.

Views

Author

Keywords

Comments

Links

Crossrefs

A123716 Signature permutation of a Catalan automorphism: row 79361 of table A122204.

Views

Author

Keywords

Comments

Links

Crossrefs