A370221 Irregular triangle T(n,k) read by rows: row n lists the values encoding a permutation (see comments) related to the properly nested string of parentheses encoded by A063171(n).

1, 1, 2, 2, 1, 1, 2, 3, 1, 3, 2, 2, 1, 3, 2, 3, 1, 3, 2, 1, 1, 2, 3, 4, 1, 2, 4, 3, 1, 3, 2, 4, 1, 3, 4, 2, 1, 4, 3, 2, 2, 1, 3, 4, 2, 1, 4, 3, 2, 3, 1, 4, 2, 3, 4, 1, 2, 4, 3, 1, 3, 2, 1, 4, 3, 2, 4, 1, 3, 4, 2, 1, 4, 3, 2, 1, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 4, 3, 5

Offset

1,3

Comments

Knuth (2011) refers to these terms as p_k and defines them so that, in a properly nested string of parentheses, the k-th right parenthesis matches the p_k-th left parenthesis.

A370222 gives the corresponding values of a related inversion table.

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

Example

The following table lists p_k values for properly nested strings having lengths up to 8, along with d_k, z_k and c_k values from related combinatorial objects (see related sequences for more information). Cf. Knuth (2011), p. 442, Table 1.
.
      | Properly |          | A370219 | A370220 |         | 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

Mathematica

slist[m_] := Reverse[Select[Permutations[PadLeft[Table[-1, m], 2*m, 1]], Min[Accumulate[#]] >= 0 &]];
plist[s_] := Flatten[Reap[Module[{p, p0 = Flatten[Position[s, -1]], p1 = Flatten[Position[s, 1]], p1r}, p1r = p1; For[i = 1, i <= Length[p0], i++, p = Max[Select[p1r, # < p0[[i]] &]]; Sow[Position[p1, p]]; p1r = DeleteCases[p1r, p]]]][[2, 1]]];
Array[Delete[Map[plist, slist[#]], 0] &, 5]

Crossrefs

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

Cf. A370219, A370220, A370222, A370291 (row sums).

Sequence in context: A279522 A182592 A030298 * A098281 A207324 A352620

Adjacent sequences: A370218 A370219 A370220 * A370222 A370223 A370224

Keyword

nonn,tabf

Author

Paolo Xausa, Feb 12 2024

Status

approved