A368804 -id:A368804 - cp's OEIS frontend

A362030 Irregular triangle read by rows where row n contains the balanced binary words of length 2n interpreted as binary numbers.

1, 2, 3, 5, 6, 9, 10, 12, 7, 11, 13, 14, 19, 21, 22, 25, 26, 28, 35, 37, 38, 41, 42, 44, 49, 50, 52, 56, 15, 23, 27, 29, 30, 39, 43, 45, 46, 51, 53, 54, 57, 58, 60, 71, 75, 77, 78, 83, 85, 86, 89, 90, 92, 99, 101, 102, 105, 106, 108, 113, 114, 116, 120, 135

Offset: 1

Louis Conover, Apr 05 2023

Within a row, strings are ordered lexicographically, which means the resulting values are ordered numerically.
This is from an idea of David Lovler, which he calls "zigzags". It is a rearrangement of A072601. A072603 lists all the numbers that are not in this sequence. A000984 gives the number of coin flip sequences of length 2,4,6, etc.
Not a permutation of the integers. E.g. 8 never occurs. When there are more 0's than 1's, adding 0's doesn't bring it to balance. - Kevin Ryde, Aug 31 2023

			The first few terms written as binary words with leading 0's: 01, 10, 0011, 0101, 0110, 1001, 1010, 1100, 000111, 001011, 001101, 001110, ... (cf. A368804).
Triangle T(n,k) begins:
   1,  2;
   3,  5,  6,  9, 10, 12;
   7, 11, 13, 14, 19, 21, 22, 25, 26, 28, 35, 37, 38, ...;
  15, 23, 27, 29, 30, 39, 43, 45, 46, 51, 53, 54, 57, ...;
  ...

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

Columns k=1-2 give: A000225, A083329.
Row sums give A131568.
Main diagonal gives A036563(n+1).
Cf. A000984 (row lengths), A072601, A072603, A368804 (binary).

T:= n-> sort(map(Bits[Join], combinat[permute]([0$n, 1$n])))[]:
seq(T(n), n=1..4);  # Alois P. Heinz, Apr 13 2023

T[n_] := Sort[FromDigits[#, 2] & /@ Permutations[Join[ConstantArray[0, n], ConstantArray[1, n]]]]; Flatten[Table[T[n], {n, 1, 4}]][[1 ;; 64]] (* Robert P. P. McKone, Aug 29 2023 *)

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

A368751 Irregular triangle read by rows: T(n,k) is the number of 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, 0, 1, 2, 1, 1, 0, 0, 1, 1, 2, 1, 2, 3, 2, 2, 1, 1, 1, 2, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 3, 2, 2, 1, 1, 2, 2, 3, 2, 3, 4, 3, 3, 2, 2, 2, 3, 2, 2, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 2, 3, 2, 2, 1, 1, 1, 2, 1, 1, 0, 0, 1, 0, 0, 0, 1, 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.

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

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. A368750 (atoms), A368752 (all atoms), A368753 (defects).

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

T(n,k) = A368752(n,k) - A368750(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

A362030 Irregular triangle read by rows where row n contains the balanced binary words of length 2n interpreted as binary numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

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

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

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