A370943 Row sums of A370942: a(n) is the total number of nonempty, longest nonoverlapping properly nested substrings among all strings of parentheses of length n.

0, 0, 1, 4, 11, 28, 66, 152, 339, 748, 1622, 3496, 7454, 15832, 33380, 70192, 146819, 306508, 637326, 1323272, 2738922, 5662600, 11677916, 24061264

Offset: 0

Author

Paolo Xausa, Mar 06 2024

Keywords

• nonn
• hard
• more

Comments

a(n) counts the nonempty s_i substrings (as described in A370883) among all strings of parentheses of length n.

See A370942 and A370883 for more information.

Examples

			a(3) = 4 because the eight strings of parentheses of length 3 contain, in total, 4 properly nested substrings:
.
           properly
  string    nested
          substrings
  ------------------
   )))      none
   ))(      none
   )()       ()
   )((      none
   ())       ()
   ()(       ()
   (()       ()
   (((      none
		

Crossrefs

Cf. A063171, A370883, A370942.

Programs

Mathematica

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

Formula

a(0) = 0; for n >= 1, a(n) = a(n-1) + Sum_{k=2^(n-1)+1..2^n-1} A370942(n,k).