A368750 Irregular triangle read by rows: T(n,k) is the number of atoms contained in the k-th balanced string of left/right parentheses of length 2*n, where strings within a row are in reverse lexicographical order.

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

Offset

1,7

Comments

A balanced string of parentheses is composed of the same number of left and right parentheses. E.g., "(())()" and "))(()(" are balanced, while "((()((()" is not.

A balanced string can be uniquely split into substrings s_1, s_2, ..., s_k, where s_i is either an atom (i.e., a balanced string, as short as possible, beginning with "(" and ending with ")"), or a co-atom (the reverse of an atom). Please note that, here, an atom is defined as a shortest possible properly nested substring: the string "()()" is composed of two contiguous atoms, while Knuth (2011) considers it a single atom.

To count for the number of atoms/co-atoms, we begin from the leftmost character of the string and proceed to the right, adding 1 to a counter when "(" is encountered, and subtracting 1 when ")" is encountered. Each time the counter reaches 0, we have found either an atom or a co-atom, depending on whether the starting character was a "(" or a ")", respectively.

For example, the string ")(()()(())))((" can be split into ")(" (co-atom), "()" (atom), "()" (atom), "(())" (atom) and "))((" (co-atom).

If ")" is encoded by 0 and "(" is encoded by 1, the triangle with the balanced strings is given by A368804 (and, converted to decimal, by A362030).

References

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

Links

Paolo Xausa, Table of n, a(n) for n = 1..17576 (rows 1..8 of the triangle, flattened).

Formula

T(n,k) = A368752(n,k) - A368751(n,k).

Example

Triangle begins:
  [1] 0 1;
  [2] 0 0 1 1 2 1;
  [3] 0 0 0 1 0 0 1 1 2 1 1 1 2 2 3 2 1 2 1 1;
  ...
The strings corresponding to row 2, in reverse lexicographical order, are:
  "))((" (0 atoms),
  ")()(" (0 atoms),
  ")(()" (1 atom),
  "())(" (1 atom),
  "()()" (2 atoms) and
  "(())" (1 atom).

Mathematica

strings[n_] := Permutations[PadLeft[Table[1, n], 2*n, -1]];
Array[Map[SequenceCount[Accumulate[#], {1, 0}] &, strings[#]] &, 5]

Crossrefs

Cf. A000346 (row sums), A000984 (row lengths), A362030 and A368804 (binary words).

Cf. A368751 (co-atoms), A368752 (all atoms), A368753 (defects).

Sequence in context: A085977 A288424 A127325 * A259660 A119842 A015624

Adjacent sequences: A368747 A368748 A368749 * A368751 A368752 A368753

Keyword

nonn,tabf

Author

Paolo Xausa, Jan 05 2024

Status

approved