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

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

Author

Paolo Xausa, Feb 12 2024

Keywords

• nonn
• tabf

Comments

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.

Examples

			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
		

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. See also exercise 2, p. 471 and p. 781.

Links

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

Crossrefs

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

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

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 &]]]];
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]]

Formula

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