A057161 -id:A057161 - cp's OEIS frontend

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

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

A057544 Maximum cycle length (orbit size) in the rotation permutation of n+2 side polygon triangularizations.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Sep 07 2000

I.e., in permutations A057161 and A057162 (also A057503 and A057504), the longest cycle among all cycles between the (A014138(n-2)+1)-th and (A014138(n-1))-th terms.

Index entries for linear recurrences with constant coefficients, signature (2,-1).

Cf. A057542, A057543, A057545.

a(n)=if(n>2,n+2,1) \\ Charles R Greathouse IV, Jun 20 2024

a(0)=1, a(1)=1, a(2)=2, a(n)=n+2.
From Chai Wah Wu, Jul 28 2022: (Start)
a(n) = 2*a(n-1) - a(n-2) for n > 4.
G.f.: (-2*x^4 + 2*x^3 + x^2 - x + 1)/(x - 1)^2. (End)

More terms from Sean A. Irvine, Jun 13 2022

A069769 Self-inverse permutation of natural numbers induced by the automorphism Rev1CarSide! acting on the parenthesizations encoded by A014486.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 7, 6, 8, 9, 10, 11, 12, 13, 17, 18, 16, 14, 15, 21, 20, 19, 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, 58, 59, 57, 54, 55, 56, 53, 51, 52, 63, 62, 61, 60, 64, 65, 66, 67, 68, 69, 70, 71

Offset: 0

Antti Karttunen, Apr 16 2002

nonn

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

The car/cdr-flipped conjugate of A057508, i.e. A069769(n) = A057163(A057508(A057163(n))). Cf. also A069787, A057161.

A215406 A ranking algorithm for the lexicographic ordering of the Catalan families.

Original entry on oeis.org

0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4

Offset: 0

Peter Luschny, Aug 09 2012

See Antti Karttunen's code in A057117. Karttunen writes: "Maple procedure CatalanRank is adapted from the algorithm 3.23 of the CAGES (Kreher and Stinson) book."

For all n>0, a(A014486(n)) = n = A080300(A014486(n)). The sequence A080300 differs from this one in that it gives 0 for those n which are not found in A014486. - Antti Karttunen, Aug 10 2012

G. C. Greubel, Table of n, a(n) for n = 0..1000
A. Karttunen, Catalan's Triangle and ranking of Mountain Ranges
D. L. Kreher and D. R. Stinson, Combinatorial Algorithms, Generation, Enumeration and Search, CRC Press, 1998.
F. Ruskey, Algorithmic Solution of Two Combinatorial Problems, Thesis, Department of Applied Physics and Information Science, University of Victoria, 1978.

Cf. A213704, A057117, A057164, A057505, A057506, A057501, A057502, A057511, A057512, A057123, A057117, A057509, A057510, A057161, A057162, A072766, A071654, A071652, A075161, A061856, A072635, A072788, A057518, A075168, A080119, A057120, A072773.

A215406 := proc(n) local m,a,y,t,x,u,v;
m := iquo(A070939(n), 2);
a := A030101(n);
y := 0; t := 1;
for x from 0 to 2*m-2 do
    if irem(a, 2) = 1 then y := y + 1
    else u := 2*m - x;
         v := m-1 - iquo(x+y,2);
         t := t + A037012(u,v);
         y := y - 1 fi;
    a := iquo(a, 2) od;
A014137(m) - t end:
seq(A215406(i),i=0..199); # Peter Luschny, Aug 10 2012

A215406[n_] := Module[{m, d, a, y, t, x, u, v}, m = Quotient[Length[d = IntegerDigits[n, 2]], 2]; a = FromDigits[Reverse[d], 2]; y = 0; t = 1; For[x = 0, x <= 2*m - 2, x++, If[Mod[a, 2] == 1, y++, u = 2*m - x; v = m - Quotient[x + y, 2] - 1; t = t - Binomial[u - 1, v - 1] + Binomial[u - 1, v]; y--]; a = Quotient[a, 2]]; (1 - I*Sqrt[3])/2 - 4^(m + 1)*Gamma[m + 3/2]*Hypergeometric2F1[1, m + 3/2, m + 3, 4]/(Sqrt[Pi]*Gamma[m + 3]) - t]; Table[A215406[n] // Simplify, {n, 0, 86}] (* Jean-François Alcover, Jul 25 2013, translated and adapted from Peter Luschny's Maple program *)

def A215406(n) : # CatalanRankGlobal(n)
    m = A070939(n)//2
    a = A030101(n)
    y = 0; t = 1
    for x in (1..2*m-1) :
        u = 2*m - x; v = m - (x+y+1)/2
        mn = binomial(u, v) - binomial(u, v-1)
        t += mn*(1 - a%2)
        y -= (-1)^a
        a = a//2
    return A014137(m) - t

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A057544 Maximum cycle length (orbit size) in the rotation permutation of n+2 side polygon triangularizations.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions

A069769 Self-inverse permutation of natural numbers induced by the automorphism Rev1CarSide! acting on the parenthesizations encoded by A014486.

Views

Author

Keywords

Links

Crossrefs

A215406 A ranking algorithm for the lexicographic ordering of the Catalan families.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Sage