A069772 -id:A069772 - cp's OEIS frontend

A126313 Signature-permutation of a Catalan automorphism: composition of A069772 and A125976.

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

Offset: 0

Antti Karttunen, Jan 16 2007

nonn

Like A069771, A069772, A125976 and A126315/A126316, this automorphism keeps symmetric Dyck paths symmetric, but not necessarily same.

Inverse: A126314. a(n) = A069772(A125976(n)) = A126290(A069772(n)) = A126315(A057164(n)). The number of cycles, number of fixed points, maximum cycle sizes and LCM's of all cycle sizes in range [A014137(n-1)..A014138(n-1)] of this permutation are given by A127277, A127278, A127279 and A127280. The fixed points are given by A127306. Note the curiosity: this automorphism partitions the A000108(8) = 1430 Catalan structures of size eight (e.g. Dyck paths of length 16) into 79 equivalence classes, of which the largest contains 79 members.

A126314 Signature-permutation of a Catalan automorphism: composition of A125976 and A069772.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jan 16 2007

nonn

Like A069771, A069772, A125976 and A126315/A126316, this automorphism keeps symmetric Dyck paths symmetric, but not necessarily same.

Index entries for signature-permutations of Catalan automorphisms

Inverse: A126313. a(n) = A125976(A069772(n)) = A069772(A126290(n)) = A057164(A126316(n)).

A089849 Number of fixed points in range [A014137(n-1)..A014138(n-1)] of permutation A069772.

Original entry on oeis.org

1, 1, 2, 1, 6, 2, 20, 5, 70, 14, 252, 42, 924, 132, 3432, 429, 12870, 1430, 48620, 4862, 184756, 16796, 705432, 58786, 2704156, 208012, 10400600, 742900, 40116600, 2674440, 155117520, 9694845, 601080390, 35357670, 2333606220, 129644790

Offset: 0

Antti Karttunen, Nov 29 2003

The number of n-node binary trees fixed by the corresponding automorphism(s). A000984 interleaved with A000108.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Antti Karttunen, C-program for computing the initial terms of this sequence.

Cf. A014137, A014138, A069772, A089880.

Cf. A000984 interleaved with A000108.

A089849:= func< n | n eq 0 select 1 else ((1+(-1)^n)*Binomial(n,Floor(n/2))+(1-(-1)^n)*Catalan(Floor((n-1)/2)))/2 >;
[A089849(n): n in [0..50]]; // G. C. Greubel, Feb 22 2025

a[n_] := If[EvenQ[n], Binomial[n, n/2], CatalanNumber[(n-1)/2]];
Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Mar 09 2023 *)

def A089849(n): return binomial(n, n//2) if n%2==0 else catalan_number((n-1)//2)
print([A089849(n) for n in range(51)]) # G. C. Greubel, Feb 22 2025

(define (A089849 n) (if (even? n) (A000984 (/ n 2)) (A000108 (/ (- n 1) 2))))

a(2n) = A000984(n), a(2n+1) = A000108(n).
a(n) = Sum_{k=0..floor(n/2)} binomial(k+1,n-k)*Catalan(k). - Paul Barry, Feb 23 2005
From Paul Barry, Jan 23 2006: (Start)
a(n+1) = Jacobi_P(n, 2, 0, 0)*2^n*(cos(Pi*n/2)+sin(Pi*n/2)).
a(n+1) = (Sum_{k=0..n} C(n,k)*C(n+2,k)*(-1)^k)*(cos(Pi*n/2)+sin(Pi*n/2)). (End)
From Sergei N. Gladkovskii, Dec 18 2012 (Start)
E.g.f.: 1 + integral(G(0)) dx where G(k) = 1 + 2*x/(1 - 2*x/(2*x + (2*k+2)*(2*k+4)/G(k+1) )); (continued fraction).
E.g.f.: 1 + x*G(0) where G(k) = 1 + x*(2*k+1)/(k+1 - x*(k+1)/(x + (k+2)*(2*k+3)/G(k+1) )); (continued fraction).
E.g.f.: E(x) = integral( (1/x + 2)*BesselI(1,2*x) ) dx. (End)
G.f.: G(0), where G(k) = 1 + x/(k+1 - (k+1)*(4*k+2)*x/((4*k+2)*x + 1/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jul 19 2013
From Amiram Eldar, Mar 12 2023: (Start)
Sum_{n>=0} 1/a(n) = 10/3 + 2*Pi/(3*sqrt(3)).
Sum_{n>=0} (-1)^n/a(n) = 2/3 + 2*Pi/(9*sqrt(3)). (End)

A126290 Signature-permutation of a Catalan automorphism: A069772-conjugate of A125976.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jan 02 2007

nonn

This is a self-inverse permutation (involution) of the nonnegative integers.

Index entries for signature-permutations of Catalan automorphisms

a(n) = A069772(A125976(A069772(n))) = A069771(A125976(A069771(n))).

A069766 Self-inverse permutation of natural numbers induced by the automorphism RotateHandshakes180 (A069771) or xReflectHandshakes (A069772) acting on the symmetric parenthesizations encoded by A061855.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Apr 16 2002

nonn

Index entries for sequences that are permutations of the natural numbers

Cf. A061855, A069771, A069772.

A089880 Number of cycles in range [A014137(n-1)..A014138(n-1)] of permutation A069772.

Original entry on oeis.org

1, 1, 2, 3, 10, 22, 76, 217, 750, 2438, 8524, 29414, 104468, 371516, 1338936, 4847637, 17685270, 64823110, 238843660, 883634026, 3282152588, 12233141908, 45741634536, 171529836218, 644953425740, 2430973304732, 9183681736376

Offset: 0

Antti Karttunen, Nov 29 2003

The number of orbits to which the corresponding automorphism(s) partitions the set of A000108(n) binary trees with n internal nodes.

A. Karttunen, C-program for computing the initial terms of this sequence

(define (A089880 n) (/ (+ (A000108 n) (A089849 n)) 2))

a(n) = (A000108(n)+A089849(n))/2

A057164 Self-inverse permutation of natural numbers induced by reflections of the rooted plane trees and mountain ranges encoded by A014486.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Aug 18 2000

nonn

CatalanRankGlobal given in A057117 and the other Maple procedures in A056539.

Composition with A057163 gives Donaghey's Map M (A057505/A057506).

			a(10)=14 and a(14)=10, A014486[10] = 172 (10101100 in binary), A014486[14] = 202 (11001010 in binary) and these encode the following mountain ranges (and the corresponding rooted plane trees), which are reflections of each other:
...../\___________/\
/\/\/__\_________/__\/\/\
...
...../...........\
..\|/.............\|/

Rémy Sigrist, Table of n, a(n) for n = 0..6917 (first 197 terms from Indranil Ghosh)
Antti Karttunen, Gatomorphisms (includes the complete Scheme program for computing this sequence).
Antti Karttunen, C program which implements this Catalan bijection.
Indranil Ghosh, Python program for computing the sequence.
Rémy Sigrist, PARI program.
Index entries for signature-permutations induced by Catalan automorphisms

A057123(A057163(n)) = A057164(A057123(n)) for all n. Also the car/cdr-flipped conjugate of A069787, i.e., A057164(n) = A057163(A069787(A057163(n))). Fixed terms are given by A061856. Cf. also A057508, A069772.

Row 2 of tables A122287 and A122288.

a(n) = CatalanRankGlobal(runcounts2binexp(reverse(binexp2runcounts(A014486[n])))) # i.e., reverse and complement the totally balanced binary sequences

PARI
```
See Links section.
```

a(n) = A080300(A036044(A014486(n))) = A080300(A056539(A014486(n))).

A057501 Signature-permutation of a Catalan Automorphism: Rotate non-crossing chords (handshake) arrangements; rotate the root position of general trees as encoded by A014486.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Sep 03 2000; entry revised Jun 06 2014

nonn

This is a permutation of natural numbers induced when "noncrossing handshakes", i.e., Stanley's interpretation (n), "n nonintersecting chords joining 2n points on the circumference of a circle", are rotated.
The same permutation is induced when the root position of plane trees (Stanley's interpretation (e)) is successively changed around the vertices.
For a good illustration how the rotation of the root vertex works, please see the Figure 6, "Rotation of an ordered rooted tree" in Torsten Mütze's paper (on page 24 in 20 May 2014 revision).
For yet another application of this permutation, please see the attached notes for A085197.
By "recursivizing" either the left or right hand side argument of A085201 in the formula, one ends either with A057161 or A057503. By "recursivizing" the both sides, one ends with A057505. - Antti Karttunen, Jun 06 2014

Antti Karttunen, Table of n, a(n) for n = 0..2055
A. Karttunen, Introductory Survey of Catalan Automorphisms and Bijections (an unfinished draft), pp. 56-57.
A. Karttunen et al, Combinatorial interpretations of Catalan numbers, OEIS Wiki.
Torsten Mütze, Proof of the middle levels conjecture, arXiv preprint arXiv:1404.4442 [math.CO], 2014 (p. 24).
R. P. Stanley, Exercises on Catalan and Related Numbers (This sequence is concerned with rotations of the interpretations (e) and (n) in the Exercise 19)
Index entries for signature-permutations of Catalan automorphisms

Inverse: A057502.
Also, a "SPINE"-transform of A074680, and thus occurs as row 17 of A122203. (Also as row 65167 of A130403.)
Successive powers of this permutation, a^2(n) - a^6(n): A082315, A082317, A082319, A082321, A082323.
Other related permutations: A057161, A057163, A057503, A057505, A057508, A057509, A057511, A069770, A069771, A069772, A069773, A069888, A069889, A082313, A082314, A085173, A086427, A123501, A127291, A127292.
Cf. also A057548, A072771, A072772, A085201, A002995 (cycle counts), A057543 (max cycle lengths), A085197, A129599, A057517, A064638, A064640.

map(CatalanRankGlobal,map(RotateHandshakes, A014486));
RotateHandshakes := n -> pars2binexp(RotateHandshakesP(binexp2pars(n)));
RotateHandshakesP := h -> `if`((0 = nops(h)),h,[op(car(h)),cdr(h)]); # This does the trick! In Lisp: (defun RotateHandshakesP (h) (append (car h) (list (cdr h))))
car := proc(a) if 0 = nops(a) then ([]) else (op(1,a)): fi: end: # The name is from Lisp, takes the first element (head) of the list.
cdr := proc(a) if 0 = nops(a) then ([]) else (a[2..nops(a)]): fi: end: # As well. Takes the rest (the tail) of the list.
PeelNextBalSubSeq := proc(nn) local n,z,c; if(0 = nn) then RETURN(0); fi; n := nn; c := 0; z := 0; while(1 = 1) do z := 2*z + (n mod 2); c := c + (-1)^n; n := floor(n/2); if(c >= 0) then RETURN((z - 2^(floor_log_2(z)))/2); fi; od; end;
RestBalSubSeq := proc(nn) local n,z,c; n := nn; c := 0; while(1 = 1) do c := c + (-1)^n; n := floor(n/2); if(c >= 0) then break; fi; od; z := 0; c := -1; while(1 = 1) do z := 2*z + (n mod 2); c := c + (-1)^n; n := floor(n/2); if(c >= 0) then RETURN(z/2); fi; od; end;
pars2binexp := proc(p) local e,s,w,x; if(0 = nops(p)) then RETURN(0); fi; e := 0; for s in p do x := pars2binexp(s); w := floor_log_2(x); e := e * 2^(w+3) + 2^(w+2) + 2*x; od; RETURN(e); end;
binexp2pars := proc(n) option remember; `if`((0 = n),[],binexp2parsR(binrev(n))); end;
binexp2parsR := n -> [binexp2pars(PeelNextBalSubSeq(n)),op(binexp2pars(RestBalSubSeq(n)))];
# Procedure CatalanRankGlobal given in A057117, other missing ones in A038776.

a(0) = 0, and for n>=1, a(n) = A085201(A072771(n), A057548(A072772(n))). [This formula reflects directly the given non-destructive Lisp/Scheme function: 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 dialects), and A057548 corresponds to unary form of function 'list'].
As a composition of related permutations:
a(n) = A057509(A069770(n)).
a(n) = A057163(A069773(A057163(n))).
Invariance-identities:
A129599(a(n)) = A129599(n) holds for all n.

A057502 Permutation of natural numbers: rotations of non-crossing handshakes encoded by A014486 (to opposite direction of A057501).

Original entry on oeis.org

0, 1, 3, 2, 7, 6, 8, 4, 5, 17, 16, 18, 14, 15, 20, 19, 21, 9, 10, 22, 11, 12, 13, 45, 44, 46, 42, 43, 48, 47, 49, 37, 38, 50, 39, 40, 41, 54, 53, 55, 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, 128, 130, 126, 127

Offset: 0

Antti Karttunen, Sep 03 2000

nonn

In A057501 and A057502, the cycles between (A014138(n-1)+1)-th and (A014138(n))-th term partition A000108(n) objects encoded by the corresponding terms of A014486 into A002995(n+1) equivalence classes of planar trees, thus the latter sequence can be produced also with Maple procedure RotHandshakesPermutationCycleCounts given below.

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 A057501 and the car/cdr-flipped conjugate of A069774, i.e. A057502(n) = A057163(A069774(A057163(n))). Cf. also A057507, A057510, A057513, A069771, A069772.

map(CatalanRankGlobal,map(RotateHandshakesR, A014486));
RotateHandshakesR := n -> pars2binexp(deepreverse(RotateHandshakesP(deepreverse(binexp2pars(n)))));
deepreverse := proc(a) if 0 = nops(a) or list <> whattype(a) then (a) else [op(deepreverse(cdr(a))), deepreverse(a[1])]; fi; end;
with(group); CountCycles := b -> (nops(convert(b,'disjcyc')) + (nops(b)-convert(map(nops,convert(b,'disjcyc')),`+`)));
RotHandshakesPermutationCycleCounts := 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,RotateHandshakes(CatalanUnrank(n,r)))]; od; a := [op(a),CountCycles(b)]; od; RETURN(a); end;
# For other procedures, follow A057501.

A125976 Signature-permutation of Kreweras' 1970 involution on Dyck paths.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jan 02 2007

nonn

Lalanne shows in the 1992 paper that this automorphism preserves the sum of peak heights, i.e., that A126302(a(n)) = A126302(n) for all n. Furthermore, he also shows that A126306(a(n)) = A057514(n)-1 and likewise, that A057514(a(n)) = A126306(n)+1, for all n >= 1.
Like A069772, this involution keeps symmetric Dyck paths symmetric, but not necessarily same.
The number of cycles and fixed points in range [A014137(n-1)..A014138(n-1)] of this involution seem to be given by A007595 and the "aerated" Catalan numbers [1, 1, 0, 1, 0, 2, 0, 5, 0, 14, 0, 42, ...], thus this is probably a conjugate of A069770 (as well as of A057163).

A. Karttunen, Table of n, a(n) for n = 0..2055
G. Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationelle, Cahier no. 15, Paris, 1970, pp. 3-41.
J.-C. Lalanne, Une Involution sur les Chemins de Dyck, European J. Combin. 13 (1992), no. 6, 477-487.
Index entries for signature-permutations of Catalan automorphisms

Cf. A080300, A125974, A014486.
Cf. A057163, A069770, A007595, A014137, A014138.
Compositions and conjugations with other automorphisms: A125977-A125979, A125980, A126290.

a(n) = A080300(A125974(A014486(n))).

cp's OEIS Frontend

A126313 Signature-permutation of a Catalan automorphism: composition of A069772 and A125976.

Views

Author

Keywords

Comments

Links

Crossrefs

A126314 Signature-permutation of a Catalan automorphism: composition of A125976 and A069772.

Views

Author

Keywords

Comments

Links

Crossrefs

A089849 Number of fixed points in range [A014137(n-1)..A014138(n-1)] of permutation A069772.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Scheme

Formula

A126290 Signature-permutation of a Catalan automorphism: A069772-conjugate of A125976.

Views

Author

Keywords

Comments

Links

Crossrefs

A069766 Self-inverse permutation of natural numbers induced by the automorphism RotateHandshakes180 (A069771) or xReflectHandshakes (A069772) acting on the symmetric parenthesizations encoded by A061855.

Views

Author

Keywords

Links

Crossrefs

A089880 Number of cycles in range [A014137(n-1)..A014138(n-1)] of permutation A069772.

Views

Author

Keywords

Comments

Links

Programs

Scheme

Formula

A057164 Self-inverse permutation of natural numbers induced by reflections of the rooted plane trees and mountain ranges encoded by A014486.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

A057501 Signature-permutation of a Catalan Automorphism: Rotate non-crossing chords (handshake) arrangements; rotate the root position of general trees as encoded by A014486.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A057502 Permutation of natural numbers: rotations of non-crossing handshakes encoded by A014486 (to opposite direction of A057501).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs