Exact Formulas for Multitype Run Statistics in a Random Ordering (Q5285938)

The authors derive exact formulas as follows: Result 1: Given \(n_ 1\) \(A\)'s and \(n_ 2=N-n_ 1\) \(B\)'s, the number of orderings with at least \(s\) separate runs of at least \(r\) \(A\)'s. Result 2: Given \(n_ 1\) \(A\)'s and \(n_ 2=N-n_ 1\) \(B\)'s, the number of orderings with at least \(s_ i\) separate runs of at least \(r_ i\) \(A\)'s for \(i=1,2,\dots,q\), where \(\vec s=(s_ 1,s_ 2,\dots,s_ q)\) and \(\vec r=(r_ 1,r_ 2,\dots,r_ q)\) with \(r_ 1> r_ 2>\cdots> r_ q\). Result 3: Given \(n_ i\) of each letter type \(L_ i\), the number of orderings that have at least \(s_{ij}\) separate runs of at least \(r_{ij}\) letters \(L_ i\), for \(i=1,2,\dots,p\) and \(j=1,2,\dots,q_ i\), where \(s_{ij}\) and \(r_{ij}\) are positive integers and \(r_{i1}> r_{i2}>\cdots >r_{iq_ i}\). The formulas are not in ``closed form'', and involve multiple sums and products. From the authors' abstract: These results are particularly useful for short sequences and other cases where asymptotic formulas cannot be trusted. Computer programs to evaluate these formulas are available.