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
KEYWORD
nonn,tabf
AUTHOR
Paolo Xausa, Mar 22 2024
STATUS
approved