A370942 Irregular triangle read by rows: T(n,k) is the number of nonempty, longest nonoverlapping properly nested substrings into which the k-th string of parentheses of length n can be split into, where strings within a row are in reverse lexicographical order.

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

Offset: 0

Author

Paolo Xausa, Mar 06 2024

Keywords

• nonn
• tabf

Comments

This sequence counts the nonempty s_i substrings described in A370883.

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

Examples

			Triangle begins:
  [0] 0;
  [1] 0 0;
  [2] 0 0 1 0;
  [3] 0 0 1 0 1 1 1 0;
  [4] 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0;
  ...
T(2,3) is 1 because the corresponding string, "()", coincides with a properly nested string.
T(5,19) is 2 because the corresponding string, "())()", can be split into "()", ")" and "()": there are two copies of the nested substring "()".
T(7,99) is 2 because the corresponding string, "(()))()", can be split into the substrings "(())", ")" and "()", two of which are properly nested.
		

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

Cf. A000079 (row lengths), A063171, A370943 (row sums).

Programs

Mathematica

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