MathDB
A counting problem

Source: Iranian National Olympiad (3rd Round) 2008

August 31, 2008
combinatorics proposedcombinatorics

Problem Statement

Prove that the number of pairs (α,S) \left(\alpha,S\right) of a permutation α \alpha of {1,2,…,n} \{1,2,\dots,n\} and a subset S S of {1,2,…,n} \{1,2,\dots,n\} such that ∀x∈S:α(x)∉S \forall x\in S: \alpha(x)\not\in S is equal to n!F_{n \plus{} 1} in which Fn F_n is the Fibonacci sequence such that F_1 \equal{} F_2 \equal{} 1
Back to ProblemsView on AoPS