A057544 -id:A057544 - cp's OEIS frontend

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

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]

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

Original entry on oeis.org

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

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 clockwise.

In A057161 and A057162, the cycles between A014138(n-1)-th and A014138(n)-th term partition A000108(n) objects encoded by the corresponding terms of A014486 into A001683(n+2) equivalence classes of flexagons (or unlabeled plane boron trees), thus the latter sequence can be counted with the Maple procedure A057162_CycleCounts given below. Cf. also the comments in A057161.

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

Inverse: A057161.
Also, an "ENIPS"-transform of A069773, and thus occurs as row 17 of A130402.
Other related permutations: A057163, A057164, A057501, A057503, A057505.
Cf. A001683 (cycle counts), A057544 (max cycle lengths).

a(n) = CatalanRankGlobal(RotateTriangularizationR(A014486[n]))
RotateTriangularizationR := n -> ReflectBinTree(RotateTriangularization(ReflectBinTree(n)));
with(group); A057162_CycleCounts := 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,RotateTriangularization(CatalanUnrank(n,r)))]; od; a := [op(a),(`if`((n < 2),1,nops(convert(b,'disjcyc'))))]; od; RETURN(a); end;
# See also the code in A057161.

As a composition of related permutations:
a(n) = A069768(A057508(n)).
a(n) = A057163(A057161(A057163(n))).
a(n) = A057164(A057503(A057164(n))). [For the proof, see pp. 53-54 in the "Introductory survey ..." draft, eq. 143.]

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

A057543 Maximum cycle length (orbit size) in the rotation permutation of 2n non-crossing handshakes.

Original entry on oeis.org

1, 1, 2, 3, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 106, 108, 110, 112, 114, 116, 118, 120, 122, 124

Offset: 0

Antti Karttunen, Sep 07 2000

nonn

That is, in permutations A057501 and A057502, the longest cycle among all cycles between the (A014138(n-2)+1)th and (A014138(n-1))th terms.

Cf. A057542, A057544, A057545.

a(0)=1, a(1)=1, a(2)=2, a(3)=3, and a(n)=2*n for n>=4.

More terms from Sean A. Irvine, Jun 13 2022

A057542 Maximum cycle length in each permutation between A038776(1) and A038776(A000108(n)).

Original entry on oeis.org

1, 1, 1, 3, 4, 16, 87, 202, 607, 1441, 4708, 41888, 44741, 339108, 1617551

Offset: 0

Antti Karttunen, Sep 07 2000

Sean A. Irvine, Java program (github)

Cycle lengths of permutation A038776 given in A038774.
Cf. A057543, A057544, A057545.
LCM's of all cycles: A060113.

map(lmax,Bf2DfBinTreePermutationCycleLengths(some_value)); (e.g. 10)
bf2df := s -> (btbf2df(binrev(s),0,1)/2); # btbf2df and binrev given in A038776
Bf2DfBinTreePermutationCycleLengths := 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,bf2df(CatalanUnrank(n,r)))]; od; a := [op(a),CycleLengths1(b)]; od; RETURN(a); end;
CycleLengths1 := b -> [[(nops(b)-convert(map(nops,convert(b,'disjcyc')),`+`)),`*`,1],op(map(nops,convert(b,'disjcyc')))];
last_term := proc(l) local n: n := nops(l); if(0 = n) then ([]) else (op(n,l)): fi: end:
lmax := proc(a) local e,z; z := 0; for e in a do if whattype(e) = list then e := last_term(e); fi; if e > z then z := e; fi; od; RETURN(z); end;

a(11)-a(14) from Sean A. Irvine, Jun 13 2022

A073203 Array of maximum cycle length sequences for the table A073200.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 2, 2, 1, 1, 2, 2, 2, 2, 1, 1, 2, 2, 2, 3, 2, 1, 1, 2, 2, 2, 6, 2, 2, 1, 1, 2, 2, 2, 8, 2, 3, 2, 1, 1, 2, 2, 2, 10, 2, 6, 4, 1, 1, 1, 2, 2, 2, 12, 2, 8, 8, 1, 2, 1, 1, 2, 2, 2, 14, 2, 10, 16, 1, 4, 1, 1, 1, 2, 2, 2, 16, 2, 12, 32, 1, 8, 2, 2, 1, 1

Offset: 0

Antti Karttunen, Jun 25 2002

Each row of this table gives the longest cycle/orbit produced by the Catalan bijection (given in the corresponding row of A073200) when it acts on A000108(n) structures encoded in the range [A014137(n-1)..A014138(n-1)] of the sequence A014486/A063171.

A. Karttunen, Gatomorphisms (With the complete source and explanation)

Cf. also A073201, A073202, A073204.
Few EIS-sequences which occur in this table. Only the first known occurrence(s) given:.
Rows 6 and 8: A011782, Row 7: A000012, Row 12, 14: A000793 (shifted right and prepended with 1), Row 261: A057543, Row 2614: A057545, Rows 2618, 17517: A057544.

A073204 Array of LCMs-of-cycle-lengths sequences for the table A073200.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 2, 2, 1, 1, 2, 2, 2, 2, 1, 1, 2, 2, 2, 6, 2, 1, 1, 2, 2, 2, 12, 2, 2, 1, 1, 2, 2, 2, 120, 2, 6, 2, 1, 1, 2, 2, 2, 120, 2, 12, 4, 1, 1, 1, 2, 2, 2, 840, 2, 120, 8, 1, 2, 1, 1, 2, 2, 2, 840, 2, 120, 16, 1, 4, 1, 1, 1, 2, 2, 2, 5040, 2, 840, 32, 1, 8, 2, 2, 1, 1

Offset: 0

Antti Karttunen, Jun 25 2002

Each row of this table gives the least common multiple of all cycle lengths produced by the Catalan bijection (given in the corresponding row of A073200) when it acts on A000108(n) structures encoded in the range [A014137(n-1)..A014138(n-1)] of the sequence A014486/A063171.

A. Karttunen, Gatomorphisms (With the complete source and explanation)

Cf. also A073201-A073203.

Few EIS-sequences occur in this table. The first known occurrences are: rows 6 and 8: A011782, Row 7: A000012, Row 2614: A060114, Row 2618 (?), ..., 17517: A057544.

A350510 Square array read by descending antidiagonals: A(n,k) is the least number m such that the base-n expansion of m contains the base-n expansions of 1..k as substrings.

Original entry on oeis.org

1, 2, 1, 6, 5, 1, 12, 11, 6, 1, 44, 38, 27, 7, 1, 44, 95, 75, 38, 8, 1, 92, 285, 331, 194, 51, 9, 1, 184, 933, 1115, 694, 310, 66, 10, 1, 1208, 2805, 4455, 3819, 1865, 466, 83, 11, 1, 1256, 7179, 17799, 16444, 8345, 3267, 668, 102, 12, 1

Offset: 2

Davis Smith, Jan 02 2022

			Square array begins:
n/k|| 1 |  2 |   3 |    4 |     5 |      6 |       7 |        8 |
================================================================|
2  || 1 |  2 |   6 |   12 |    44 |     44 |      92 |      184 |
3  || 1 |  5 |  11 |   38 |    95 |    285 |     933 |     2805 |
4  || 1 |  6 |  27 |   75 |   331 |   1115 |    4455 |    17799 |
5  || 1 |  7 |  38 |  194 |   694 |   3819 |   16444 |    82169 |
6  || 1 |  8 |  51 |  310 |  1865 |   8345 |   55001 |   289577 |
7  || 1 |  9 |  66 |  466 |  3267 |  22875 |  123717 |   947260 |
8  || 1 | 10 |  83 |  668 |  5349 |  42798 |  342391 |  2177399 |
9  || 1 | 11 | 102 |  922 |  8303 |  74733 |  672604 |  6053444 |
10 || 1 | 12 | 123 | 1234 | 12345 | 123456 | 1234567 | 12345678 |
11 || 1 | 13 | 146 | 1610 | 17715 | 194871 | 2143588 | 23579476 |

Davis Smith, Upper bounds for A350510(n, k) and various conjectured patterns.

Cf. A023811, A035239, A049363, A056744, A057544, A061845, A102305.

The first n - 1 terms of rows: 2: A047778, 3: A048435, 4: A048436, 5: A048437, 6: A048438, 7: A048439, 8: A048440, 9: A048441, 10: A007908, 11: A048442, 12: A048443, 13: A048444, 14: A048445, 15: A048446, 16: A048447.

T[n_,k_]:=(m=0;While[!ContainsAll[Subsequences@IntegerDigits[++m,n],IntegerDigits[Range@k,n]]];m);Flatten@Table[T[1+i,j+1-i],{j,9},{i,j}] (* Giorgos Kalogeropoulos, Jan 09 2022 *)

A350510_rows(n,k,N=0)= my(L=List(concat(apply(z->fromdigits([1..z],n),[1..n-1]),if(n>2,fromdigits(concat([1,0],[2..n-1]),n),[]))),T1(x)=digits(x,n),T2(x)=fromdigits(x,n),A(x)=my(S=T1(x));setbinop((y,z)->T2(S[y..z]),[1..#S]),N=if(N,N,L[#L]),A1=A(N));while(#Lsetsearch(A1,z),[1..#L+1])),A1=A(N++));listput(L,N));Vec(L)

For k < n, A(n,k) = A(n,k - 1)*n + k = Sum_{i=1..k} i*(n^(k - i)).
A(n,n) = A049363(n).
A(n,2) = A057544(n).
For n > 3, A(n,3) = A102305(n).
A(n,n - 1) = A023811(n).

cp's OEIS Frontend

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

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A057543 Maximum cycle length (orbit size) in the rotation permutation of 2n non-crossing handshakes.

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions

A057542 Maximum cycle length in each permutation between A038776(1) and A038776(A000108(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Extensions

A073203 Array of maximum cycle length sequences for the table A073200.

Views

Author

Keywords

Comments

Links

Crossrefs

A073204 Array of LCMs-of-cycle-lengths sequences for the table A073200.

Views

Author

Keywords

Comments

Links

Crossrefs

A350510 Square array read by descending antidiagonals: A(n,k) is the least number m such that the base-n expansion of m contains the base-n expansions of 1..k as substrings.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula