cp's OEIS Frontend

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

%I A370883 #44 Mar 13 2024 04:42:17
%S A370883 0,1,0,2,1,0,0,3,2,1,1,1,0,0,0,4,3,2,2,2,1,1,1,2,1,0,0,0,0,0,0,5,4,3,
%T A370883 3,3,2,2,2,3,2,1,1,1,1,1,1,3,2,1,1,1,0,0,0,1,0,0,0,0,0,0,0,6,5,4,4,4,
%U A370883 3,3,3,4,3,2,2,2,2,2,2,4,3,2,2,2,1,1,1,2
%N A370883 Irregular triangle read by rows: T(n,k) is the number of unmatched right parentheses in the k-th string of parentheses of length n, where strings within a row are in reverse lexicographical order.
%C A370883 Using Knuth's (2011) notation, any string of parentheses can be uniquely written as s_0")"...s_p-1")"s_p"("s_p+1..."("s_q, with 0 <= p <= q, where the substrings s_i are the longest possible properly nested substrings (possibly empty). Examples of properly nested substrings are "()", "()()" and "(())()" (cf. A063171).
%C A370883 Exactly p right parentheses and q-p (cf. A370884) left parentheses are unmatched.
%C A370883 Knuth observes that the above string is part of a chain of length q+1: s_0")"...s_q-1")"s_q, s_0")"...s_q-2")"s_q-1"("s_q, ... , s_0"("s_1..."("s_q, where the q unmatched right parentheses in the first element of the chain are turned, one by one, into unmatched left parentheses in the next elements of the chain. By encoding "(" and ")" with 1 and 0, respectively, such a chain corresponds to a row in the Christmas tree pattern (cf. A367508).
%D A370883 Donald E. Knuth, The Art of Computer Programming, Vol. 4A: Combinatorial Algorithms, Part 1, Addison-Wesley, 2011, Section 7.2.1.6, p. 459.
%H A370883 Paolo Xausa, <a href="/A370883/b370883.txt">Table of n, a(n) for n = 0..16382</a> (rows 0..13 of the triangle, flattened).
%F A370883 T(n,k) = A370885(n,k) - A370884(n,k).
%e A370883 Triangle begins:
%e A370883   [0] 0;
%e A370883   [1] 1 0;
%e A370883   [2] 2 1 0 0;
%e A370883   [3] 3 2 1 1 1 0 0 0;
%e A370883   [4] 4 3 2 2 2 1 1 1 2 1 0 0 0 0 0 0;
%e A370883   ...
%e A370883 The strings corresponding to row 2, in reverse lexicographical order, are:
%e A370883   "))" (2 unmatched right parentheses),
%e A370883   ")(" (1 unmatched right parenthesis),
%e A370883   "()" (0 unmatched right parentheses), and
%e A370883   "((" (0 unmatched right parentheses).
%e A370883 The k-th string in row n corresponds to the binary expansion of k-1, padded with zeros on the left as to make it n digits long, with zeros replaced by ")" and ones replaced by "(".
%e A370883 In the following string the position of the unmatched p = 6 right parentheses is denoted by R, the position of the unmatched q-p = 3 left parentheses is denoted by L, and the q+1 = 10 properly nested substrings s_0..s_9 are marked either with E (empty) or * (nonempty).
%e A370883 .
%e A370883    R      R      R R R R L      L            L
%e A370883    ) ()() ) (()) ) ) ) ) ( (()) ( (()(()())) (
%e A370883   |  \__/   \__/  | | | |  \__/   \________/  |
%e A370883   E   *      *    E E E E   *         *       E
%e A370883 .
%t A370883 countR[s_] := StringCount[s, "0"] - StringCount[StringJoin[StringCases[s, RegularExpression["1(?R)*+0"]]], "0"];
%t A370883 Array[Map[countR, IntegerString[Range[0, 2^#-1], 2, #]] &, 7, 0]
%Y A370883 Cf. A367508, A370884 (p-q), A370885 (q), A370942 (nonempty nested substrings).
%Y A370883 Cf. A000079 (row lengths), A063171.
%Y A370883 Apparently, row sums are given by A189391.
%K A370883 nonn,tabf
%O A370883 0,4
%A A370883 _Paolo Xausa_, Mar 06 2024