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

Author

Paolo Xausa, Jan 05 2024

Keywords

• nonn
• tabf

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.

Examples

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

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.

Crossrefs

Cf. A000108.

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

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

Programs

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]