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

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

Offset

1,1

Comments

See A370220 for the positions of left parentheses.

References

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.

Links

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

Example

The following table lists the positions of right parentheses for properly nested strings having lengths up to 8, along with the positions of left parentheses.
.
      | Properly |          | Pos. of right | Pos. of left
      | Nested   | A063171  | parentheses   | parentheses
    n | String   |   (n)    | (this seq.)   | (A370220)
  ----+----------+----------+---------------+---------------
    1 | ()       | 10       | 2             | 1
    2 | ()()     | 1010     | 2 4           | 1 3
    3 | (())     | 1100     | 3 4           | 1 2
    4 | ()()()   | 101010   | 2 4 6         | 1 3 5
    5 | ()(())   | 101100   | 2 5 6         | 1 3 4
    6 | (())()   | 110010   | 3 4 6         | 1 2 5
    7 | (()())   | 110100   | 3 5 6         | 1 2 4
    8 | ((()))   | 111000   | 4 5 6         | 1 2 3
    9 | ()()()() | 10101010 | 2 4 6 8       | 1 3 5 7
   10 | ()()(()) | 10101100 | 2 4 7 8       | 1 3 5 6
   11 | ()(())() | 10110010 | 2 5 6 8       | 1 3 4 7
   12 | ()(()()) | 10110100 | 2 5 7 8       | 1 3 4 6
   13 | ()((())) | 10111000 | 2 6 7 8       | 1 3 4 5
   14 | (())()() | 11001010 | 3 4 6 8       | 1 2 5 7
   15 | (())(()) | 11001100 | 3 4 7 8       | 1 2 5 6
   16 | (()())() | 11010010 | 3 5 6 8       | 1 2 4 7
   17 | (()()()) | 11010100 | 3 5 7 8       | 1 2 4 6
   18 | (()(())) | 11011000 | 3 6 7 8       | 1 2 4 5
   19 | ((()))() | 11100010 | 4 5 6 8       | 1 2 3 7
   20 | ((())()) | 11100100 | 4 5 7 8       | 1 2 3 6
   21 | ((()())) | 11101000 | 4 6 7 8       | 1 2 3 5
   22 | (((()))) | 11110000 | 5 6 7 8       | 1 2 3 4

Mathematica

zlist[m_] := With[{r = 2*Range[2, m]}, Reverse[Map[Join[{1}, #] &, Select[Subsets[Range[2, 2*m-1], {m-1}], Min[r-#] > 0 &]]]];
Table[Delete[Map[Complement[Range[2*m], #] &, zlist[m]], 0], {m, 5}] (* Paolo Xausa, Mar 27 2024 *)
(* 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[{{2}}, Table[Delete[Map[Complement[Range[2*m], #] &, zlist[m]], 0], {m, 2, 5}]] (* Paolo Xausa, Mar 27 2024 *)

Crossrefs

Cf. A063171, A370220, A072643 (row lengths), A371410 (row sums).

Sequence in context: A209138 A368149 A051297 * A338756 A078317 A105016

Adjacent sequences: A371406 A371407 A371408 * A371410 A371411 A371412

Keyword

nonn,tabf

Author

Paolo Xausa, Mar 22 2024

Status

approved