cp's OEIS Frontend

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.

%I A370942 #27 Mar 13 2024 04:43:41
%S A370942 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,
%T A370942 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,
%U A370942 1,1,0,1,1,1,1,1,1,1,0,1,1,2,1,1,1,2,1,1
%N 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.
%C A370942 This sequence counts the nonempty s_i substrings described in A370883.
%C A370942 The first half of each row n >= 1 is equal to row n-1.
%D A370942 Donald E. Knuth, The Art of Computer Programming, Vol. 4A: Combinatorial Algorithms, Part 1, Addison-Wesley, 2011, Section 7.2.1.6, p. 459.
%H A370942 Paolo Xausa, <a href="/A370942/b370942.txt">Table of n, a(n) for n = 0..16382</a> (rows 0..13 of the triangle, flattened).
%e A370942 Triangle begins:
%e A370942   [0] 0;
%e A370942   [1] 0 0;
%e A370942   [2] 0 0 1 0;
%e A370942   [3] 0 0 1 0 1 1 1 0;
%e A370942   [4] 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0;
%e A370942   ...
%e A370942 T(2,3) is 1 because the corresponding string, "()", coincides with a properly nested string.
%e A370942 T(5,19) is 2 because the corresponding string, "())()", can be split into "()", ")" and "()": there are two copies of the nested substring "()".
%e A370942 T(7,99) is 2 because the corresponding string, "(()))()", can be split into the substrings "(())", ")" and "()", two of which are properly nested.
%t A370942 countS[s_] := StringCount[s, RegularExpression["(1(?R)*+0)++"]];
%t A370942 Array[countS[IntegerString[Range[0, 2^#-1], 2, #]] &, 7, 0]
%Y A370942 Cf. A370883, A370884, A370885.
%Y A370942 Cf. A000079 (row lengths), A063171, A370943 (row sums).
%K A370942 nonn,tabf
%O A370942 0,50
%A A370942 _Paolo Xausa_, Mar 06 2024