An explicit formula for the number of permutations with a given number of alternating runs

摘要

Let R(n, k) denote the number of permutations of {1, 2,...,n} with k alternating runs. In this paper we present an explicit formula for the numbers R(n, k).