login
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.
3
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. A000079 (row lengths), A063171, A370943 (row sums).
Sequence in context: A114116 A054532 A260415 * A214710 A120888 A031230
KEYWORD
nonn,tabf
AUTHOR
Paolo Xausa, Mar 06 2024
STATUS
approved