MathDB
Number of permutations [Canada MO 1982 - P4]

Source:

September 30, 2011
countingderangement

Problem Statement

Let pp be a permutation of the set Sn={1,2,…,n}S_n = \{1, 2, \dots, n\}. An element j∈Snj \in S_n is called a fixed point of pp if p(j)=jp(j) = j. Let fnf_n be the number of permutations having no fixed points, and gng_n be the number with exactly one fixed point. Show that ∣fn−gn∣=1|f_n - g_n| = 1.
Back to ProblemsView on AoPS