A partition of Catalan permuted sequences with applications (Q1094423)

Sequences of overlapping line segments are investigated as the models of paired events. The ordering of beginnings and ends of events may be described by the Catalan permuted sequences. By \(X_ i\) is denoted the beginning of i-th event and by \(y_ i\) its end. The order of \(X_ i\) in the sequence of border points of events is denoted \(r(X_ i)\) and order of \(y_ i\) is \(r(y_ i)\). For every of \(\binom{n}{2}\) of pairs of events is defined the value \(\lambda_{ij}\) as \[ \lambda_{ij} = \begin{cases} 0 &\text{if \(r(y_ i)<r(X_ j)\)} \\ 1 &\text{if \(r(X_ j)<r(y_ i)<r(y_ j)\)} \\ 2 &\text{if \(r(y_ j)<r(y_ i)\)} \end{cases} \] Any sequence of paired events defines a vector \((v_ 0,v_ 1,v_ 2)\) of numbers of pairs with \(\lambda_{ij}=0,1,2\), respectively. Vectors \((v_ 0,v_ 1,v_ 2)\) create a partition of the set of all sequences of events. The recursion formulae for the cardinality of these classes are derived.