A370222 Irregular triangle T(n,k) read by rows: row n gives the inversion table (see comments) of the permutation encoded by row n of A370221.

0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 2, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 2, 0, 1, 2, 0, 0, 1, 2, 1, 0, 1, 2, 2, 0, 1, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0

Offset: 1

Author

Paolo Xausa, Feb 12 2024

Keywords

• nonn
• tabf

Comments

Knuth (2011) uses the inversion table c_1, c_2, ..., c_k (defined so that exactly c_k elements to the right of k are less than k) to encode the permutation given by row n of A370221.

This way c_1 = 0 and 0 <= c_(k+1) <= c_k + 1 for 1 <= k < m, where m >= 1 is half the length of the corresponding properly nested string of parentheses (see example).

The concatenation of terms in each row from row n = 23714 to 82498 (corresponding to strings of length 22, excluding the last one) gives the A000108(11) - 1 = 58785 terms of the finite sequence A239903.

Examples

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

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

Crossrefs

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

Cf. A370219, A370220, A370221, A370292 (row sums).

Programs

Mathematica

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

Formula

T(n,k) = 2*k - 1 - A370220(n,k).