A072796 -id:A072796 - cp's OEIS frontend

A072797 Self-inverse permutation of natural numbers induced by a Catalan bijection acting on binary trees as encoded by A014486. See comments and examples for details.

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

Offset: 0

Antti Karttunen, Jun 12 2002

nonn

This bijection effects the following transformation on the unlabeled rooted plane binary trees (letters A, B, C refer to arbitrary subtrees located on those nodes and () stands for an implied terminal node).
   A   B           A   C
    \ /             \ /
     x   C    -->    x   B               ()  A        ()   A
      \ /             \ /                 \ /    -->    \ /
       x               x                   x             x
  ((a . b) . c) --> ((a . c) . b)      (() . a) ---> (() . a)
See the example for an explanation of how to obtain a given integer sequence from this definition.
Notably for this permutation, A127301(a(n)) = A127301(n) does not always hold, even though for all n, A129593(a(n)) = A129593(n). - Antti Karttunen, Jan 14 2024

			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 the two subtrees in positions marked "B" and "C" in the diagram given in the comments are:
.
                          \/     \/       \/               \/
       \/     \/         \/       \/     \/       \/ \/     \/
      \/       \/       \/       \/       \/       \_/       \/
a(n)=  2        3        4        5        7        6        8
thus we obtain the first nine terms of this sequence: 0, 1, 2, 3, 4, 5, 7, 6, 8.

Row 8 of A089840.
Cf. A014486, A057163, A072796, A127301, A129593.
Counts for the fixed points and for the number of distinct cycles (in each subrange limited by A014137) are given by A073190 and A073191.

a(n) = A057163(A072796(A057163(n))).

Further comments added by Antti Karttunen, Jun 04 2011 and Mar 30 2024

A074680 Signature permutation of the seventeenth nonrecursive Catalan automorphism in table A089840. (Rotate binary tree right if possible, otherwise swap its sides.)

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Sep 11 2002

nonn

This automorphism effects the following transformation on the unlabeled rooted plane binary trees (letters A, B, C refer to arbitrary subtrees located on those nodes and () stands for an implied terminal node.)
A...B..............B...C
.\./................\./
..x...C..-->.....A...x................()..B.......B..()
...\./............\./..................\./...-->...\./.
....x..............x....................x...........x..
((a . b) . c) -> (a . (b . c)) __ (() . b) --> (b . ())
That is, we rotate the binary tree right, in case it is possible and otherwise (if the left hand side of a tree is a terminal node) swap the right and left subtree (so that the terminal node ends to the right hand side), i.e. apply the automorphism *A069770. Look at the example in A069770 to see how this will produce the given sequence of integers.
See also the comments at A074679.

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

This automorphism has several variants, where the first clause is same (rotate binary tree to the right, if possible), but something else is done (than just swapping sides), in case the left hand side is empty: A082336, A082350, A123500, A123696. The following automorphisms can be derived recursively from this one: A057501, A074682, A074684, A074686, A074688, A074689, A089866, A120705, A122322, A122331. See also somewhat similar ones: A069774, A071659, A071655, A071657, A072090, A072094, A072092.
Inverse: A074679. Row 17 of A089840. Occurs also in A073200 as row 2156396687 as a(n) = A072796(A073280(A073282(n))). a(n) = A083927(A123497(A057123(n))).
Number of cycles: LEFT(A001683). Number of fixed points: LEFT(A019590). Max. cycle size & LCM of all cycle sizes: A089410 (in range [A014137(n-1)..A014138(n-1)] of this permutation).

Description clarified Oct 10 2006

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

Original entry on oeis.org

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

Antti Karttunen, Jan 16 2007

nonn

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

			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.

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

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.

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 *)

(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)))

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

A089839 Array A(x,y): (read as A(0,0), A(1,0), A(0,1), A(2,0), A(1,1), A(0,2), A(3,0), A(2,1), A(1,2), A(0,3),...) Position of the composition A089840[y] o A089840[x] in the table A089840.

Original entry on oeis.org

0, 1, 1, 2, 0, 2, 3, 14, 19, 3, 4, 15, 0, 21, 4, 5, 16, 6, 4, 17, 5, 6, 13, 5, 0, 3, 18, 6, 7, 12, 4, 2, 5, 6, 20, 7, 8, 21, 3, 6, 6, 4, 5, 15, 8, 9, 18, 1654606, 5, 2, 3, 2, 1654137, 13, 9, 10, 17, 1655095, 1654694, 0, 0, 0, 1654694, 1654255, 16, 10

Offset: 0

Antti Karttunen, Dec 05 2003

This is a "multiplication table" of an infinite enumerable group. Each row and column is a permutation of A001477.

			A(2,1)=14 because A089840[2] = A072796, A089840[1] = A069770 and the composition A069770 o A072796 (here the right hand side permutation acts first) yields A073269 = A089840[14]. Similarly A(2,2)=0, as A089840[2] = A072796, which being an involution, yields A001477 (= A089840[0]) when "squared".

A. Karttunen, C-program for computing the elements of this table

Column 1: A089837, row 1: A089838, the main diagonal: A089841.

A089851 Permutation of natural numbers induced by Catalan automorphism *A089851 acting on the binary trees/parenthesizations encoded by A014486/A063171.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Nov 29 2003

nonn

This automorphism effects the following transformation on the unlabeled rooted plane binary trees (letters A, B, C refer to arbitrary subtrees located on those nodes and () stands for an implied terminal node.)
...B...C...........C...A
....\./.............\./
.A...x....-->....B...x.................A..().........A...()..
..\./.............\./...................\./....-->....\./...
...x...............x.....................x.............x....
(a . (b . c)) -> (b . (c . a)) ____ (a . ()) ---> (a . ())
In terms of S-expressions, this rotates car, cadr and cddr of an S-exp
if its length > 1, otherwise keeps it intact.
Note that the first clause corresponds to generator C of Thompson's groups T and V.
(Cf. also A072796, A074679 and A154121 for other related generators).
See "Catalan Automorphisms" OEIS-Wiki page for a detailed explanation how to obtain a given integer sequence from this definition.

A. Karttunen, Catalan Automorphisms
A. Karttunen, C-program for computing this sequence
Index entries for signature-permutations induced by Catalan automorphisms

Inverse of A089853. a(n) = A089850(A072796(n)) = A057163(A089857(A057163(n))). Row 4 of A089840.

Number of cycles: A089847. Number of fixed-points: A089848 (in each range limited by A014137 and A014138).

The new mail-address, further comments and constructive implementation of Scheme-function (*A089851) added by Antti Karttunen, Jun 04 2011

A073269 Permutation of natural numbers induced by Catalan Automorphism *A073269 acting on the binary trees/parenthesizations encoded by A014486/A063171.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jun 25 2002

nonn

This automorphism effects the following transformation on the unlabeled rooted plane binary trees (letters A, B, C refer to arbitrary subtrees located on those nodes and () stands for an implied terminal node).
.....B...C.......A...C
......\./.........\./
...A...x...-->... .x...B...............A..().........()..A..
....\./.............\./.................\./....-->....\./...
.....x...............x...................x.............x....
(a . (b . c)) --> ((a . c) . b) ___ (a . ()) --> (() . a)
See the Karttunen OEIS-Wiki link for a detailed explanation of how to obtain a given integer sequence from this definition.

Row 14 of A089840. Inverse permutation: A073270. a(n) = A069770(A072796(n)).

Further comments, a mail-address and Scheme-implementation of this automorphism added by Antti Karttunen, Jun 04 2011

A083927 Inverse function of N -> N injection A057123.

Original entry on oeis.org

0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 5, 0

Offset: 0

Antti Karttunen, May 13 2003

nonn

a(0)=0 because A057123(0)=0, but a(n) = 0 also for those n which do not occur as values of A057123. All positive natural numbers occur here once.

If g(n) = A083927(f(A057123(n))) then we can say that Catalan bijection g embeds into Catalan bijection f in scale n:2n, using the obvious binary tree -> general tree embedding. E.g. we have: A057163 = A083927(A057164(A057123(n))), A057117 = A083927(A072088(A057123(n))), A057118 = A083927(A072089(A057123(n))), A069770 = A083927(A072796(A057123(n))), A072797 = A083927(A072797(A057123(n))).

Antti Karttunen, Gatomorphisms

a(A057123(n)) = n for all n. Cf. A083925-A083926, A083928-A083929, A083935.

A089853 Permutation of natural numbers induced by Catalan automorphism *A089853 acting on the binary trees/parenthesizations encoded by A014486/A063171.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Nov 29 2003

nonn

This automorphism effects the following transformation on the unlabeled rooted plane binary trees (letters A, B, C refer to arbitrary subtrees located on those nodes and () stands for an implied terminal node).
...B...C...........A...B
....\./.............\./
.A...x....-->....C...x.................A..().........A...()..
..\./.............\./...................\./....-->....\./...
...x...............x.....................x.............x....
(a . (b . c)) -> (c . (a . b)) ____ (a . ()) ---> (a . ())
In terms of S-expressions, this automorphism rotates car, cadr and cddr of an S-exp if its length > 1.
See the Karttunen OEIS-Wiki link for a detailed explanation of how to obtain a given integer sequence from this definition.

A. Karttunen, Catalan Automorphisms
A. Karttunen, C-program for computing this sequence
Index entries for signature-permutations induced by Catalan automorphisms

Inverse of A089851. a(n) = A072796(A089850(n)) = A057163(A089855(A057163(n))). Row 6 of A089840.

Number of cycles: A089847. Number of fixed-points: A089848 (in each range limited by A014137 and A014138).

Further comments and constructive implementation of Scheme-function (*A089853) added by Antti Karttunen, Jun 04 2011

A073270 Permutation of natural numbers induced by Catalan Automorphism *A073270 acting on the binary trees/parenthesizations encoded by A014486/A063171.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jun 25 2002

nonn

This automorphism effects the following transformation on the unlabeled rooted plane binary trees (letters A, B, C refer to arbitrary subtrees located on those nodes and () stands for an implied terminal node).
.A...B...............C...B
..\./.................\./
...x...C...-->.....A...x...............()..A.........A..()..
....\./.............\./.................\./....-->....\./...
.....x...............x...................x.............x....
((a . b) . c) --> (a . (c . b)) __ (() . a) ----> (a . ())
See the Karttunen OEIS-Wiki link for a detailed explanation of how to obtain a given integer sequence from this definition.

Row 19 of A089840. Inverse permutation: A073269. a(n) = A072796(A069770(n)).

A graphical description and Scheme-implementations of automorphism added by Antti Karttunen, Jun 04 2011

A073190 Number of general plane trees which are either empty (the case a(0)), or whose root degree is either 1 (i.e., the planted trees) or the two leftmost subtrees (of the root node) are identical.

Original entry on oeis.org

1, 1, 2, 3, 8, 20, 60, 181, 584, 1916, 6476, 22210, 77416, 272840, 971640, 3488925, 12621168, 45946156, 168206604, 618853270, 2286974856, 8485246456, 31596023208, 118037654258, 442287721872, 1661790513944, 6259494791096

Offset: 0

Antti Karttunen, Jun 25 2002

nonn

The Catalan bijection A072796 fixes only these kinds of trees, so this occurs in the table A073202 as row 1.

G. C. Greubel, Table of n, a(n) for n = 0..1000

Occurs for first time in A073202 as row 1. A073191(n) = (A000108(n)+A073190(n))/2. Cf. also A073192.

A073190 := proc(n) local d; Cat(n-1)+ add( (`mod`((n-d+1),2))*Cat((n-d-2)/2)*Cat(d), d=0..n-2); end;
Cat := n -> binomial(2*n,n)/(n+1);

a[n_] := CatalanNumber[n - 1] + Sum[Mod[n - d + 1, 2]*CatalanNumber[(n - d - 2)/2]*CatalanNumber[d], {d, 0, n - 2}]; a[0] = 1; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Mar 06 2016 *)

Cat(n) = binomial(2*n,n)/(n+1);
a(n) = if (n==0, 1, Cat(n-1) + sum(i=0, n-2, if (!((n-i)%2), Cat((n-i-2)/2)*Cat(i)))); \\ Michel Marcus, May 30 2018

a(0)=1, a(n) = Cat(n-1) + Sum_{i=0..n-2, (n-i) is even} Cat((n-i-2)/2)*Cat(i), where Cat(n) is A000108(n).

cp's OEIS Frontend

A072797 Self-inverse permutation of natural numbers induced by a Catalan bijection acting on binary trees as encoded by A014486. See comments and examples for details.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A074680 Signature permutation of the seventeenth nonrecursive Catalan automorphism in table A089840. (Rotate binary tree right if possible, otherwise swap its sides.)

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Scheme

Formula

A089839 Array A(x,y): (read as A(0,0), A(1,0), A(0,1), A(2,0), A(1,1), A(0,2), A(3,0), A(2,1), A(1,2), A(0,3),...) Position of the composition A089840[y] o A089840[x] in the table A089840.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A089851 Permutation of natural numbers induced by Catalan automorphism *A089851 acting on the binary trees/parenthesizations encoded by A014486/A063171.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A073269 Permutation of natural numbers induced by Catalan Automorphism *A073269 acting on the binary trees/parenthesizations encoded by A014486/A063171.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A083927 Inverse function of N -> N injection A057123.

Views

Author

Keywords

Comments

Links

Crossrefs

A089853 Permutation of natural numbers induced by Catalan automorphism *A089853 acting on the binary trees/parenthesizations encoded by A014486/A063171.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A073270 Permutation of natural numbers induced by Catalan Automorphism *A073270 acting on the binary trees/parenthesizations encoded by A014486/A063171.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A073190 Number of general plane trees which are either empty (the case a(0)), or whose root degree is either 1 (i.e., the planted trees) or the two leftmost subtrees (of the root node) are identical.