[go: up one dir, main page]
login
The OEIS is supported by the many generous donors to the OEIS Foundation.
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
Search: a370885 -id:a370885
Displaying 1-3 of 3 results found.
page 1
     Sort: relevance | references | number | modified | created      Format: long | short | data
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.
+10
5
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, 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, 3, 3, 3, 4, 3, 2, 2, 2, 2, 2, 2, 4, 3, 2, 2, 2, 1, 1, 1, 2
(list; graph; refs; listen; history; text; internal format)
OFFSET
0,4
COMMENTS
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).
Exactly p right parentheses and q-p (cf. A370884) left parentheses are unmatched.
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).
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) - A370884(n,k).
EXAMPLE
Triangle begins:
[0] 0;
[1] 1 0;
[2] 2 1 0 0;
[3] 3 2 1 1 1 0 0 0;
[4] 4 3 2 2 2 1 1 1 2 1 0 0 0 0 0 0;
...
The strings corresponding to row 2, in reverse lexicographical order, are:
"))" (2 unmatched right parentheses),
")(" (1 unmatched right parenthesis),
"()" (0 unmatched right parentheses), and
"((" (0 unmatched right parentheses).
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 "(".
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).
.
R R R R R R L L L
) ()() ) (()) ) ) ) ) ( (()) ( (()(()())) (
| \__/ \__/ | | | | \__/ \________/ |
E * * E E E E * * E
.
MATHEMATICA
countR[s_] := StringCount[s, "0"] - StringCount[StringJoin[StringCases[s, RegularExpression["1(?R)*+0"]]], "0"];
Array[Map[countR, IntegerString[Range[0, 2^#-1], 2, #]] &, 7, 0]
CROSSREFS
Cf. A367508, A370884 (p-q), A370885 (q), A370942 (nonempty nested substrings).
Cf. A000079 (row lengths), A063171.
Apparently, row sums are given by A189391.
KEYWORD
nonn,tabf
AUTHOR
Paolo Xausa, Mar 06 2024
STATUS
approved
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.
+10
4
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
(list; graph; refs; listen; history; text; internal format)
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.
KEYWORD
nonn,tabf
AUTHOR
Paolo Xausa, Mar 06 2024
STATUS
approved
A370942
Irregular triangle read by rows: T(n,k) is the number of nonempty, longest nonoverlapping properly nested substrings into which the k-th string of parentheses of length n can be split into, where strings within a row are in reverse lexicographical order.
+10
3
0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 2, 1, 1, 1, 2, 1, 1
(list; graph; refs; listen; history; text; internal format)
OFFSET
0,50
COMMENTS
This sequence counts the nonempty s_i substrings described in A370883.
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).
EXAMPLE
Triangle begins:
[0] 0;
[1] 0 0;
[2] 0 0 1 0;
[3] 0 0 1 0 1 1 1 0;
[4] 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0;
...
T(2,3) is 1 because the corresponding string, "()", coincides with a properly nested string.
T(5,19) is 2 because the corresponding string, "())()", can be split into "()", ")" and "()": there are two copies of the nested substring "()".
T(7,99) is 2 because the corresponding string, "(()))()", can be split into the substrings "(())", ")" and "()", two of which are properly nested.
MATHEMATICA
countS[s_] := StringCount[s, RegularExpression["(1(?R)*+0)++"]];
Array[countS[IntegerString[Range[0, 2^#-1], 2, #]] &, 7, 0]
CROSSREFS
Cf. A370883, A370884, A370885.
Cf. A000079 (row lengths), A063171, A370943 (row sums).
KEYWORD
nonn,tabf
AUTHOR
Paolo Xausa, Mar 06 2024
STATUS
approved
page 1

Search completed in 0.006 seconds

Lookup Welcome Wiki Register Music Plot 2 Demos Index WebCam Contribute Format Style Sheet Transforms Superseeker Recents
The OEIS Community
Maintained by The OEIS Foundation Inc.
Last modified October 5 01:23 EDT 2024. Contains 376527 sequences.
License Agreements, Terms of Use, Privacy Policy