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

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.

Links

Table of n, a(n) for n=0..23.

Formula

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

Example

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

Mathematica

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

Crossrefs

Cf. A063171, A370883, A370942.

Sequence in context: A293628 A113478 A056601 * A003230 A099326 A127985

Adjacent sequences: A370940 A370941 A370942 * A370944 A370945 A370946

Keyword

nonn,hard,more

Author

Paolo Xausa, Mar 06 2024

Status

approved