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,3

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.

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

Formula

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

Example

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

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

Crossrefs

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

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

Sequence in context: A287872 A191863 A166866 * A177343 A124036 A182481

Adjacent sequences: A370217 A370218 A370219 * A370221 A370222 A370223

Keyword

nonn,tabf

Author

Paolo Xausa, Feb 12 2024

Status

approved