Distribution of increasing \(\ell\)-sequences in a random permutation (Q5936986)

The purpose of the paper is to examine the distribution of the number \(k\) of increasing \(\ell\)-sequences in a random permutation of \(\{1,\dots, n\}\). It should be useful to recall that an increasing \(\ell\)-sequence represents a sequence of \(\ell\) consecutive integers in increasing order, and that for nonnegative integers \(n\) and \(m\), a composition of \(n\) into exactly \(m\) parts is an ordered collection of positive integers \(x_1,\dots, x_m\) such that \(x_1+ x_2+\cdots+ x_m= n\). The author succeeds in determining a new solution for the distribution of the numbers \(k\) of increasing \(\ell\)-sequences in a random permutation, the solution being based on the composition of \(n\) and requiring, at most, \(k(n-k-\ell)\) summands. Relying on the theory of composition of integers, the obtained solution easily yields the already existing results for the special case \(\ell= 2\), and provides an alternate form for the case \(\ell=3\). In addition to the exact form, a closed form for the expected number of increasing \(\ell\)-sequences in a random permutation is determined. An algorithm for computing the exact distribution, using the partitions of \(n\), is presented and proved to be easy to implement and to be efficient for small values of \(n\). Three applications support the proposed approach: a non-parametric test for independence, a non-parametric test for independence in paired samples, and a simple application in graph theory.