cp's OEIS Frontend

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.

%I A368750 #33 Mar 06 2024 17:48:00
%S A368750 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,
%T A368750 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,
%U A368750 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
%N 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.
%C A368750 A balanced string of parentheses is composed of the same number of left and right parentheses. E.g., "(())()" and "))(()(" are balanced, while "((()((()" is not.
%C A368750 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.
%C A368750 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.
%C A368750 For example, the string ")(()()(())))((" can be split into ")(" (co-atom), "()" (atom), "()" (atom), "(())" (atom) and "))((" (co-atom).
%C A368750 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).
%D A368750 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.
%H A368750 Paolo Xausa, <a href="/A368750/b368750.txt">Table of n, a(n) for n = 1..17576</a> (rows 1..8 of the triangle, flattened).
%F A368750 T(n,k) = A368752(n,k) - A368751(n,k).
%e A368750 Triangle begins:
%e A368750   [1] 0 1;
%e A368750   [2] 0 0 1 1 2 1;
%e A368750   [3] 0 0 0 1 0 0 1 1 2 1 1 1 2 2 3 2 1 2 1 1;
%e A368750   ...
%e A368750 The strings corresponding to row 2, in reverse lexicographical order, are:
%e A368750   "))((" (0 atoms),
%e A368750   ")()(" (0 atoms),
%e A368750   ")(()" (1 atom),
%e A368750   "())(" (1 atom),
%e A368750   "()()" (2 atoms) and
%e A368750   "(())" (1 atom).
%t A368750 strings[n_] := Permutations[PadLeft[Table[1, n], 2*n, -1]];
%t A368750 Array[Map[SequenceCount[Accumulate[#], {1, 0}] &, strings[#]] &, 5]
%Y A368750 Cf. A000346 (row sums), A000984 (row lengths), A362030 and A368804 (binary words).
%Y A368750 Cf. A368751 (co-atoms), A368752 (all atoms), A368753 (defects).
%K A368750 nonn,tabf
%O A368750 1,7
%A A368750 _Paolo Xausa_, Jan 05 2024