A085197 -id:A085197 - cp's OEIS frontend

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

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.

A007001 Trajectory of 1 under the morphism 1 -> 12, 2 -> 123, 3 -> 1234, etc.

Original entry on oeis.org

1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 1, 2, 3, 1, 2

Offset: 1

N. J. A. Sloane, Mira Bernstein, James Propp

Records in this sequence occur at positions: 1, 2, 5, 14, 42, 132, 429, 1430, ... (which appear to be the Catalan numbers A000108). - Robert G. Wilson v, May 07 2005
The records do occur at Catalan numbers. Of the first C(n) numbers, the number that are equal to k is A033184(n,k), with the one n last. - Franklin T. Adams-Watters, Mar 29 2009
Let (T(1) < T(2) < ... < T(A000108(m))) denote the sequence of Young tableaux of shape (2^m) ordered lexicographically with respect to their columns, and let f(T(i), T(j)) denote the first label of disagreement among T(i) and T(j). Then, empirically, if we take away the zeros from (f(T(1), T(A000108(m) - i + 1)) - f(T(A000108(m) - i), T(A000108(m) - i + 1)), i=1..A000108(m)-1), we obtain the first A000108(m - 1) - 1 terms in this sequence. This is illustrated in the below example. - John M. Campbell, Sep 07 2018
The average of the first k terms tends to 3 as k tends to infinity. - Andrew Slattery, Jan 19 2021

			From _John M. Campbell_, Sep 07 2018: (Start)
Letting m = 5, as above let (T(1) < T(2) < ... < T(42)) denote the lexicographic sequence of Young tableaux of shape (2, 2, 2, 2, 2). In this case, the sequence (f(T(1), T(43 - i)) - f(T(42 - i), T(43 - i)), i=1..41) is equal to (0, 1, 0, 0, 2, 0, 1, 0, 0, 2, 0, 0, 0, 3, 0, 1, 0, 0, 2, 0, 1, 0, 0, 2, 0, 0, 0, 3, 0, 1, 0, 0, 2, 0, 0, 0, 3, 0, 0, 0, 0). Removing the zeroes from this tuple, we obtain (1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 3), which gives us the first 13 = A000108(m - 1) - 1 terms in this sequence. For example, the first term in the preceding tuple is 0 since T(1) and T(42) are respectively
   [ 5 10] [ 9 10]
   [ 4 9 ] [ 7 8 ]
   [ 3 8 ] [ 5 6 ]
   [ 2 7 ] [ 3 4 ]
   [ 1 6 ] [ 1 2 ]
and T(41) is equal to
   [ 9 10]
   [ 7 8 ]
   [ 5 6 ]
   [ 2 4 ]
   [ 1 3 ]
so that the first letter of disagreement between T(1) and T(42) is 2, and that between T(41) and T(42) is also 2. (End)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
J. West, Generating trees and forbidden subsequences, Proc. 6th FPSAC [ Conference on Formal Power Series and Algebraic Combinatorics ] (1994), pp. 441-450 (see p. 443).

T. D. Noe, Table of n, a(n) for n = 1..4862 (8 iterations)
C. Banderier, A. Denise, P. Flajolet, M. Bousquet-Mélou et al., Generating Functions for Generating Trees, Discrete Mathematics 246(1-3), March 2002, pp. 29-55.
Antti Karttunen, Notes concerning A080237-tree and related sequences.
S. Lehr, J. Shallit and J. Tromp, On the vector space of the automatic reals, Theoret. Comput. Sci. 163 (1996), no. 1-2, 193-210.
James Propp and N. J. A. Sloane, Email, March 1994
Index entries for sequences that are fixed points of mappings

Cf. A000245, A085182. a(n)=A076050(n)-1. Partial sums: A080336. Positions of ones: A085197. The first occurrence of each n is at A000108(n). See A085180.

Nest[ Flatten[ # /. a_Integer -> Range[a + 1]] &, {1}, 6] (* Robert G. Wilson v, Jan 24 2006 *)

a(n)=local(v,w); if(n<1,0,v=[1]; while(#v

From n > 1 onward a(n) = A080237(A081291(n-1)). - Antti Karttunen, Jul 31 2003

More terms from Larry Reeves (larryr(AT)acm.org), Sep 22 2000

A179752 Maximum depth of parenthesizations encoded by A014486, or correspondingly, maximum height for the equivalent general trees.

Original entry on oeis.org

0, 1, 1, 2, 1, 2, 2, 2, 3, 1, 2, 2, 2, 3, 2, 2, 2, 2, 3, 3, 3, 3, 4, 1, 2, 2, 2, 3, 2, 2, 2, 2, 3, 3, 3, 3, 4, 2, 2, 2, 2, 3, 2, 2, 2, 2, 3, 3, 3, 3, 4, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 1, 2, 2, 2, 3, 2, 2, 2, 2, 3, 3, 3, 3, 4, 2, 2, 2, 2, 3, 2, 2, 2, 2, 3, 3, 3, 3, 4, 3, 3, 3, 3, 3, 3, 3, 3, 4

Offset: 0

Antti Karttunen, Aug 03 2010

Each integer n appears first at position given by A014138.

			The terms A014486[1..8] encode the following rooted plane general trees:
.1.......2.......3.......4.......5.......6.......7.......8.
...........................................................
.........................................................o.
.........................................................|.
.................o.................o...o.......o...o.....o.
.................|.................|...|........\./......|.
.o.....o...o.....o.....o.o.o...o...o...o...o.....o.......o.
.|......\./......|......\|/.....\./.....\./......|.......|.
.*.......*.......*.......*.......*.......*.......*.......*.
and the corresponding parenthesizations:
.().....()()....(())...()()()..()(())..(())()..(()())..((()))
thus a(1)=1, a(2)=1, a(3)=2, a(4)=1, a(5)=2, a(6)=2, a(7)=2, a(8)=3.

Antti Karttunen, Table of n, a(n) for n = 0..2055

Cf. A179751, A126303, A126304, A080237, A085197.

blist[m_] := Select[Map[Accumulate, Permutations[PadLeft[Table[1, m], 2*m, -1]]], Min[#] >= 0 &]; Join[{{0}}, Array[Map[Max, blist[#]] &, 6]] (* Paolo Xausa, Mar 04 2024 *)

A085180 Array A(x,y) giving the position of the y-th x in A007001 listed by rising antidiagonals.

Original entry on oeis.org

1, 2, 3, 5, 4, 6, 14, 10, 7, 8, 42, 28, 13, 9, 11, 132, 84, 37, 19, 12, 15, 429, 264, 112, 41, 24, 16, 17, 1430, 858, 354, 126, 56, 27, 18, 20, 4862, 2860, 1155, 402, 131, 70, 33, 21, 22, 16796, 9724, 3861, 1320, 422, 174, 79, 36, 23, 25, 58786, 33592, 13156, 4433

Offset: 1

Antti Karttunen, Jun 18 2003

Read by upwards antidiagonals as A(1,1), A(2,1), A(1,2), A(3,1), A(2,2), A(1,3), etc.

			In A007001 each n occurs for the first time at position Cat(n), thus A(x,1) (the first row) is A000108.

Index entries for sequences that are permutations of the natural numbers

Variant: A085178.
Inverse permutation: A085181.
First row: A000108, second row: A068875 apart from initial terms, first column: A085197, central diagonal: A001453.

cp's OEIS Frontend

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

A007001 Trajectory of 1 under the morphism 1 -> 12, 2 -> 123, 3 -> 1234, etc.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A179752 Maximum depth of parenthesizations encoded by A014486, or correspondingly, maximum height for the equivalent general trees.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A085180 Array A(x,y) giving the position of the y-th x in A007001 listed by rising antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A080336 Partial sums of A007001.

Views

Author

Keywords

Links

Crossrefs

A085196 Difference of row 1 and column 1 of the array A085201.

Views

Author

Keywords

Crossrefs

Formula