cp's OEIS Frontend

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

%I A370219 #36 Mar 27 2024 15:45:56
%S A370219 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,
%T A370219 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,
%U A370219 0,0,1,3,0,0,0,4,1,1,1,1,1,1,1,1,0,2,1,1,0,2,1
%N 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).
%C A370219 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.
%D A370219 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.
%H A370219 Paolo Xausa, <a href="/A370219/b370219.txt">Table of n, a(n) for n = 1..15521</a> (rows 1..2055 of the triangle, flattened).
%F A370219 T(n,k) = A370220(n,k+1) - A370220(n,k) - 1, for 1 <= k < A072643(n).
%e A370219 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.
%e A370219 .
%e A370219       | Properly |          |         | A370220 | A370221 | A370222
%e A370219       | Nested   | A063171  | d d d d | z z z z | p p p p | c c c c
%e A370219     n | String   |   (n)    | 1 2 3 4 | 1 2 3 4 | 1 2 3 4 | 1 2 3 4
%e A370219   ----+----------+----------+---------+---------+---------+---------
%e A370219     1 | ()       | 10       | 1       | 1       | 1       | 0
%e A370219     2 | ()()     | 1010     | 1 1     | 1 3     | 1 2     | 0 0
%e A370219     3 | (())     | 1100     | 0 2     | 1 2     | 2 1     | 0 1
%e A370219     4 | ()()()   | 101010   | 1 1 1   | 1 3 5   | 1 2 3   | 0 0 0
%e A370219     5 | ()(())   | 101100   | 1 0 2   | 1 3 4   | 1 3 2   | 0 0 1
%e A370219     6 | (())()   | 110010   | 0 2 1   | 1 2 5   | 2 1 3   | 0 1 0
%e A370219     7 | (()())   | 110100   | 0 1 2   | 1 2 4   | 2 3 1   | 0 1 1
%e A370219     8 | ((()))   | 111000   | 0 0 3   | 1 2 3   | 3 2 1   | 0 1 2
%e A370219     9 | ()()()() | 10101010 | 1 1 1 1 | 1 3 5 7 | 1 2 3 4 | 0 0 0 0
%e A370219    10 | ()()(()) | 10101100 | 1 1 0 2 | 1 3 5 6 | 1 2 4 3 | 0 0 0 1
%e A370219    11 | ()(())() | 10110010 | 1 0 2 1 | 1 3 4 7 | 1 3 2 4 | 0 0 1 0
%e A370219    12 | ()(()()) | 10110100 | 1 0 1 2 | 1 3 4 6 | 1 3 4 2 | 0 0 1 1
%e A370219    13 | ()((())) | 10111000 | 1 0 0 3 | 1 3 4 5 | 1 4 3 2 | 0 0 1 2
%e A370219    14 | (())()() | 11001010 | 0 2 1 1 | 1 2 5 7 | 2 1 3 4 | 0 1 0 0
%e A370219    15 | (())(()) | 11001100 | 0 2 0 2 | 1 2 5 6 | 2 1 4 3 | 0 1 0 1
%e A370219    16 | (()())() | 11010010 | 0 1 2 1 | 1 2 4 7 | 2 3 1 4 | 0 1 1 0
%e A370219    17 | (()()()) | 11010100 | 0 1 1 2 | 1 2 4 6 | 2 3 4 1 | 0 1 1 1
%e A370219    18 | (()(())) | 11011000 | 0 1 0 3 | 1 2 4 5 | 2 4 3 1 | 0 1 1 2
%e A370219    19 | ((()))() | 11100010 | 0 0 3 1 | 1 2 3 7 | 3 2 1 4 | 0 1 2 0
%e A370219    20 | ((())()) | 11100100 | 0 0 2 2 | 1 2 3 6 | 3 2 4 1 | 0 1 2 1
%e A370219    21 | ((()())) | 11101000 | 0 0 1 3 | 1 2 3 5 | 3 4 2 1 | 0 1 2 2
%e A370219    22 | (((()))) | 11110000 | 0 0 0 4 | 1 2 3 4 | 4 3 2 1 | 0 1 2 3
%t A370219 zlist[m_] := With[{r = 2*Range[2, m]}, Reverse[Map[Join[{1}, #] &, Select[Subsets[Range[2, 2*m-1], {m-1}], Min[r-#] > 0 &]]]];
%t A370219 dlist[m_] := Map[Append[#, m - Total[#]] &, Map[Differences, zlist[m]] - 1];
%t A370219 Array[Delete[dlist[#], 0] &, 5]
%t A370219 (* 2nd program: uses Algorithm Z from Knuth's TAOCP section 7.2.1.6, exercise 2 *)
%t A370219 zlist[m_] := Block[{z = 2*Range[m] - 1, j},
%t A370219     Reap[
%t A370219     While[True,
%t A370219         Sow[z];
%t A370219         If[z[[m-1]] < z[[m]] - 1,
%t A370219             z[[m]]--,
%t A370219             j = m - 1; z[[m]] = 2*m - 1;
%t A370219             While[j > 1 && z[[j-1]] == z[[j]] - 1, z[[j]] = 2*j - 1; j--];
%t A370219             If[j == 1,Break[]];
%t A370219             z[[j]]--]
%t A370219     ]][[2]][[1]]];
%t A370219 dlist[m_] := Map[Append[#, m - Total[#]] &, Map[Differences, zlist[m]] - 1];
%t A370219 Join[{{1}}, Array[Delete[dlist[#], 0] &, 4, 2]] (* _Paolo Xausa_, Mar 25 2024 *)
%Y A370219 Cf. A000108, A063171, A072643 (row lengths and row sums).
%Y A370219 Cf. A370220, A370221, A370222.
%K A370219 nonn,tabf
%O A370219 1,5
%A A370219 _Paolo Xausa_, Feb 12 2024