MathDB
Problems
Contests
National and Regional Contests
India Contests
India National Olympiad
2007 India National Olympiad
4
4
Part of
2007 India National Olympiad
Problems
(1)
How many permutations exist with exactly two inversions?
Source: INMO 2007 Question 4
11/2/2009
Let
σ
=
(
a
1
,
a
2
,
⋯
,
a
n
)
\sigma = (a_1, a_2, \cdots , a_n)
σ
=
(
a
1
,
a
2
,
⋯
,
a
n
)
be permutation of
(
1
,
2
,
⋯
,
n
)
(1, 2 ,\cdots, n)
(
1
,
2
,
⋯
,
n
)
. A pair
(
a
i
,
a
j
)
(a_i, a_j)
(
a
i
,
a
j
)
is said to correspond to an inversion of
σ
\sigma
σ
if
i
<
j
i<j
i
<
j
but
a
i
>
a
j
a_i>a_j
a
i
>
a
j
. How many permutations of
(
1
,
2
,
⋯
,
n
)
(1,2,\cdots,n)
(
1
,
2
,
⋯
,
n
)
,
n
≥
3
n \ge 3
n
≥
3
, have exactly two inversions?For example, In the permutation
(
2
,
4
,
5
,
3
,
1
)
(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)
(
2
,
1
)
,
(
4
,
3
)
,
(
4
,
1
)
,
(
5
,
3
)
,
(
5
,
1
)
,
(
3
,
1
)
.
combinatorics