cp's OEIS Frontend

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.

%I A368753 #33 Jan 09 2024 16:56:42
%S A368753 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,
%T A368753 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,
%U A368753 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
%N 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.
%C A368753 See A368750 for the definition of balanced strings and atoms/co-atoms.
%C A368753 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).
%C A368753 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.
%D A368753 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.
%H A368753 Paolo Xausa, <a href="/A368753/b368753.txt">Table of n, a(n) for n = 1..17576</a> (rows 1..8 of the triangle, flattened).
%H A368753 K. L. Chung and W. Feller, <a href="https://doi.org/10.1073/pnas.35.10.605">On Fluctuations in Coin-Tossing</a>, PNAS, vol. 35, no. 10, 1949, pp. 605-608.
%H A368753 J. L. Hodges, <a href="https://doi.org/10.2307/2333442">Galton's Rank-Order Test</a>, Biometrika, vol. 42, no. 1/2, 1955, pp. 261-262.
%H A368753 P. A. MacMahon, <a href="http://www.jstor.org/stable/91034">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</a>, Philosophical Transactions of the Royal Society of London, Series A, Containing Papers of a Mathematical or Physical Character, vol. 209, 1909, pp. 153-175.
%e A368753 Triangle begins:
%e A368753   [1] 1 0;
%e A368753   [2] 2 2 1 1 0 0;
%e A368753   [3] 3 3 3 2 3 3 2 2 1 1 2 2 1 1 0 0 1 0 0 0;
%e A368753   ...
%e A368753 The strings corresponding to row 2, in reverse lexicographical order, are:
%e A368753   "))((" (defect 2),
%e A368753   ")()(" (defect 2),
%e A368753   ")(()" (defect 1),
%e A368753   "())(" (defect 1),
%e A368753   "()()" (defect 0) and
%e A368753   "(())" (defect 0).
%e A368753 For the string "())((())))(()(", for example, the defect is calculated as follows:
%e A368753 .
%e A368753   atom
%e A368753   |   co-atom
%e A368753   |   |   atom  co-atom
%e A368753   |   |   |     |     co-atom
%e A368753   |   |   |     |     |
%e A368753   ()  )(  (())  ))((  )(
%e A368753       *         **    *
%e A368753 .
%e A368753   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).
%t A368753 strings[n_]:=Permutations[PadLeft[PadLeft[{},n,1],2n]];
%t A368753 defect[s_]:=Count[Position[s,1]-Position[s,0],_?Positive,{2}];
%t A368753 Array[Map[defect,strings[#]]&,5]
%Y A368753 Cf. A000108.
%Y A368753 Cf. A000984 (row lengths), A002457 (row sums), A362030 and A368804 (binary words).
%Y A368753 Cf. A368750 (atoms), A368751 (co-atoms), A368752 (all atoms).
%K A368753 nonn,tabf
%O A368753 1,3
%A A368753 _Paolo Xausa_, Jan 05 2024