A014486 -id:A014486 - cp's OEIS frontend

A057509 Permutation of natural numbers: rotations of the bottom branches of the rooted plane trees encoded by A014486.

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

Offset: 0

Antti Karttunen, Sep 03 2000

nonn

The number of objects (rooted planar trees, mountain ranges, parenthesizations) fixed by this permutation can be computed with procedure fixedcount, which gives A034731.

Index entries for sequences that are permutations of the natural numbers
A. Karttunen, Gatomorphisms (Includes the complete Scheme program for computing this sequence)

Inverse of A057510 and the car/cdr-flipped conjugate of A069775 and also composition of A069770 & A057501, i.e. A057509(n) = A057163(A069775(A057163(n))) = A057501(A069770(n)).

Cycle counts given by A003239. Cf. also A057511.

map(CatalanRankGlobal,map(RotateBottomBranchesL, A014486));
RotateBottomBranchesL := n -> pars2binexp(rotateL(binexp2pars(n)));
rotateL := proc(a) if 0 = nops(a) then (a) else [op(cdr(a)), a[1]]; fi; end;
fixedcount := proc(n) local d,z; z := 0; for d in divisors(n) do z := z+C(d-1); od; RETURN(z); end;

A074683 Permutation of natural numbers induced by the Catalan Automorphism *A074683 acting on parenthesizations as encoded and ordered by A014486/A063171.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Sep 11 2002

nonn

This bijection maps between the "standard" ordering of binary trees as encoded by A014486 and "variant A quaternary encoding" as explained in the sequence A085184.

This is a rare example of Catalan Automorphism (with simple definition) where the cycle count sequence (A089411) is not monotone. (See A127296 for more complex example.)

Row 12 of A122202. Inverse of A074684. a(n) = A057163(A074682(A057163(n))).

The number of cycles, maximum cycle sizes and LCM's of all cycle sizes in subpermutations limited by A014137 and A014138 are given by A089411, A086586 and A089412.

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

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Sep 11 2002

nonn

This bijection maps between the "standard" ordering of binary trees as encoded by A014486 and "variant A quaternary encoding" as explained in the sequence A085184.

This is a rare example of a simply defined Catalan Automorphism where the cycle count sequence (A089411) is not monotone. (See A127296 for a much more complex example.)

Row 17 of A122201. Inverse of A074683. a(n) = A057163(A074681(A057163(n))).

The number of cycles, maximum cycle sizes and LCM's of all cycle sizes in subpermutations limited by A014137 and A014138 are given by A089411, A086586 and A089412.

A057510 Permutation of natural numbers: rotations of the bottom branches of the rooted plane trees encoded by A014486. (to opposite direction of A057509).

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Sep 03 2000

nonn

Index entries for sequences that are permutations of the natural numbers
A. Karttunen, Gatomorphisms (Includes the complete Scheme program for computing this sequence)

Inverse of A057509 and the car/cdr-flipped conjugate of A069776 and also composition of A057502 & A069770, i.e. A057510(n) = A057163(A069776(A057163(n))) = A069770(A057502(n)).

Cycle counts given by A003239. Cf. also A057512, A057513.

# reverse given in A057508, for CountCycles, see A057502, for other procedures, follow A057501.
map(CatalanRankGlobal,map(RotateBottomBranchesR, A014486));
RotateBottomBranchesR := n -> pars2binexp(rotateR(binexp2pars(n)));
rotateR := a -> reverse(rotateL(reverse(a)));
RotBBPermutationCycleCounts := proc(upto_n) local u,n,a,r,b; a := []; for n from 0 to upto_n do b := []; u := (binomial(2*n,n)/(n+1)); for r from 0 to u-1 do b := [op(b),1+CatalanRank(n,RotateBottomBranchesL(CatalanUnrank(n,r)))]; od; a := [op(a),CountCycles(b)]; od; RETURN(a); end;
A003239 := RotBBPermutationCycleCounts(some_value); (e.g. 9. Cf. A057502, A057162)

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

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

Original entry on oeis.org

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

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).
.A...B...........B...A
..\./.............\./
...x...C....-->....x...C...............()..A.........()..A..
....\./.............\./.................\./....-->....\./...
.....x...............x...................x.............x....
((a . b) . c) -> ((b . a) . c) ___ (() . a) ---> (() . a)
In terms of S-expressions, this automorphism swaps caar and cdar of an S-exp if its first element is not ().
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

a(n) = A089859(A069770(n)) = A069770(A089863(n)) = A057163(A089850(A057163(n))). Row 7 of A089840. Cf. A122282.

Number of cycles: A073191. Number of fixed points: A073190. Max. cycle size & LCM of all cycle sizes: A046698 (in each range limited by A014137 and A014138).

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

A080069 a(n) = A014486(A080068(n)).

Original entry on oeis.org

0, 2, 10, 44, 178, 740, 2868, 11852, 47522, 190104, 735842, 3090116, 11777124, 48557252, 194656036, 778669672, 3117617996, 12677727330, 49850271300, 192901051976, 795560529352, 3243898094388, 12977884832332, 51055591319170

Offset: 0

Antti Karttunen, Jan 27 2003

Note that A080068 can be also obtained as iteration of A072795 o A057506.

Antti Karttunen, Table of n, a(n) for n = 0..512
Antti Karttunen, Python program for computing this sequence and the associated image. (this replaces the old a080069.py.txt)
Antti Karttunen, Terms a(1)-a(512) drawn as binary strings.
Antti Karttunen, Terms a(1)-a(2048) drawn as binary strings.

Same sequence in binary: A080070. Compare with similar Wolframesque plots given in A122229, A122232, A122235, A122239, A122242, A122245, A328111.

Cf. A179758.

Python
```
# See attached program
```

Python program and Wolfram-like plot added by Antti Karttunen, Sep 14 2006

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

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

A072795 A014486-indices of the plane binary trees AND plane general trees whose left subtree is just a stick: \. thus corresponding to the parenthesizations whose first element (of the top-level list) is an empty parenthesization: ().

Original entry on oeis.org

1, 2, 4, 5, 9, 10, 11, 12, 13, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 197, 198, 199

Offset: 0

Antti Karttunen Jun 12 2002

nonn

This sequence is induced by the 'flipped form' of the function 'list': (define (flippedlist x) (cons '() x)) when it acts on symbolless S-expressions encoded by A014486/A063171.

Gives in A063171 positions of the terms which begin with digits 10...

Column 0 of A072764, row 0 of A072766, column 1 of A085201. Complement: A081291. Cf. A085223.

Range[0, Length[#]-1] + CatalanNumber[#] & [Flatten[Array[Table[#, CatalanNumber[#]] &, 7, 0]]] (* Paolo Xausa, Mar 01 2024 *)

a(n) = n + A000108(A072643(n)) = A069770(A057548(n)) = A080300(A083937(n))

cp's OEIS Frontend

A057509 Permutation of natural numbers: rotations of the bottom branches of the rooted plane trees encoded by A014486.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

A074683 Permutation of natural numbers induced by the Catalan Automorphism *A074683 acting on parenthesizations as encoded and ordered by A014486/A063171.

Views

Author

Keywords

Comments

Links

Crossrefs

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

Views

Author

Keywords

Comments

Links

Crossrefs

A057510 Permutation of natural numbers: rotations of the bottom branches of the rooted plane trees encoded by A014486. (to opposite direction of A057509).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

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

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

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A080069 a(n) = A014486(A080068(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Extensions

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A072795 A014486-indices of the plane binary trees AND plane general trees whose left subtree is just a stick: \. thus corresponding to the parenthesizations whose first element (of the top-level list) is an empty parenthesization: ().

Views

Author

Keywords

Comments