# Partitions on Integer Permutations

Let $S_n$ be the set of all permutations of integers from $1$ to $n$. Let $P_1$ and $P_2$ be two partitions defined on $S_n$ as follows.

$P_1$ is the set of all those permutations which have even number of cycles. $P_2$ is the set of all those permutations which have odd number of cycles. The sets $P_1$ and $P_2$ have a lexicographic ordering imposed on them.

Given a permutation $P$

1. Tell which partition it belongs to
2. What is the lexicographic rank($1$ based indexing) of this permutation in that partition. If this rank is $K$, you have to specify the number $K$ mod $M$ where $M = 1000000007 (1e9 + 7)$

Here $N$ can be as large as $10^5$

My approach: Calculate the number of cycles in P using a simple DFS technique on my computer and decide which partition it belongs to. For calculating rank I first calculate its rank in the set $S_n$ Let that rank be $K_1$($1$ based indexing) then the actual rank is coming out to be floor($\frac{K_1+1}{2}$). I am having trouble applying modular arithmetic on this expression. Is there any other way to solve this problem?

Note: By "cycle" I mean when the permutation is represented as a graph, the number of components or disjoint forests formed.

• @AndrásSalamon I have corrected the question – lassaendie Oct 5 '15 at 11:41