A370885 Irregular triangle read by rows: T(n,k) is the total number of unmatched parentheses (both left and right) in the k-th string of parentheses of length n, where strings within a row are in reverse lexicographical order.

0, 1, 1, 2, 2, 0, 2, 3, 3, 1, 3, 1, 1, 1, 3, 4, 4, 2, 4, 2, 2, 2, 4, 2, 2, 0, 2, 0, 2, 2, 4, 5, 5, 3, 5, 3, 3, 3, 5, 3, 3, 1, 3, 1, 3, 3, 5, 3, 3, 1, 3, 1, 1, 1, 3, 1, 1, 1, 3, 1, 3, 3, 5, 6, 6, 4, 6, 4, 4, 4, 6, 4, 4, 2, 4, 2, 4, 4, 6, 4, 4, 2, 4, 2, 2, 2, 4, 2

Offset: 0

Author

Paolo Xausa, Mar 06 2024

Keywords

• nonn
• tabf

Comments

See A370883 for more information.

Examples

			Triangle begins:
  [0] 0;
  [1] 1 1;
  [2] 2 2 0 2;
  [3] 3 3 1 3 1 1 1 3;
  [4] 4 4 2 4 2 2 2 4 2 2 0 2 0 2 2 4;
  ...
		

References

• Donald E. Knuth, The Art of Computer Programming, Vol. 4A: Combinatorial Algorithms, Part 1, Addison-Wesley, 2011, Section 7.2.1.6, p. 459.

Links

• Paolo Xausa, Table of n, a(n) for n = 0..16382 (rows 0..13 of the triangle, flattened).

Crossrefs

Cf. A370883, A370884.

Cf. A000079 (row lengths).

Apparently, row sums are given by 2*A189391.

Programs

Mathematica

countLR[s_] := StringLength[s] - StringLength[StringJoin[StringCases[s, RegularExpression["1(?R)*+0"]]]];
Array[Map[countLR, IntegerString[Range[0, 2^#-1], 2, #]] &, 7, 0]

Formula

T(n,k) = A370883(n,k) + A370884(n,k).