Cuente las permutaciones que primero disminuyen y luego aumentan.

Dado un número entero N , calcule el número de permutaciones de A = [1, 2, …, N] que primero disminuyen y luego aumentan. 
Ejemplos:  

Entrada: N = 5 
Salida: 14
Las siguientes son las subsecuencias que primero disminuyen y luego aumentan: 
[2, 1, 3, 4, 5], [3, 1, 2, 4, 5], [4, 1 , 2, 3, 5], [5, 1, 2, 3, 4], 
[3, 2, 1, 4, 5], [4, 2, 1, 3, 5], [5, 2, 1 , 3, 4], [4, 3, 1, 2, 5], 
[5, 3, 1, 2, 4], [5, 4, 1, 2, 3], [5, 4, 3, 1 , 2], [5, 4, 2, 1, 3], 
[5, 3, 2, 1, 4], [4, 3, 2, 1, 5]
Entrada: N = 1 
Salida: 0  

Enfoque: Está claro que el punto en el que la secuencia pasa de ser creciente a decreciente está ocupado por el elemento más pequeño de la permutación, que es 1 . Además, la secuencia decreciente siempre va seguida de una secuencia creciente, lo que significa que el elemento más pequeño puede tener posiciones que van [2, …, N-1] . De lo contrario, dará como resultado una secuencia totalmente creciente o totalmente decreciente.
Por ejemplo, considere N = 5 y posición = 2 , es decir, el elemento más pequeño en la posición 2 de la secuencia. Cuente todas las secuencias posibles con Configuración = [_, 1, _, _, _].
Seleccione cualquier elemento 1 de los 4 elementos restantes (2, 3, 4, 5) para ocupar la posición 1. Por ejemplo, seleccionamos el elemento = 3. La configuración se parece a [3, 1, _, _, _]. Solo es posible 1 secuencia, es decir, [3, 1, 2, 4, 5]. Por lo tanto, para cada elemento seleccionado para ocupar la posición 1, es posible una secuencia. Con esta configuración, es posible un total de ⁴ permutaciones C _{1 .}
Ahora, considere la configuración = [_, _, 1, _, _].  
Se puede aplicar un enfoque similar seleccionando 2 elementos cualquiera de los 4 elementos restantes y para cada par de elementos, es posible una sola permutación válida. Por lo tanto, el número de permutaciones para esta configuración = ⁴ C ₂
La configuración final posible para N = 5 es[_, _, _, 1, _] 
Seleccione 3 cualquiera de los 4 elementos restantes y para cada triplete, se obtiene una permutación. Número de permutaciones, en este caso, = ⁴ C ₃
Cuenta final = ⁴ C ₁ + ⁴ C ₂ + ⁴ C ₃ para N = 5
Resultado generalizado para N:  

Count = N-1C1 + N-1C2 + ... + N-1CN-2 which simplifies to,
 N-1Ci = 2N-1 - 2 (from binomial theorem)

// C++ implementation of the above approach
#include <bits/stdc++.h>
 
#define ll long long
using namespace std;
 
const int mod = 1000000007;
 
// Function to compute a^n % mod
ll power(ll a, ll n)
{
 
    if (n == 0)
        return 1;
 
    ll p = power(a, n / 2) % mod;
    p = (p * p) % mod;
    if (n & 1)
        p = (p * a) % mod;
 
    return p;
}
 
// Function to count permutations that are
// first decreasing and then increasing
int countPermutations(int n)
{
 
    // For n = 1 return 0
    if (n == 1) {
        return 0;
    }
 
    // Calculate and return result
    return (power(2, n - 1) - 2) % mod;
}
 
// Driver code
int main()
{
    int n = 5;
    cout << countPermutations(n);
    return 0;
}

// Java implementation of the above approach
class GFG
{
 
static final int mod = 1000000007;
 
// Function to compute a^n % mod
static long power(long a, long n)
{
 
    if (n == 0)
        return 1;
 
    long p = power(a, n / 2) % mod;
    p = (p * p) % mod;
    if ((n & 1) == 1)
        p = (p * a) % mod;
 
    return p;
}
 
// Function to count permutations that are
// first decreasing and then increasing
static int countPermutations(int n)
{
 
    // For n = 1 return 0
    if (n == 1)
    {
        return 0;
    }
 
    // Calculate and return result
    return ((int)power(2, n - 1) - 2) % mod;
}
 
// Driver code
public static void main(String args[])
{
    int n = 5;
    System.out.println(countPermutations(n));
}
}
 
// This code is contributed by Arnab Kundu

# Python3 implementation of the above approach
mod = 1000000007
 
# Function to compute a^n % mod
def power(a, n):
    if(n == 0):
        return 1
 
    p = power(a, int(n / 2)) % mod;
    p = (p * p) % mod
    if (n & 1):
        p = (p * a) % mod
 
    return p
 
# Function to count permutations that are
# first decreasing and then increasing
def countPermutations(n):
     
    # For n = 1 return 0
    if (n == 1):
        return 0
 
    # Calculate and return result
    return (power(2, n - 1) - 2) % mod
 
# Driver code
if __name__ == '__main__':
    n = 5
    print(countPermutations(n))
     
# This code is contributed by
# Surendra_Gangwar

// C# implementation of the above approach
using System;
 
class GFG
{
     
static int mod = 1000000007;
 
// Function to compute a^n % mod
static long power(long a, long n)
{
 
    if (n == 0)
        return 1;
 
    long p = power(a, n / 2) % mod;
    p = (p * p) % mod;
    if ((n & 1) == 1)
        p = (p * a) % mod;
 
    return p;
}
 
// Function to count permutations that are
// first decreasing and then increasing
static int countPermutations(int n)
{
 
    // For n = 1 return 0
    if (n == 1)
    {
        return 0;
    }
 
    // Calculate and return result
    return ((int)power(2, n - 1) - 2) % mod;
}
 
// Driver code
static public void Main ()
{
    int n = 5;
    Console.WriteLine(countPermutations(n));
}
}
 
// This code is contributed by ajit..

<?php
// PHP implementation of the above approach
 
$mod = 1000000007;
 
// Function to compute a^n % mod
function power($a, $n)
{
    global $mod;
    if ($n == 0)
        return 1;
 
    $p = power($a, $n / 2) % $mod;
    $p = ($p * $p) % $mod;
    if ($n & 1)
        $p = ($p * $a) % $mod;
 
    return $p;
}
 
// Function to count permutations that are
// first decreasing and then increasing
function countPermutations($n)
{
    global $mod;
     
    // For n = 1 return 0
    if ($n == 1)
    {
        return 0;
    }
 
    // Calculate and return result
    return (power(2, $n - 1) - 2) % $mod;
}
 
// Driver Code
$n = 5;
echo countPermutations($n);
 
// This code is contributed by Tushil.
?>

<script>
    // Javascript implementation of the above approach
     
    let mod = 1000000007;
   
    // Function to compute a^n % mod
    function power(a, n)
    {
 
        if (n == 0)
            return 1;
 
        let p = power(a, parseInt(n / 2, 10)) % mod;
        p = (p * p) % mod;
        if ((n & 1) == 1)
            p = (p * a) % mod;
 
        return p;
    }
 
    // Function to count permutations that are
    // first decreasing and then increasing
    function countPermutations(n)
    {
 
        // For n = 1 return 0
        if (n == 1)
        {
            return 0;
        }
 
        // Calculate and return result
        return (power(2, n - 1) - 2) % mod;
    }
     
    let n = 5;
    document.write(countPermutations(n));
         
</script>

14

Complejidad temporal: O(log ₂ n)
Espacio auxiliar: O(1)