Distribution of increasing -sequences in a random permutation
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.
- The distribution of increasing l-sequences in random permutations: A Markov chain approach
- The distribution of increasing 2-sequences in random permutations of arbitrary multi-sets.
- The distribution of the length of the longest increasing subsequence in random permutations of arbitrary multi-sets
- On the distribution of the length of the longest increasing subsequence in a random permutation
- scientific article; zbMATH DE number 1515819
- The distribution of increasing l-sequences in random permutations: A Markov chain approach
- The distribution of increasing 2-sequences in random permutations of arbitrary multi-sets.
- On the distribution of the number of occurrences of an order-preserving pattern of length three in a random permutation
- Law of large numbers for increasing subsequences of random permutations
- The orders of equidistribution of subsequences of some asymptotically random sequences
- Distributions of runs of consecutive ascending integers with unequal probabilities
- The numbers of ascending segments in a random permutation and in the inverse to it are asymptotically independent
- Computing the distribution of a combinatorial statistics defined on permutations of a given multiset
- Distributions of successions of arbitrary multisets
This page was built for publication: Distribution of increasing \(\ell\)-sequences in a random permutation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5936986)
