Problem

Source: III International Festival of Young Mathematicians Sozopol 2012, Theme for 10-12 grade

Tags: combinatorics, Fibonacci sequence



Let M={1,2,...,n}. Prove that the number of pairs (A,a), where AM and a is a permutation of M, for which a(A)A=, is equal to n!.Fn+1, where Fn+1 is the n+1 member of the Fibonacci sequence.