¿De cuántas maneras se pueden sumar 1 y 2 para que sean iguales a 17 si el orden importa?

Question

La pregunta está completa en el título. No pensé que volvería aquí tan rápido, ya que la mayoría de estos ejercicios de permutación y combinación no son muy difíciles, pero éste es el segundo que me hace rascarme la cabeza para saber por dónde empezar. He buscado algo de ayuda en Google, pero no he encontrado nada lo suficientemente parecido a este problema como para ayudarme.

Answer 1

Ayer mismo me surgió exactamente esto en un problema de la vida real[1] que estaba resolviendo. Aquí hay un Una pista:

Empieza con algo pequeño: intenta hacer sumas de 1 y 2 que sumen 1, 2, 3, 4, 5, 6. En este momento deberías ver el patrón, que es una secuencia de números que deberías reconocer. Demostrar que los números siguen realmente esta secuencia no es especialmente difícil. A continuación, encuentra el 17º número de la secuencia (tampoco es difícil).

[1] Bueno, algo así como la vida real. Tiene que ver con las sumas que surgen en una matriz de covarianza en un modelo autorregresivo en estadística. El número de términos en cada suma viene dado por este problema.

Answer 2

Sugerencia: Deja que $f(k)$ sea el número de formas de generar una suma de $k$ . A continuación, supongamos que se trata de calcular $f(n)$ . ¿Cuántas de esas combinaciones terminan con un $1$ ? ¿Cuántos terminan con un $2$ ? Suma estos dos para obtener $f(n)$ . Utiliza una relación de recurrencia. ¿Te resulta familiar? Calcula $f(17)$ .

Answer 3

Dejemos que $f(n)$ sea el número de formas de sumar $1$ s y $2$ s para conseguir $n$ .

$f(0) = 0$
$f(1) = 1$

Como podemos resumir $n-1$ y añadiendo $1$ o sumando hasta $n-2$ y añadiendo $2$ obtenemos,

$f(n) = f(n-1) + f(n-2)$

para $n>1$

Esta es la definición de la secuencia de números de Fibonacci, que es la solución.

Answer 4

Denotemos por a número de 2-s y b número de 1-s entonces número de permutaciones(arreglos) de $a+b$ objetos donde están $a$ de primera clase y $b$ de segundo tipo es $$\frac{(a+b)!}{a!b!}$$ si $$a\cdot 2+b\cdot 1=17\Rightarrow b=17-2a,0\leq a\leq 8,a+b=17-a$$ $$\sum_{2a+b=17}\frac{(a+b)!}{a!b!}=\sum_{a=0}^{8}\frac{(17-a)!}{a!(17-2a)!}=\sum_{a=0}^{8}\binom{17-a}{a}=F_{18}=1597$$

Answer 5

Si tienes algunos conocimientos de programación, puedes encontrar la respuesta de forma computacional, Proyecto Euler -estilo. Simplemente escriba un programa que itere sobre todas las combinaciones posibles de términos, y cuente el número de combinaciones que suman diecisiete.

Sabemos que hay como máximo diecisiete términos (1 + 1 + 1 ... = 17), y tres valores posibles para cada término (0, 1 o 2). Así que podemos dar un límite superior en el número de iteraciones como 3^17 = 129140163, que es un número manejable de iteraciones.

Está claro que esta solución no sirve para sumas muy superiores a 17, ya que el número de iteraciones necesarias crece exponencialmente.

Teniendo en cuenta las respuestas matemáticas más elegantes que he visto aquí, esto es probablemente parecido a matar una mosca con un mazo, pero no deja de ser una solución :)

Acabo de darme cuenta de que esto está etiquetado como tarea, así que voy a retirar el código que publiqué, para respetar eso. Todavía puedes encontrarlo en el historial de ediciones si realmente quieres verlo. En su lugar, aquí hay algunas pistas:

• Lo más difícil será probablemente encontrar una forma de iterar sobre las posibles combinaciones. Puede ser útil pensar en los términos como dígitos de un número trinario (base 3) que se incrementa de 0 a 11111111111111111.
• Tenga cuidado con las combinaciones que son realmente iguales - ...121 y ...1210, por ejemplo
• Siempre que encuentres una combinación que sume 17, añádela a un Conjunto. La respuesta será el tamaño del Conjunto una vez que termines de iterar.