A370220 - OEIS

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

%I #29 Mar 27 2024 15:45:14

%S 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,

%T 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,

%U 1,2,3,5,1,2,3,4,1,3,5,7,9,1,3,5,7,8,1,3,5,6,9

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

%C 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.

%D 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.

%H Paolo Xausa, <a href="/A370220/b370220.txt">Table of n, a(n) for n = 1..15521</a> (rows 1..2055 of the triangle, flattened).

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

%e 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.

%e .

%e | Properly | | A370219 | | A370221 | A370222

%e n | String | (n) | 1 2 3 4 | 1 2 3 4 | 1 2 3 4 | 1 2 3 4

%e ----+----------+----------+---------+---------+---------+---------

%e 1 | () | 10 | 1 | 1 | 1 | 0

%e 2 | ()() | 1010 | 1 1 | 1 3 | 1 2 | 0 0

%e 3 | (()) | 1100 | 0 2 | 1 2 | 2 1 | 0 1

%e 4 | ()()() | 101010 | 1 1 1 | 1 3 5 | 1 2 3 | 0 0 0

%e 5 | ()(()) | 101100 | 1 0 2 | 1 3 4 | 1 3 2 | 0 0 1

%e 6 | (())() | 110010 | 0 2 1 | 1 2 5 | 2 1 3 | 0 1 0

%e 7 | (()()) | 110100 | 0 1 2 | 1 2 4 | 2 3 1 | 0 1 1

%e 8 | ((())) | 111000 | 0 0 3 | 1 2 3 | 3 2 1 | 0 1 2

%e 9 | ()()()() | 10101010 | 1 1 1 1 | 1 3 5 7 | 1 2 3 4 | 0 0 0 0

%e 10 | ()()(()) | 10101100 | 1 1 0 2 | 1 3 5 6 | 1 2 4 3 | 0 0 0 1

%e 11 | ()(())() | 10110010 | 1 0 2 1 | 1 3 4 7 | 1 3 2 4 | 0 0 1 0

%e 12 | ()(()()) | 10110100 | 1 0 1 2 | 1 3 4 6 | 1 3 4 2 | 0 0 1 1

%e 13 | ()((())) | 10111000 | 1 0 0 3 | 1 3 4 5 | 1 4 3 2 | 0 0 1 2

%e 14 | (())()() | 11001010 | 0 2 1 1 | 1 2 5 7 | 2 1 3 4 | 0 1 0 0

%e 15 | (())(()) | 11001100 | 0 2 0 2 | 1 2 5 6 | 2 1 4 3 | 0 1 0 1

%e 16 | (()())() | 11010010 | 0 1 2 1 | 1 2 4 7 | 2 3 1 4 | 0 1 1 0

%e 17 | (()()()) | 11010100 | 0 1 1 2 | 1 2 4 6 | 2 3 4 1 | 0 1 1 1

%e 18 | (()(())) | 11011000 | 0 1 0 3 | 1 2 4 5 | 2 4 3 1 | 0 1 1 2

%e 19 | ((()))() | 11100010 | 0 0 3 1 | 1 2 3 7 | 3 2 1 4 | 0 1 2 0

%e 20 | ((())()) | 11100100 | 0 0 2 2 | 1 2 3 6 | 3 2 4 1 | 0 1 2 1

%e 21 | ((()())) | 11101000 | 0 0 1 3 | 1 2 3 5 | 3 4 2 1 | 0 1 2 2

%e 22 | (((()))) | 11110000 | 0 0 0 4 | 1 2 3 4 | 4 3 2 1 | 0 1 2 3

%t 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 Array[Delete[zlist[#], 0] &, 5]

%t (* 2nd program: uses Algorithm Z from Knuth's TAOCP section 7.2.1.6, exercise 2 *)

%t zlist[m_] := Block[{z = 2*Range[m] - 1, j},

%t Reap[

%t While[True,

%t Sow[z];

%t If[z[[m-1]] < z[[m]] - 1,

%t z[[m]]--,

%t j = m - 1; z[[m]] = 2*m - 1;

%t While[j > 1 && z[[j-1]] == z[[j]] - 1, z[[j]] = 2*j - 1; j--];

%t If[j == 1,Break[]];

%t z[[j]]--]

%t ]][[2]][[1]]];

%t Join[{{1}}, Array[Delete[zlist[#], 0] &, 4, 2]]

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

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

%K nonn,tabf

%O 1,3

%A _Paolo Xausa_, Feb 12 2024