Problem

Source: Iranian National Olympiad (3rd Round) 2008

Tags: combinatorics proposed, combinatorics



Prove that the number permutations $ \alpha$ of $ \{1,2,\dots,n\}$ s.t. there does not exist $ i<j<n$ s.t. $ \alpha(i)<\alpha(j+1)<\alpha(j)$ is equal to the number of partitions of that set.