Counting permutations by cyclic peaks and valleys. (English) Zbl 1324.05002
Summary: In this paper, we study the generating functions for the number of permutations having a prescribed number of cyclic peaks or valleys. We derive closed form expressions for these functions by use of various algebraic methods. When restricted to the set of derangements (i.e., fixed point free permutations), the evaluation at \(-1\) of the generating function for the number of cyclic valleys gives the Pell number. We provide a bijective proof of this result, which can be extended to the entire symmetric group.
Online Encyclopedia of Integer Sequences:
Pell numbers: a(0) = 0, a(1) = 1; for n > 1, a(n) = 2*a(n-1) + a(n-2).Triangle read by rows: T(n,k) (n >= 1, 0 <= k <= ceiling(n/2)-1) = number of permutations of [n] with k peaks.
Triangle read by rows: T(n,k) is the number of permutations of [n] with k increasing runs of length at least 2.
Triangle read by rows: T(n,k) is the number of permutations of [n] with k alternating runs (n>=2, k>=1).
