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.

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,3

Comments

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.

References

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.

Links

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.

Example

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

Mathematica

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

Crossrefs

Cf. A000108.

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

Cf. A368750 (atoms), A368751 (co-atoms), A368752 (all atoms).

Sequence in context: A128521 A090477 A349802 * A345907 A293019 A376590

Adjacent sequences: A368750 A368751 A368752 * A368754 A368755 A368756

Keyword

nonn,tabf

Author

Paolo Xausa, Jan 05 2024

Status

approved