(Received April 14, 1994; revised November 7, 1994)
Abstract. Traditionally the distributions of the number of patterns and successions in a random permutation of n integers 1, 2, ..., and n were studied by combinatorial analysis. In this short article, a simple way based on finite Markov chain imbedding technique is used to obtain the exact distribution of successions on a permutation. This approach also gives a direct proof that the limiting distribution of successions is a Poisson distribution with parameter lambda = 1. Furthermore, a direct application of the main result, it also yields the waiting time distribution of a succession.
Key words and phrases: Permutation, succession, Markov chain imbedding, transition probabilities, Poisson convergence, waiting time.
Source ( TeX , DVI , PS )