A368751 -id:A368751 - cp's OEIS frontend

A368804 Irregular triangle read by rows: T(n,k) is the k-th balanced binary word of length 2*n, where words within a row are in lexicographical order (with leading zeros removed and interpreted as decimal numbers).

1, 10, 11, 101, 110, 1001, 1010, 1100, 111, 1011, 1101, 1110, 10011, 10101, 10110, 11001, 11010, 11100, 100011, 100101, 100110, 101001, 101010, 101100, 110001, 110010, 110100, 111000, 1111, 10111, 11011, 11101, 11110, 100111, 101011, 101101, 101110, 110011, 110101, 110110

Offset: 1

Paolo Xausa, Jan 06 2024

A balanced binary word is composed of the same number of zeros and ones.

This is triangle A362030 with terms converted to binary and interpreted as decimal numbers.

			Triangle begins (where terms in row n are padded with zeros on the left to form a 2*n word):
  [1] 01 10;
  [2] 0011 0101 0110 1001 1010 1100;
  [3] 000111 001011 001101 001110 010011 010101 010110 011001 011010 011100 ... ;
  ...

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

Cf. A014486, A063171, A362030.

Cf. A368750, A368751, A368752, A368753.

words[n_]:=Permutations[PadLeft[PadLeft[{},n,1],2n]];
Array[Map[FromDigits,words[#]]&,4]

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.

Original entry on oeis.org

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

Paolo Xausa, Jan 05 2024

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

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

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.

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

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

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

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

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

A368752 Irregular triangle read by rows: T(n,k) is the number of atoms + co-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.

Original entry on oeis.org

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

Offset: 1

Paolo Xausa, Jan 05 2024

See A368750 for the definition of balanced strings and atoms/co-atoms.

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

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.

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

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

Cf. A368750 (atoms), A368751 (co-atoms), A368753 (defects).

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

T(n,k) = A368750(n,k) + A368751(n,k).

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

Original entry on oeis.org

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

Offset: 1

Paolo Xausa, Jan 05 2024

See A368750 for the definition of balanced strings and atoms/co-atoms.
The defect is half the length of co-atoms or, equivalently, the number of indices where the i-th right parenthesis precedes the i-th left parenthesis (see Knuth, 2011).
Knuth reports a result by MacMahon (1909) and Chung and Feller (1949): exactly A000108(n) balanced strings of length 2*n have defect d, for 0 <= d <= n.

			Triangle begins:
  [1] 1 0;
  [2] 2 2 1 1 0 0;
  [3] 3 3 3 2 3 3 2 2 1 1 2 2 1 1 0 0 1 0 0 0;
  ...
The strings corresponding to row 2, in reverse lexicographical order, are:
  "))((" (defect 2),
  ")()(" (defect 2),
  ")(()" (defect 1),
  "())(" (defect 1),
  "()()" (defect 0) and
  "(())" (defect 0).
For the string "())((())))(()(", for example, the defect is calculated as follows:
.
  atom
  |   co-atom
  |   |   atom  co-atom
  |   |   |     |     co-atom
  |   |   |     |     |
  ()  )(  (())  ))((  )(
      *         **    *
.
  defect = length of co-atoms / 2 = 8 / 2 = 4 = number of indices where the i-th right parenthesis precedes the i-th left parenthesis (marked with asterisks).

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

Paolo Xausa, Table of n, a(n) for n = 1..17576 (rows 1..8 of the triangle, flattened).
K. L. Chung and W. Feller, On Fluctuations in Coin-Tossing, PNAS, vol. 35, no. 10, 1949, pp. 605-608.
J. L. Hodges, Galton's Rank-Order Test, Biometrika, vol. 42, no. 1/2, 1955, pp. 261-262.
P. A. MacMahon, Memoir on the Theory of the Partitions of Numbers. Part IV: On the Probability That the Successful Candidate at an Election by Ballot May Never at Any Time Have Fewer Votes Than the One Who Is Unsuccessful; on a Generalization of This Question; and on Its Connexion with Other Questions of Partition, Permutation, and Combination, Philosophical Transactions of the Royal Society of London, Series A, Containing Papers of a Mathematical or Physical Character, vol. 209, 1909, pp. 153-175.

Cf. A000108.
Cf. A000984 (row lengths), A002457 (row sums), A362030 and A368804 (binary words).
Cf. A368750 (atoms), A368751 (co-atoms), A368752 (all atoms).

strings[n_]:=Permutations[PadLeft[PadLeft[{},n,1],2n]];
defect[s_]:=Count[Position[s,1]-Position[s,0],_?Positive,{2}];
Array[Map[defect,strings[#]]&,5]

cp's OEIS Frontend

A368804 Irregular triangle read by rows: T(n,k) is the k-th balanced binary word of length 2*n, where words within a row are in lexicographical order (with leading zeros removed and interpreted as decimal numbers).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A368752 Irregular triangle read by rows: T(n,k) is the number of atoms + co-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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica