Número de composiciones de un número natural

Dado un número natural n, encuentre el número de formas en que n puede expresarse como una suma de números naturales cuando se toma en consideración el orden. Dos sucesiones que difieren en el orden de sus términos definen composiciones diferentes de su suma. 
Ejemplos: 
 

Input :  4
Output : 8
Explanation  
All 8 position composition are:
4, 1+3, 3+1, 2+2, 1+1+2, 1+2+1, 2+1+1
and 1+1+1+1

Input :  8
Output : 128

Una solución simple es generar todas las composiciones y contarlas.
Utilizando el concepto de combinatoria, se puede demostrar que cualquier número natural n tendrá 2^(n-1) composiciones distintas cuando se tenga en cuenta el orden.
 

Una forma de ver por qué la respuesta es 2^(n-1) directamente es escribir n como una suma de 1: 
n = 1 + 1 + 1 +…+ 1 (n veces).
Hay (n-1) signos más entre todos los 1. Para cada signo más podemos elegir dividir (colocando un paréntesis) en el punto o no dividir. Por lo tanto, la respuesta es 2^(n-1).
Por ejemplo, n = 4 
Sin división 
4 = 1 + 1 + 1 + 1 [Escribimos como 4 simple]
Diferentes formas de dividir una vez 
4 = (1) + (1 + 1 + 1) [Escribimos como 1 + 3] 
4 = (1 + 1) + (1 + 1) [Escribimos como 2 + 2] 
4 = (1 + 1 + 1) + (1) [Escribimos como 3 + 1]
Diferentes formas de dividir dos veces 
4 = ( 1) + (1 + 1) + (1) [Escribimos como 1 + 2 + 1] 
4 = (1 + 1) + (1) + (1) [Escribimos como 2 + 1 + 1] 
4 = ( 1) + (1) + (1 + 1) [Escribimos como 1 + 1 + 2]
Diferentes formas de dividir tres veces 
4 = (1) + (1) + (1) + (1) [Escribimos como 1 + 1 + 1 + 1]
Como hay (n-1) signos más entre los n 1, hay 2^(n-1) formas de elegir dónde dividir la suma y, por lo tanto, 2^(n-1) sumas posibles.

// C++ program to find the total number of
// compositions of a natural number
#include<iostream>
using namespace std;
 
#define ull unsigned long long
 
ull countCompositions(ull n)
{
    // Return 2 raised to power (n-1)
    return (1L) << (n-1);
}
 
// Driver Code
int main()
{
    ull n = 4;
    cout << countCompositions(n) << "\n";
    return 0;
}

// Java program to find
// the total number of
// compositions of a
// natural number
import java.io.*;
import java.util.*;
 
class GFG
{
public static int countCompositions(int n)
{
    // Return 2 raised
    // to power (n-1)
    return 1 << (n - 1);
}
 
// Driver Code
public static void main(String args[])
{
    int n = 4;
    System.out.print(countCompositions(n));
}
}
 
// This code is contributed by
// Akanksha Rai(Abby_akku)

# Python code to find the total number of
# compositions of a natural number
def countCompositions(n):
 
    # function to return the total number
    # of composition of n
    return (2**(n-1))
 
# Driver Code
print(countCompositions(4))

// C# program to find the
// total number of compositions
// of a natural number
using System;
 
class GFG
{
public static int countCompositions(int n)
{
    // Return 2 raised
    // to power (n-1)
    return 1 << (n - 1);
}
 
// Driver Code
public static void Main()
{
    int n = 4;
    Console.Write(countCompositions(n));
}
}
 
// This code is contributed by mits

<?php
// PHP program to find the
// total number of compositions
// of a natural number
 
function countCompositions($n)
{
    // Return 2 raised
    // to power (n-1)
    return ((1) << ($n - 1));
}
 
// Driver Code
$n = 4;
echo countCompositions($n), "\n";
     
// This code is contributed
// by ajit
?>

<script>
 
// javascript program to find
// the total number of
// compositions of a
// natural number
 
function countCompositions(n)
{
    // Return 2 raised
    // to power (n-1)
    return 1 << (n - 1);
}
 
// Driver Code
 
    var n = 4;
    document.write(countCompositions(n));
 
 
 
// This code is contributed by 29AjayKumar
</script>

Producción: 
 

8

Este artículo es una contribución de Sruti Rai . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@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.