Composición de un número: Composición (combinatoria)
Una composición de un número entero n es una forma de escribir n como la suma de una secuencia de enteros (estrictamente) positivos.
Por ejemplo, 4 se puede escribir como:
- Cómo calcular los componentes conectados, sin usar la función nx.connected_components (g) en NetworkX
- ¿Necesito matemáticas para programar?
- ¿Qué trabajos recomienda como introducción a la teoría de la complejidad y la teoría de la votación?
- Teoría de la complejidad computacional: ¿Hay conjeturas famosas que alguna vez se creyeron firmemente que eran ciertas pero que luego se demostraron falsas?
- ¿Por qué la gente cree que todos los teoremas sobre las máquinas de Turing son válidos cuando se habla de una computadora?
1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
2 + 1 + 1
1 + 3
3 + 1
2 + 2
4 4
Prueba:
La clave de la prueba está en la secuencia con solo unos. Coloque n 1 lado a lado con una caja □ entre cada 1. Ahora, tiene n-1 cajas.
1 □ 1 □ 1 □ 1
Puede poner un signo más (‘+’) o una coma (‘,’) en cada cuadro para obtener cada composición. Por ejemplo, si inserta comas en las 3 posiciones, obtiene 1, 1, 1, 1
Si no ha visto este problema antes, vea si puede encontrar la solución con estas sugerencias.
El remate:
Hay n – 1 decisiones binarias independientes que se tomarán donde coloque un ‘+’ o un ‘,’. Por lo tanto, el número total de formas es 2 ^ (n-1)
¿Por qué es hermosa?
El problema es fácil de enunciar. La prueba también es bastante simple. Todo lo que necesita saber es la regla del producto al contar.
El enfoque también recuerda el método de estrellas y barras (combinatoria).
