login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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

%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 | Nested | A063171 | d d d d | z z z z | p p p p | c c c c

%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