login
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.
5
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.
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
KEYWORD
nonn,tabf
AUTHOR
Paolo Xausa, Jan 05 2024
STATUS
approved