A370942 -id:A370942 - cp's OEIS frontend

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

Paolo Xausa, Mar 06 2024

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.

			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

Cf. A063171, A370883, A370942.

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

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

A370883 Irregular triangle read by rows: T(n,k) is the number of unmatched right parentheses in the k-th string of parentheses of length n, where strings within a row are in reverse lexicographical order.

Original entry on oeis.org

0, 1, 0, 2, 1, 0, 0, 3, 2, 1, 1, 1, 0, 0, 0, 4, 3, 2, 2, 2, 1, 1, 1, 2, 1, 0, 0, 0, 0, 0, 0, 5, 4, 3, 3, 3, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 6, 5, 4, 4, 4, 3, 3, 3, 4, 3, 2, 2, 2, 2, 2, 2, 4, 3, 2, 2, 2, 1, 1, 1, 2

Offset: 0

Paolo Xausa, Mar 06 2024

Using Knuth's (2011) notation, any string of parentheses can be uniquely written as s_0")"...s_p-1")"s_p"("s_p+1..."("s_q, with 0 <= p <= q, where the substrings s_i are the longest possible properly nested substrings (possibly empty). Examples of properly nested substrings are "()", "()()" and "(())()" (cf. A063171).
Exactly p right parentheses and q-p (cf. A370884) left parentheses are unmatched.
Knuth observes that the above string is part of a chain of length q+1: s_0")"...s_q-1")"s_q, s_0")"...s_q-2")"s_q-1"("s_q, ... , s_0"("s_1..."("s_q, where the q unmatched right parentheses in the first element of the chain are turned, one by one, into unmatched left parentheses in the next elements of the chain. By encoding "(" and ")" with 1 and 0, respectively, such a chain corresponds to a row in the Christmas tree pattern (cf. A367508).

			Triangle begins:
  [0] 0;
  [1] 1 0;
  [2] 2 1 0 0;
  [3] 3 2 1 1 1 0 0 0;
  [4] 4 3 2 2 2 1 1 1 2 1 0 0 0 0 0 0;
  ...
The strings corresponding to row 2, in reverse lexicographical order, are:
  "))" (2 unmatched right parentheses),
  ")(" (1 unmatched right parenthesis),
  "()" (0 unmatched right parentheses), and
  "((" (0 unmatched right parentheses).
The k-th string in row n corresponds to the binary expansion of k-1, padded with zeros on the left as to make it n digits long, with zeros replaced by ")" and ones replaced by "(".
In the following string the position of the unmatched p = 6 right parentheses is denoted by R, the position of the unmatched q-p = 3 left parentheses is denoted by L, and the q+1 = 10 properly nested substrings s_0..s_9 are marked either with E (empty) or * (nonempty).
.
   R      R      R R R R L      L            L
   ) ()() ) (()) ) ) ) ) ( (()) ( (()(()())) (
  |  \__/   \__/  | | | |  \__/   \________/  |
  E   *      *    E E E E   *         *       E
.

Donald E. Knuth, The Art of Computer Programming, Vol. 4A: Combinatorial Algorithms, Part 1, Addison-Wesley, 2011, Section 7.2.1.6, p. 459.

Paolo Xausa, Table of n, a(n) for n = 0..16382 (rows 0..13 of the triangle, flattened).

Cf. A367508, A370884 (p-q), A370885 (q), A370942 (nonempty nested substrings).
Cf. A000079 (row lengths), A063171.
Apparently, row sums are given by A189391.

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

T(n,k) = A370885(n,k) - A370884(n,k).

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula