A370883 -id:A370883 - cp's OEIS frontend

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

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

Offset: 0

Paolo Xausa, Mar 06 2024

See A370883 for more information.

The first half of each row n >= 1 is equal to row n-1.

			Triangle begins:
  [0] 0;
  [1] 0 1;
  [2] 0 1 0 2;
  [3] 0 1 0 2 0 1 1 3;
  [4] 0 1 0 2 0 1 1 3 0 1 0 2 0 2 2 4;
  ...
The strings corresponding to row 2, in reverse lexicographical order, are:
  "))" (0 unmatched left parentheses),
  ")(" (1 unmatched left parenthesis),
  "()" (0 unmatched left parentheses), and
  "((" (2 unmatched left parentheses).

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. A370883, A370885.
Cf. A000079 (row lengths).
Apparently, row sums are given by A189391.

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

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

A370885 Irregular triangle read by rows: T(n,k) is the total number of unmatched parentheses (both left and right) 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, 1, 2, 2, 0, 2, 3, 3, 1, 3, 1, 1, 1, 3, 4, 4, 2, 4, 2, 2, 2, 4, 2, 2, 0, 2, 0, 2, 2, 4, 5, 5, 3, 5, 3, 3, 3, 5, 3, 3, 1, 3, 1, 3, 3, 5, 3, 3, 1, 3, 1, 1, 1, 3, 1, 1, 1, 3, 1, 3, 3, 5, 6, 6, 4, 6, 4, 4, 4, 6, 4, 4, 2, 4, 2, 4, 4, 6, 4, 4, 2, 4, 2, 2, 2, 4, 2

Offset: 0

Paolo Xausa, Mar 06 2024

See A370883 for more information.

			Triangle begins:
  [0] 0;
  [1] 1 1;
  [2] 2 2 0 2;
  [3] 3 3 1 3 1 1 1 3;
  [4] 4 4 2 4 2 2 2 4 2 2 0 2 0 2 2 4;
  ...

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. A370883, A370884.
Cf. A000079 (row lengths).
Apparently, row sums are given by 2*A189391.

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

T(n,k) = A370883(n,k) + A370884(n,k).

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.

Original entry on oeis.org

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

Paolo Xausa, Mar 06 2024

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.

			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.

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. A370883, A370884, A370885.

Cf. A000079 (row lengths), A063171, A370943 (row sums).

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

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.

Original entry on oeis.org

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).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

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