Counting Successions in Permutations
Let π = (π(1), π(2),...,π(n)) be a permutation of the arbitrary n‐set S of postive integers. A succession in π is any pair π(i), π(i + 1) with π(i + 1) = π(i) + 1, i = 1,2..., n −1. We show that the number of permutations of S which have precisely k successions depends only upon n, k and b, where b is the number of maximal disjoint intervals in the set [n + m]\S, and n + m is the largest element in S. We derive a linear recurrence relation for this number, which we call the succession number σ(n, k; b), as well as an explicit formula in terms of derangement numbers. The linear recurrence is used to derive the generating function for succession numbers. is also derived by formal power series methods from a well‐known generating function for succession in general integer sequences.
No Supplementary Data
No Article Media
Document Type: Research Article
Affiliations: University of Toronto
Publication date: July 1, 1979