MathDB

4

Part of 1982 Canada National Olympiad

Problems(1)

Number of permutations [Canada MO 1982 - P4]

Source:

9/30/2011
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.
countingderangement