Problem Challenge by Josh Zucker

A permutation of n elements is a rearrangement of those elements. For instance, BDAC is a rearrangement of ABCD. Another way to represent that is that the first element goes to the third spot, the third goes to the fourth, the fourth goes to second, and the second goes back to the first. We could write that as [1342]. This is quite different from a rearrangement like BADC, in which the first and second swap and the third and fourth swap, which we could write as [12][34]. The first example has one cycle of all four elements, and the second example has two cycles of two elements each. There are also cycles of just one element, as in ADBC, which we could also write as [1][234]. A one-element cycle is also called a fixed point of the permutation.

• How many permutations of four elements have no fixed points?
• How many permutations of n elements have no fixed points?
• How many permutations of n elements have exactly one fixed point?
• How many permutations of 5 elements have exactly 2 cycles?
• On average, how many cycles does a permutation of n elements have?
  (Begin by determining this value for n = 1, 2, 3, and so on).