The number of permutations ofwith k descents is equal to the number with k drops, i.e.,
![]()
A descent ofmust lie inside a cycle of
since our conventions guarantee that the last element in a cycle is followed by a larger integer. By the meaning of the cycle decomposition
(namely, that elements within cycles are mapped to the next element in the cycle) we see that a descent of
corresponds to a drop of
. Conversely, a drop in
must occur within a cycle (i.e., not in passing from the last element of a cycle to the first) and corresponds to a descent in
. Thus the number of permutations with k descents is equal to the number
with k drops.