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

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

Offset: 0

Author

Paolo Xausa, Mar 06 2024

Keywords

• nonn
• tabf

Comments

See A370883 for more information.

The first half of each row n >= 1 is equal to row n-1.

Examples

			Triangle begins:
  [0] 0;
  [1] 0 1;
  [2] 0 1 0 2;
  [3] 0 1 0 2 0 1 1 3;
  [4] 0 1 0 2 0 1 1 3 0 1 0 2 0 2 2 4;
  ...
The strings corresponding to row 2, in reverse lexicographical order, are:
  "))" (0 unmatched left parentheses),
  ")(" (1 unmatched left parenthesis),
  "()" (0 unmatched left parentheses), and
  "((" (2 unmatched left parentheses).
		

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, A370885.

Cf. A000079 (row lengths).

Apparently, row sums are given by A189391.

Programs

Mathematica

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

Formula

T(n,k) = A370885(n,k) - A370883(n,k).