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

Author

Paolo Xausa, Jan 05 2024

Keywords

• nonn
• tabf

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

Examples

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

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

Crossrefs

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

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

Programs

Mathematica

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

Formula

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