Número de arrays bitónicas de longitud n y que constan de elementos de 1 a n

Para un número dado n (n > 1), necesitamos encontrar el número de formas en que puede hacer una array bitónica de longitud n, que consta de todos los elementos del 1 al n. 
Nota: [1, 2,…n] y [n, n – 1…2, 1] no se consideran arreglos bitónicos. 
 

Ejemplos: 

Input : n = 3
Output : 2

Explanation : [1, 3, 2] & [2, 3, 1] 
are only two ways of bitonic array 
formation for n = 3.

Input : n = 4
Output : 6

Para la creación de un arreglo bitónico, digamos que tenemos un arreglo vacío de longitud n, y queremos poner los números del 1 al n en este arreglo en forma bitónica, ahora digamos que queremos agregar el número 1, tenemos solo 2 formas posibles de poner el número 1, ambas son las posiciones finales porque si debemos poner 1 en cualquier lugar que no sean los puntos finales, entonces el número en ambos lados de 1 es mayor que 1. Después de eso, podemos imaginar que tenemos un array de longitud n-1, y ahora queremos poner el número 2, nuevamente por las mismas razones tenemos dos formas y así sucesivamente, hasta que queramos poner el número n, solo tendremos 1 forma en lugar de 2, entonces tenemos n-1 números que tienen 2 formas de poner, entonces por la regla de multiplicación de la combinatoria la respuesta es 2^n-1, finalmente debemos restar 2 de la respuesta porque las permutaciones 1 2 3 4…. n y n n-1 … 3 2 1 no deben contarse.
 

// C++ program for finding
// total bitonic array
#include<bits/stdc++.h>
using namespace std;
 
// Function to calculate no. of ways
long long int maxWays( int n)
{
    // return (2^(n - 1)) -2
    return (pow(2, n - 1) - 2);
}
 
// Driver Code
int main()
{
    int n = 6;
    cout << maxWays(n);
    return 0;
}

// Java program for finding
// total bitonic array
class GFG
{
     
    // Function to calculate no. of ways
    static int maxWays( int n)
    {
         
        // return (2 ^ (n - 1)) -2
        return (int)(Math.pow(2, n - 1) - 2);
    }
     
    // Driver Code
    public static void main (String[] args)
    {
        int n = 6;
         
        System.out.print(maxWays(n));
    }
}
 
// This code is contributed by Anant Agarwal.

# python program for finding
# total bitonic array
 
# Function to calculate no. of ways
def maxWays(n):
     
    # return (2^(n - 1)) -2
    return (pow(2, n - 1) - 2);
  
# Driver Code
n = 6;
print(maxWays(n))
  
# This code is contributed by Sam007

// C# program for finding
// total bitonic array
using System;
 
class GFG
{
     
    // Function to calculate no. of ways
    static int maxWays( int n)
    {
         
        // return (2 ^ (n - 1)) -2
        return (int)(Math.Pow(2, n - 1) - 2);
    }
     
    // Driver Code
    public static void Main ()
    {
        int n = 6;
         
        Console.Write(maxWays(n));
    }
}
 
// This code is contributed by nitin mittal.

<?php
// PHP program for finding
// total bitonic array
 
// Function to calculate
// no. of ways
function maxWays( $n)
{
     
    // return (2^(n - 1)) -2
    return (pow(2, $n - 1) - 2);
}
 
// Driver Code
$n = 6;
echo maxWays($n);
 
// This code is contributed by vt_m.
?>

<script>
 
// Javascript program for finding
// total bitonic array
 
// Function to calculate no. of ways
function maxWays( n)
{
    // return (2^(n - 1)) -2
    return (Math.pow(2, n - 1) - 2);
}
 
// Driver Code
var n = 6;
document.write( maxWays(n));
 
</script>

Producción:  

30

Este artículo es una contribución de Shivam Pradhan (anuj_charm) . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.