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,50

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.

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

Example

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.

Mathematica

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

Crossrefs

Cf. A370883, A370884, A370885.

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

Sequence in context: A114116 A054532 A260415 * A214710 A120888 A031230

Adjacent sequences: A370939 A370940 A370941 * A370943 A370944 A370945

Keyword

nonn,tabf

Author

Paolo Xausa, Mar 06 2024

Status

approved