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

Comments

See A370883 for more information.

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

References

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

Links

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

Formula

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

Example

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

Mathematica

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]

Crossrefs

Cf. A370883, A370885.

Cf. A000079 (row lengths).

Apparently, row sums are given by A189391.

Sequence in context: A035232 A359269 A091603 * A325036 A194942 A129688

Adjacent sequences: A370881 A370882 A370883 * A370885 A370886 A370887

Keyword

nonn,tabf

Author

Paolo Xausa, Mar 06 2024

Status

approved