Count of permutations of size 2N with at least N increasing elements – GeeksforGeeks

Given N, the task is to determine the count of all permutations of size 2N having at least N-increasing elements. An element p_i of a permutation P is called increasing if p_i < p_i+1. For example: 

• Permutation [1, 2, 3, 4] will count because the number of such i that p_i < p_i+1 equals 3 (i = 1, i = 2, i = 3). 
• Permutation [3, 2, 1, 4] won’t count, because the number of such i that p_i < p_i+1 equals 1 (i = 3). 

Examples:

Input: 1
Output: 1
Explanation: N = 1, there is only one permutation of size 2 that have at least 1 increasing elements: [1, 2].
In permutation [1, 2], p₁ < p₂ , and there is one, i=1, that satisfy the condition. Since, 1 ≥ N this permutation should be counted. 
In permutation [2, 1], p₁ > p₂ , and there is no increasing element since, 0<N, this permutation should not be counted.

Input: 2
Output: 12
Explanation: N = 2, there are 12 permutations of size 4 that have at least 2 increasing elements. Following are those permutations: [1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [2, 1, 3, 4], [2, 3, 1, 4], [2, 3, 4, 1], [2, 4, 1, 3], [3, 1, 2, 4], [3, 4, 1, 2], [4, 1, 2, 3].

Naive Approach: The basic way to solve the problem is as follows:

Generate all permutations of size 2N and for each permutation check if it is the required permutation by counting the number of increasing elements in it.

Time Complexity: O(N! * N),  

• Generating all the permutations of size 2N will take O(N!) time,  
• Counting the number of increasing elements in each permutation will take O(N) time 
• Thus, overall the naive solution will take O(N! * N) time.

Auxiliary Space: O(N)

Efficient Approach: The problem can be solved based on the following observation:

Assume a permutation P and let k be the total count of increasing elements in P. Assume a permutation Q obtained by reversing permutation P and let l be the total count of increasing elements in Q. Mathematically: 

if P = [p₁, p₂, p₃, . . ., p_2N], then Q = [p_2N, p_2N-1, p_2N-2, . . ., p₂, p₁]. 
k = ∑[p_i−1 < p_i] ∀ 2⩽ i ⩽ 2N

It can be observed that:
The number of increasing elements in Q = 2N – 1 – Number of increasing elements in P = l = 2N – 1 – k

This means, that for every permutation P having the number of increasing elements k < N, there exists a corresponding permutation Q, obtained by reversing P that has the number of increasing elements l ≥ N.

From the above observation, it can be concluded out of all the permutations of size 2N, exactly half of them will have the count of increasing elements l >= N. Therefore, the count of required permutations = total permutations / 2 = (2N)!/2.

Below is the implementation of the above approach:

Time Complexity: O(N), as we only need to calculate (2N)! which can be calculated in O(N) time
Auxiliary Space: O(1)