MathDB
How many permutations exist with exactly two inversions?

Source: INMO 2007 Question 4

November 2, 2009
combinatorics

Problem Statement

Let σ=(a1,a2,⋯ ,an) \sigma = (a_1, a_2, \cdots , a_n) be permutation of (1,2,⋯ ,n) (1, 2 ,\cdots, n). A pair (ai,aj) (a_i, a_j) is said to correspond to an inversion of σ\sigma if i<j i<j but ai>aj a_i>a_j. How many permutations of (1,2,⋯ ,n) (1,2,\cdots,n), n≥3 n \ge 3, have exactly two inversions?
For example, In the permutation (2,4,5,3,1)(2,4,5,3,1), there are 6 inversions corresponding to the pairs (2,1),(4,3),(4,1),(5,3),(5,1),(3,1) (2,1),(4,3),(4,1),(5,3),(5,1),(3,1).
Back to ProblemsView on AoPS