A057548 -id:A057548 - cp's OEIS frontend

A122242 a(n) = A014486(A122241(n)).

42, 240, 916, 3748, 14960, 62104, 248176, 969304, 3876576, 15962544, 63772488, 248169896, 993554240, 4086635408, 16350541128, 63529835824, 254129143040, 1046249323840, 4184725760584, 16276030608712, 65054467548432, 267635134298624

Offset: 1

Antti Karttunen, Sep 14 2006

Question: to which Wolfram's class does this simple program belong, class 3 or class 4, or is such categorization at all applicable here?

Antti Karttunen, Table of n, a(n) for n = 1..1650
Antti Karttunen, Python program for computing this sequence and the associated images.
Antti Karttunen, Terms a(1)-a(768) drawn as binary strings, in Wolframesque fashion.
Antti Karttunen, Terms a(1)-a(256) drawn as binary strings, showing details better.
Antti Karttunen, The central parts of terms a(1) - a(20000) drawn in similar fashion. (Note the "foreshadowing ghost columns" present in the "central skyscraper" attractor that are not present at A122245. Compare also to illustrations in A376412)
Index entries for sequences related to binary expansion of n
Index entries for encodings of plane rooted trees
Index entries for sequences related to parenthesizing

Cf. A014486, A057548, A082358, A122237, A122241, A122243 (same sequence in binary).
Compare to similar Wolframesque plots given in A080070, A122229, A122232, A122235, A122239, A122245.
Cf. also A376402, A376412.

Python
```
# See the Links section
```

For n >= 1, a(1+n) = 2*a(n) XOR A376402(n), a(4+n) = 16*a(n) XOR A376412(n). - Antti Karttunen, Sep 23 2024

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

A057161 Signature-permutation of a Catalan Automorphism: rotate one step counterclockwise the triangulations of polygons encoded by A014486.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Aug 18 2000; entry revised Jun 06 2014

nonn

This is a permutation of natural numbers induced when Euler's triangulation of convex polygons, encoded by the sequence A014486 in a straightforward way (via binary trees, cf. the illustration of the rotation of a triangulated pentagon, given in the Links section) are rotated counterclockwise.
The number of cycles in range [A014137(n-1)..A014138(n)] of this permutation is given by A001683(n+2), otherwise the same sequence as for Catalan bijections *A074679/*A074680, but shifted once left (for an explanation, see the related notes in OEIS Wiki).
E.g., in range [A014137(0)..A014138(1)] = [1,1] there is one cycle (as a(1)=1), in range [A014137(1)..A014138(2)] = [2,3] there is one cycle (as a(2)=3 and a(3)=2), in range [A014137(2)..A014138(3)] = [4,8] there is also one cycle (as a(4) = 7, a(7) = 6, a(6) = 5, a(5) = 8 and a(8) = 4), and in range [A014137(3)..A014138(4)] = [9,22] there are A001683(4+2) = 4 cycles.
From the recursive forms of A057161 and A057503 it is seen that both can be viewed as a convergent limits of a process where either the left or right side argument of A085201 in formula for A057501 is "iteratively recursivized", and on the other hand, both of these can then in turn be made to converge towards A057505 by the same method, when the other side of the formula is also "recursivized".

A. Karttunen, Table of n, a(n) for n = 0..2055
A. Karttunen, Introductory Survey of Catalan Automorphisms and Bijections (an unfinished draft), pp. 51-54.
A. Karttunen, Notes on the orbits of the related permutations A074679/A074680, OEIS Wiki.
A. Karttunen, Illustration of how the five triangulations of a pentagon will rotate, and the corresponding changes it induces in the binary trees
Index entries for signature-permutations of Catalan automorphisms

Inverse: A057162.
Also, a "SPINE"-transform of A069774, and thus occurs as row 12 of A130403.
Other related permutations: A057163, A057164, A057501, A057504, A057505.
Cf. A001683 (cycle counts), A057544 (max cycle lengths).

a(n) = CatalanRankGlobal(RotateTriangularization(A014486[n]))
CatalanRankGlobal given in A057117 and the other Maple procedures in A038776.
NextSubBinTree := proc(nn) local n,z,c; n := nn; c := 0; z := 0; while(c < 1) do z := 2*z + (n mod 2); c := c + (-1)^n; n := floor(n/2); od; RETURN(z); end;
BinTreeLeftBranch := n -> NextSubBinTree(floor(n/2));
BinTreeRightBranch := n -> NextSubBinTree(floor(n/(2^(1+binwidth(BinTreeLeftBranch(n))))));
RotateTriangularization := proc(nn) local n,s,z,w; n := binrev(nn); z := 0; w := 0; while(1 = (n mod 2)) do s := BinTreeRightBranch(n); z := z + (2^w)*s; w := w + binwidth(s); z := z + (2^w); w := w + 1; n := floor(n/2); od; RETURN(z); end;

a(0) = 0, and for n>=1, a(n) = A085201(a(A072771(n)), A057548(A072772(n))). [This formula reflects the S-expression implementation given first in the Program section: A085201 is a 2-ary function corresponding to 'append', A072771 and A072772 correspond to 'car' and 'cdr' (known also as first/rest or head/tail in some languages), and A057548 corresponds to unary form of function 'list'.]
As a composition of related permutations:
a(n) = A069767(A069769(n)).
a(n) = A057163(A057162(A057163(n))).
a(n) = A057164(A057504(A057164(n))). [For a proof, see pp. 53-54 in the "Introductory survey ..." draft]

A072764 Tabular N X N -> N bijection induced by Lisp/Scheme function 'cons' combining the two planar binary trees/general trees/parenthesizations encoded by A014486(X) and A014486(Y).

Original entry on oeis.org

0, 1, 3, 2, 7, 6, 4, 8, 16, 14, 5, 17, 19, 42, 15, 9, 18, 44, 51, 43, 37, 10, 20, 47, 126, 52, 121, 38, 11, 21, 53, 135, 127, 149, 122, 39, 12, 22, 56, 154, 136, 385, 150, 123, 40, 13, 45, 60, 163, 155, 413, 386, 151, 124, 41, 23, 46, 128, 177, 164, 475, 414, 387, 152

Offset: 0

Antti Karttunen Jun 12 2002

Index entries for the sequences induced by list functions of Lisp
Index entries for sequences that are permutations of the natural numbers
A. Karttunen, Gatomorphisms (with the complete Scheme source)

Inverse permutation: A072765. a(n) = A069770(A072766(n)). Also transpose of A072766, i.e. a(n) = A072766(A038722(n)). The upper triangular region: A072773. Projection functions are A072771 ('car') & A072772 ('cdr'). The sizes of the corresponding Catalan structures: A072768. The first row: A057548, the first column: A072795, diagonal: A083938. Cf. also A080300, A025581, A002262.

a(0)=0 prepended by Sean A. Irvine, Oct 25 2024

A085169 Permutation of natural numbers induced by the Catalan bijection gma085169 acting on symbolless S-expressions encoded by A014486/A063171.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jun 23 2003

nonn

A parenthesization is fixed by the Catalan bijections A085169/A085170 if and only if no other elements than () and (()) occur at its top-level: (); ()(),(()); ()()(),()(()),(())(); ()()()(),()()(()),()(())(),(())()(),(())(()); ... There is a simple bijection between these and Zeckendorf-expansions, explaining why Fibonacci numbers gives the number of fixed points of this permutation.

In addition to "rising slope" and "descending slope" mappings from Dyck paths to noncrossing Murasaki-diagrams as illustrated in A085161 and A086431 there is also a mapping where we insert a vertical stick after every second parenthesis and connect those that are on the same level without any intermediate points below. This Catalan bijection converts between these two mappings. See the illustration at example lines.

			.........................
..._____....________.....
..|.....|..|.....|..|....
..|..|..|..|..|..|..|....
..|..|..|..|..|..|..|....
..|..|..|..|..|..|..|....
..|..|..|..|..|..|..|....
..1((2))3((4((5))6()7))..
...(())(((())()))........
...11001111001000=13256=A014486(368)
To obtain the same Murasaki diagram using the "rising slope mapping" illustrated in A085161, we should use the following Dyck path, encoded by 360th binary string in A014486/A063171:
....___.._____...........
...|...||...|.|..........
...||..|||..|.|..........
...||..|||..|.|..........
...||..||/\.|.|..........
...|/\.|/..\/\/\.........
.../..\/........\........
...11001110010100=13204=A014486(360)
So we have A085169(368)=360 and A085170(360)=368.

A. Karttunen, Gatomorphisms (With the complete Scheme source)
Index entries for signature-permutations induced by Catalan automorphisms

Inverse: A085170. a(n) = A086433(A082853(n))+A082852(n). A074684 = A083925(A085169(A057548(n))). Cf. also A085159, A085160, A085175.

Number of cycles: A086585. Number of fixed points: A000045. Max. cycle size: A086586. LCM of cycle sizes: A086587. (In range [A014137(n-1)..A014138(n-1)] of this permutation).

A085203 Array A(x,y): Position of the totally balanced binary string obtained by concatenating the binary strings A014486(x) & A014486(y) in such a way that the latter is inserted after the least significant 1-bit of the former, followed by the remaining 0-bits, if any. Listed antidiagonalwise as A(0,0), A(1,0), A(0,1), A(2,0), A(1,1), A(0,2), ...

Original entry on oeis.org

0, 1, 1, 2, 3, 2, 3, 5, 7, 3, 4, 8, 12, 8, 4, 5, 10, 21, 13, 17, 5, 6, 13, 26, 22, 31, 18, 6, 7, 15, 35, 27, 58, 32, 20, 7, 8, 18, 40, 36, 73, 59, 34, 21, 8, 9, 22, 49, 41, 100, 74, 62, 35, 22, 9, 10, 24, 63, 50, 115, 101, 76, 63, 36, 45, 10, 11, 27, 68, 64, 142, 116, 104, 77, 64, 87, 46

Offset: 0

Antti Karttunen, Jun 23 2003

This table is induced by the list-function 'app-to-xrt' whose Scheme-definition is given below, in the same way as A085201 is induced by the ordinary 'append'-function.

Transpose: A085204. Variant: A085201. Row 1: A085225, Column 1: A057548.

Cf. also A014486, A080300, A025581, A002262.

a(0, y) = y, a(x, y) = A057548(a(A072771(x), y)) if A072772(x)=0, otherwise A072764bi(A072771(x), a(A072772(x), y)).

a(x, y) = A080300(A085211bi(A014486(x), A014486(y))) = A085200(A085219bi(A071155(y), A071155(x))).

A057503 Signature-permutation of a Catalan Automorphism: Deutsch's 1998 bijection on Dyck paths.

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, 16, 19, 64, 63, 59, 58, 62, 50, 49, 46, 45, 48, 55, 54, 57, 61, 36, 35, 32, 31, 34, 27, 26, 24, 23, 25, 29, 28, 30, 33, 41, 40, 38, 37, 39, 43, 42, 44, 47, 52, 51, 53, 56, 60, 196, 195, 190, 189, 194

Offset: 0

Antti Karttunen, Sep 03 2000

nonn

Deutsch shows in his 1998 paper that this automorphism maps the number of returns of Dyck path to the height of the last peak, i.e., that A057515(n) = A080237(A057503(n)) holds for all n, thus the two parameters have the same distribution.

From the recursive forms of A057161 and A057503 it is seen that both can be viewed as a convergent limits of a process where either the left or right side argument of A085201 in formula for A057501 is "iteratively recursivized", and on the other hand, both of these can then in turn be made to converge towards A057505, when the other side of the formula is also "recursivized" in the same way. - Antti Karttunen, Jun 06 2014

Antti Karttunen, Table of n, a(n) for n = 0..2055
Emeric Deutsch, A bijection on Dyck paths and its consequences, Discrete Math., 179 (1998), 253-256.
Antti Karttunen, C program which computes this sequence..
Antti Karttunen, Introductory Survey of Catalan Automorphisms and Bijections (an unfinished draft), pp. 53-54.
Index entries for signature-permutations of Catalan automorphisms

Inverse: A057504. Row 17 of A122285. Cf. A057501, A057161, A057505.

The number of cycles, count of the fixed points, maximum cycle sizes and LCM's of all cycle sizes in range [A014137(n-1)..A014138(n)] of this permutation are given by LEFT(LEFT(A001683)), LEFT(A019590), A057544 and A057544, the same sequences as for A057162 because this is a conjugate of it (cf. the Formula section).

a(0) = 0, and for n >= 1, a(n) = A085201(A072771(n), A057548(a(A072772(n)))). [This formula reflects the S-expression implementation given first in the Program section: A085201 is a 2-ary function corresponding to 'append', A072771 and A072772 correspond to 'car' and 'cdr' (known also as first/rest or head/tail in some languages), and A057548 corresponds to the unary form of function 'list'].
a(n) = A057164(A057162(A057164(n))). [For the proof, see pp. 53-54 in the "Introductory survey ..." draft, eq. 144.]
Other identities:
A057515(n) = A080237(a(n)) holds for all n. [See the Comments section.]

Equivalence with Emeric Deutsch's 1998 bijection realized Dec 15 2006 and entry edited accordingly by Antti Karttunen, Jan 16 2007

A127291 Signature-permutation of Elizalde's and Deutsch's 2003 bijection for Dyck paths.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jan 16 2007

Deutsch and Elizalde show in their paper that this automorphism converts certain properties concerning "tunnels" of Dyck path to another set of properties concerning the number of hills, even and odd rises, as well as the number of returns (A057515), thus proving the equidistribution of the said parameters.
This automorphism is implemented with function "tau" (Scheme code given below) that takes as its arguments an S-expression and a Catalan automorphism that permutes only the top level of the list (i.e., the top-level branches of a general tree, or the whole arches of a Dyck path) and thus when the permuting automorphism is applied to a list (parenthesization) of length 2n it induces some permutation of [1..2n].
This automorphism is induced in that manner by the automorphism *A127287 and likewise, *A127289 is induced by *A127285, *A057164 by *A057508, *A057501 by *A057509 and *A057502 by *A057510.
Note that so far these examples seem to satisfy the homomorphism condition, e.g., as *A127287 = *A127285 o *A057508 so is *A127291 = *A127289 o *A057164. and likewise, as *A057510 = *A057508 o *A057509 o *A057508, so is *A057502 = *A057164 o *A057501 o *A057164.
However, it remains open what are the exact criteria of the "picking automorphism" and the corresponding permutation that this method would induce a bijection. For example, if we give *A127288 (the inverse of *A127287) to function "tau" it will not induce *A127292 and actually not a bijection at all.
Instead, we have to compute the inverse of this automorphism with another, more specific algorithm that implements Deutsch's and Elizalde's description and is given in A127300.

A. Karttunen, Table of n, a(n) for n = 0..2055
Emeric Deutsch and Sergi Elizalde, A simple and unusual bijection for Dyck paths and its consequences, Annals of Combinatorics, 7 (2003), no. 3, 281-297.
Index entries for signature-permutations of Catalan automorphisms

Inverse: A127292. a(n) = A127289(A057164(n)) = A057164(A127299(A057164(n))). A127291(A057548(n)) = A072795(A127291(n)), A127291(A072795(n)) = A127307(A127291(A057502(n))) for all n >= 1. The number of cycles, maximum cycle sizes and LCM's of all cycle sizes in range [A014137(n-1)..A014138(n-1)] of this permutation are given by A127293, A127294 and A127295. Number of fixed points begins as 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, ...

A072766 Transpose of A072764, 'cons' with arguments swapped.

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 7, 5, 14, 16, 8, 9, 15, 42, 19, 17, 10, 37, 43, 51, 44, 18, 11, 38, 121, 52, 126, 47, 20, 12, 39, 122, 149, 127, 135, 53, 21, 13, 40, 123, 150, 385, 136, 154, 56, 22, 23, 41, 124, 151, 386, 413, 155, 163, 60, 45, 24, 107, 125, 152, 387, 414, 475, 164

Offset: 0

Antti Karttunen, Jun 12 2002

A. Karttunen, Gatomorphisms (with the complete Scheme source)
Index entries for sequences that are permutations of the natural numbers

Inverse permutation: A072767. a(n) = A069770(A072764(n)). Also transpose of A072764, i.e. a(n) = A072764(A038722(n)). Projection functions are A072772 & A072771. The sizes of the corresponding Catalan structures: A072768. The first column: A057548, the first row: A072795. Cf. also A025581, A002262.

a(0)=0 prepended by Sean A. Irvine, Oct 25 2024

A122241 Iterates of A122237, starting from 4.

Original entry on oeis.org

4, 22, 54, 169, 516, 1841, 6076, 19256, 66140, 252691, 888179, 2900616

Offset: 1

Antti Karttunen, Sep 14 2006

nonn

It might be more natural to use offset 0 for the initial value a(0) = 4 since that's not the result of an actual iteration of the map A122237. However, some other sequences (A122242, A179845, A179841, ...?) depend on this and have b-files that would require to be changed. - M. F. Hasler, Jul 18 2025

Cf. A122237 = A057548 o A082358, A122242 = A014486 o A122241.

(define (A122241 n) (if (= 1 n) 4 (A122237 (A122241 (- n 1)))))

a(n+1) = A122237(a(n)) for n >= 1; a(1) = 4.

cp's OEIS Frontend

A122242 a(n) = A014486(A122241(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

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

Links

Crossrefs

Programs

Mathematica

Formula

A057161 Signature-permutation of a Catalan Automorphism: rotate one step counterclockwise the triangulations of polygons encoded by A014486.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A072764 Tabular N X N -> N bijection induced by Lisp/Scheme function 'cons' combining the two planar binary trees/general trees/parenthesizations encoded by A014486(X) and A014486(Y).

Views

Author

Keywords

Links

Crossrefs

Extensions

A085169 Permutation of natural numbers induced by the Catalan bijection gma085169 acting on symbolless S-expressions encoded by A014486/A063171.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Views

Author

Keywords

Comments

Crossrefs

Formula

A057503 Signature-permutation of a Catalan Automorphism: Deutsch's 1998 bijection on Dyck paths.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A127291 Signature-permutation of Elizalde's and Deutsch's 2003 bijection for Dyck paths.

Views

Author

Keywords

Comments

Links

Crossrefs

A072766 Transpose of A072764, 'cons' with arguments swapped.

Views

Author

Keywords

Links

Crossrefs

Extensions

A122241 Iterates of A122237, starting from 4.

Views

Author

Keywords

Comments