MathDB
number of permutations

Source: 41-st Vietnamese Mathematical Olympiad 2003

March 10, 2007
combinatorics proposedcombinatorics

Problem Statement

Let SnS_{n} be the number of permutations (a1,a2,...,an)(a_{1}, a_{2}, ... , a_{n}) of (1,2,...,n)(1, 2, ... , n) such that 1≤∣ak−k∣≤21 \leq |a_{k}-k | \leq 2 for all kk. Show that 74Sn−1<Sn<2Sn−1\frac{7}{4}S_{n-1}< S_{n}< 2 S_{n-1} for n>6.n > 6.
Back to ProblemsView on AoPS