A063171 -id:A063171 - cp's OEIS frontend

A082350 Permutation of natural numbers induced by the Catalan bijection gma082350 acting on the parenthesizations encoded by A014486/A063171.

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

Offset: 0

Antti Karttunen, Apr 17 2003

nonn

This Catalan bijection rotates binary trees right, if possible, otherwise applies Catalan bijection A069768.

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

Inverse of A082349. Cf. also A074679-A074680, A082335-A082336.

Number of cycles: A073193 (to be checked). Number of fixed-points: A019590. (In range [A014137(n-1)..A014138(n-1)] of this permutation, possibly shifted one term left or right).

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

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jun 23 2003

nonn

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

Inverse: A086426. a(n) = A057164(A074684(n)). Occurs in A073200. Cf. also A086427, A086428, A086429, A086430, A086431.

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

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jun 23 2003

nonn

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

Inverse: A086425. a(n) = A074683(A057164(n)). Occurs in A073200. Cf. also A086427, A086428, A086429, A086430, A086431.

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

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jun 23 2003

nonn

This Catalan bijection rotates by "half step" the interpretations (pp)-(rr) of Stanley, using the "descending slope" mapping illustrated in A086431.

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

Inverse: A086428. a(n) = A086431(A086428(A086431(n))) = A057164(A085173(A057164(n))) = A086425(A057501(A086426(n))). Occurs in A073200. Cf. also A086429 (whole step rotate).

Number of cycles: A002995. Number of fixed points: A019590. Max. cycle size: A057543. (In range [A014137(n-1)..A014138(n-1)] of this permutation, possibly shifted one term left or right).

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

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jun 23 2003

nonn

This Catalan bijection rotates the interpretations (pp)-(rr) of Stanley, using the "descending slope" mapping illustrated in A086431.

A. Karttunen, Gatomorphisms (With the complete Scheme source)
R. P. Stanley, Exercises on Catalan and Related Numbers (including 66 combinatorial interpretations)
Index entries for signature-permutations induced by Catalan automorphisms

Inverse: A086430. a(n) = A086427(A086427(n)) = A086431(A086430(A086431(n))) = A057164(A085159(A057164(n))) = A086425(A082315(A086426(n))). Occurs in A073200.

Number of cycles: A054357. Number of fixed points: A046698. (In range [A014137(n-1)..A014138(n-1)] of this permutation, possibly shifted one term left or right).

A089866 Permutation of natural numbers induced by Catalan Automorphism *A089866 acting on the parenthesizations/binary trees encoded by A014486/A063171.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Dec 20 2003

nonn

This bijection of binary trees is obtained when we apply bijection *A074680 to the left subtree and keep the right subtree intact.
.A...B...............B...C
..\./.................\./
...x...C....-->....A...x.................()..B.........B...()....
....\./.............\./...................\./....-->....\./.....
.....x...D...........x...D.................x...C.........x...C..
......\./.............\./...................\./...........\./...
.......x...............x.....................x.............x....
................................................................
Compare to A154122.
See "Catalan bijections" OEIS-Wiki page for a detailed explanation how to obtain a given integer sequence from this definition.

A. Karttunen, Catalan bijections
A. Karttunen, C-program for computing this sequence
Index entries for signature-permutations induced by Catalan automorphisms

Row 4299 of A089840. Inverse of A089865. a(n) = A069770(A154122(A069770(n))).

Number of cycles: A089844. Number of fixed-points: A005807 (prepended with two 1's). Max. cycle size: A089410. LCM of cycle sizes: A089845 (in each range limited by A014137 and A014138).

Further comments and constructive version of Scheme-implementation added by Antti Karttunen, Jun 04 2011

A370220 Irregular triangle T(n,k) read by rows: row n lists the positions of left parentheses for the properly nested string of parentheses encoded by A063171(n).

Original entry on oeis.org

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

Offset: 1

Paolo Xausa, Feb 12 2024

Knuth (2011) refers to these terms as z_k and notes that z_1, z_2, ..., z_m is one of the binomial(2*m,m) combinations of m >= 1 objects from the set {1, 2, ..., 2*m}, subject to the constraint that z_(k-1) < z_k < 2*k for 1 <= k <= m and assuming that z_0 = 0.

			The following table lists z_k values for properly nested strings having lengths up to 8, along with d_k, p_k and c_k values from related combinatorial objects (see related sequences for more information). Cf. Knuth (2011), p. 442, Table 1.
.
      | Properly |          | A370219 |         | A370221 | A370222
      | Nested   | A063171  | d d d d | z z z z | p p p p | c c c c
    n | String   |   (n)    | 1 2 3 4 | 1 2 3 4 | 1 2 3 4 | 1 2 3 4
  ----+----------+----------+---------+---------+---------+---------
    1 | ()       | 10       | 1       | 1       | 1       | 0
    2 | ()()     | 1010     | 1 1     | 1 3     | 1 2     | 0 0
    3 | (())     | 1100     | 0 2     | 1 2     | 2 1     | 0 1
    4 | ()()()   | 101010   | 1 1 1   | 1 3 5   | 1 2 3   | 0 0 0
    5 | ()(())   | 101100   | 1 0 2   | 1 3 4   | 1 3 2   | 0 0 1
    6 | (())()   | 110010   | 0 2 1   | 1 2 5   | 2 1 3   | 0 1 0
    7 | (()())   | 110100   | 0 1 2   | 1 2 4   | 2 3 1   | 0 1 1
    8 | ((()))   | 111000   | 0 0 3   | 1 2 3   | 3 2 1   | 0 1 2
    9 | ()()()() | 10101010 | 1 1 1 1 | 1 3 5 7 | 1 2 3 4 | 0 0 0 0
   10 | ()()(()) | 10101100 | 1 1 0 2 | 1 3 5 6 | 1 2 4 3 | 0 0 0 1
   11 | ()(())() | 10110010 | 1 0 2 1 | 1 3 4 7 | 1 3 2 4 | 0 0 1 0
   12 | ()(()()) | 10110100 | 1 0 1 2 | 1 3 4 6 | 1 3 4 2 | 0 0 1 1
   13 | ()((())) | 10111000 | 1 0 0 3 | 1 3 4 5 | 1 4 3 2 | 0 0 1 2
   14 | (())()() | 11001010 | 0 2 1 1 | 1 2 5 7 | 2 1 3 4 | 0 1 0 0
   15 | (())(()) | 11001100 | 0 2 0 2 | 1 2 5 6 | 2 1 4 3 | 0 1 0 1
   16 | (()())() | 11010010 | 0 1 2 1 | 1 2 4 7 | 2 3 1 4 | 0 1 1 0
   17 | (()()()) | 11010100 | 0 1 1 2 | 1 2 4 6 | 2 3 4 1 | 0 1 1 1
   18 | (()(())) | 11011000 | 0 1 0 3 | 1 2 4 5 | 2 4 3 1 | 0 1 1 2
   19 | ((()))() | 11100010 | 0 0 3 1 | 1 2 3 7 | 3 2 1 4 | 0 1 2 0
   20 | ((())()) | 11100100 | 0 0 2 2 | 1 2 3 6 | 3 2 4 1 | 0 1 2 1
   21 | ((()())) | 11101000 | 0 0 1 3 | 1 2 3 5 | 3 4 2 1 | 0 1 2 2
   22 | (((()))) | 11110000 | 0 0 0 4 | 1 2 3 4 | 4 3 2 1 | 0 1 2 3

Donald E. Knuth, The Art of Computer Programming, Vol. 4A: Combinatorial Algorithms, Part 1, Addison-Wesley, 2011, Section 7.2.1.6, pp. 440-444. See also exercise 2, p. 471 and p. 781.

Paolo Xausa, Table of n, a(n) for n = 1..15521 (rows 1..2055 of the triangle, flattened).

Cf. A000108, A063171, A072643 (row lengths).

Cf. A370219, A370221, A370222, A370290 (row sums), A371409 (right parentheses).

zlist[m_] := With[{r = 2*Range[2, m]}, Reverse[Map[Join[{1}, #] &, Select[Subsets[Range[2, 2*m-1], {m-1}], Min[r-#] > 0 &]]]];
Array[Delete[zlist[#], 0] &, 5]
(* 2nd program: uses Algorithm Z from Knuth's TAOCP section 7.2.1.6, exercise 2 *)
zlist[m_] := Block[{z = 2*Range[m] - 1, j},
    Reap[
    While[True,
        Sow[z];
        If[z[[m-1]] < z[[m]] - 1,
            z[[m]]--,
            j = m - 1; z[[m]] = 2*m - 1;
            While[j > 1 && z[[j-1]] == z[[j]] - 1, z[[j]] = 2*j - 1; j--];
            If[j == 1,Break[]];
            z[[j]]--]
    ]][[2]][[1]]];
Join[{{1}}, Array[Delete[zlist[#], 0] &, 4, 2]]

T(n,k) = T(n,k+1) - A370219(n,k) - 1, for 1 <= k < A072643(n).

A074682 Permutation of natural numbers induced by the Catalan bijection gmA074682! acting on the parenthesizations encoded by A014486/A063171.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Sep 11 2002

nonn

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

Inverse of A074681. a(n) = A057163(A074683(A057163(n))). Occurs in A073200.

A074688 Permutation of natural numbers induced by the Catalan bijection gmA074688! acting on the parenthesizations encoded by A014486/A063171.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Sep 11 2002

nonn

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

Inverse of A074687 and also a(n) = A057163(A074687(A057163(n))). Cf. A074681-A074690. Occurs in A073200.

A074690 Permutation of natural numbers induced by the Catalan bijection gmA074690! acting on the parenthesizations encoded by A014486/A063171.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Sep 11 2002

nonn

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

Inverse of A074689. a(n) = A057163(A074686(A057163(n))). Cf. A074681-A074688. Occurs in A073200.

cp's OEIS Frontend

A082350 Permutation of natural numbers induced by the Catalan bijection gma082350 acting on the parenthesizations encoded by A014486/A063171.

Views

Author

Keywords

Comments

Links

Crossrefs

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

Views

Author

Keywords

Links

Crossrefs

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

Views

Author

Keywords

Links

Crossrefs

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

Views

Author

Keywords

Comments

Links

Crossrefs

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

Views

Author

Keywords

Comments

Links

Crossrefs

A089866 Permutation of natural numbers induced by Catalan Automorphism *A089866 acting on the parenthesizations/binary trees encoded by A014486/A063171.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A370220 Irregular triangle T(n,k) read by rows: row n lists the positions of left parentheses for the properly nested string of parentheses encoded by A063171(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A074682 Permutation of natural numbers induced by the Catalan bijection gmA074682! acting on the parenthesizations encoded by A014486/A063171.

Views

Author

Keywords

Links

Crossrefs

A074688 Permutation of natural numbers induced by the Catalan bijection gmA074688! acting on the parenthesizations encoded by A014486/A063171.

Views

Author

Keywords

Links

Crossrefs

A074690 Permutation of natural numbers induced by the Catalan bijection gmA074690! acting on the parenthesizations encoded by A014486/A063171.

Views

Author

Keywords

Links

Crossrefs