A371409 -id:A371409 - cp's OEIS frontend

A371410 Row sums of A371409: sums of the positions of right parentheses in the properly nested string of parentheses encoded by A063171(n).

2, 6, 7, 12, 13, 13, 14, 15, 20, 21, 21, 22, 23, 21, 22, 22, 23, 24, 23, 24, 25, 26, 30, 31, 31, 32, 33, 31, 32, 32, 33, 34, 33, 34, 35, 36, 31, 32, 32, 33, 34, 32, 33, 33, 34, 35, 34, 35, 36, 37, 33, 34, 34, 35, 36, 35, 36, 37, 38, 36, 37, 38, 39, 40, 42, 43, 43, 44, 45, 43

Offset: 1

Paolo Xausa, Mar 22 2024

nonn

See A370220 and A371409 for more information.

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.

Paolo Xausa, Table of n, a(n) for n = 1..10000

Cf. A063171, A370220, A370290, A371409.

zlist[m_] := With[{r = 2*Range[2, m]}, Reverse[Map[Join[{1}, #] &, Select[Subsets[Range[2, 2*m-1], {m-1}], Min[r-#] > 0 &]]]];
Table[Delete[Map[Total[Complement[Range[2*m], #]] &, zlist[m]], 0], {m, 5}] (* Paolo Xausa, Mar 25 2024 *)
(* 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[{2}, Table[Delete[Map[Total[Complement[Range[2*m], #]] &, zlist[m]], 0], {m, 2, 5}]] (* Paolo Xausa, Mar 25 2024 *)

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

Original entry on oeis.org

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

Paolo Xausa, Feb 12 2024

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.

			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

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.

Paolo Xausa, Table of n, a(n) for n = 1..15521 (rows 1..2055 of the triangle, flattened).

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

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

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

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

cp's OEIS Frontend

A371410 Row sums of A371409: sums of the positions of right parentheses in the properly nested string of parentheses encoded by A063171(n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica