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