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

Author

Paolo Xausa, Mar 22 2024

Keywords

• nonn
• tabf

Comments

See A370220 for the positions of left parentheses.

Examples

			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
		

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).

Crossrefs

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

Programs

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 *)