A370219 Irregular triangle T(n,k) read by rows: row n lists run-length encoding d_k values (see comments) for the properly nested string of parentheses encoded by A063171(n).

1, 1, 1, 0, 2, 1, 1, 1, 1, 0, 2, 0, 2, 1, 0, 1, 2, 0, 0, 3, 1, 1, 1, 1, 1, 1, 0, 2, 1, 0, 2, 1, 1, 0, 1, 2, 1, 0, 0, 3, 0, 2, 1, 1, 0, 2, 0, 2, 0, 1, 2, 1, 0, 1, 1, 2, 0, 1, 0, 3, 0, 0, 3, 1, 0, 0, 2, 2, 0, 0, 1, 3, 0, 0, 0, 4, 1, 1, 1, 1, 1, 1, 1, 1, 0, 2, 1, 1, 0, 2, 1

Offset: 1

Author

Paolo Xausa, Feb 12 2024

Keywords

• nonn
• tabf

Comments

As explained by Knuth (2011), a string of properly nested parentheses of length 2*m (for m >= 1) can be run-length encoded as ()d_1()d_2 ... ()d_m, where d_k are nonnegative integers such that d_1 + d_2 + ... + d_k <= k for 1 <= k < m and d_1 + d_2 + ... + d_m = m.

Examples

			The following table lists d_k values for properly nested strings having lengths up to 8, along with z_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 |          |         | A370220 | 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.

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 and row sums).

Cf. A370220, A370221, A370222.

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 &]]]];
dlist[m_] := Map[Append[#, m - Total[#]] &, Map[Differences, zlist[m]] - 1];
Array[Delete[dlist[#], 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]]];
dlist[m_] := Map[Append[#, m - Total[#]] &, Map[Differences, zlist[m]] - 1];
Join[{{1}}, Array[Delete[dlist[#], 0] &, 4, 2]] (* Paolo Xausa, Mar 25 2024 *)

Formula

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