¿Cuántas formas de sumar hasta 32?

Question

Se me ha presentado un problema de combinación bastante complejo.

Utilizando sólo los números 2, 4, 6 y 8, ¿de cuántas formas posibles se puede sumar hasta 32 si el número 4 sólo puede utilizarse una vez en cualquier solución?

Incluyendo también las soluciones que no utilizan el número 4, puedo encontrar 29 soluciones únicas cuando el orden no importa.

Solución 1: 8 8 8 8
Solución 2: 8 8 8 4 2 2
Solución 3: 8 8 8 2 2 2
Solución 4: 8 8 6 6 4
Solución 5: 8 8 6 6 2 2
Solución 6: 8 8 6 4 2 2 2
Solución 7: 8 8 6 2 2 2 2 2
Solución 8: 8 8 4 2 2 2 2 2
Solución 9: 8 8 2 2 2 2 2 2 2
Solución 10: 8 6 6 6
Solución 11: 8 6 6 4 2
Solución 12: 8 6 6 6 2 2 2
Solución 13: 8 6 6 4 2 2 2
Solución 14: 8 6 6 2 2 2 2 2 2
Solución 15: 8 6 4 2 2 2 2 2 2
Solución 16: 8 6 2 2 2 2 2 2 2 2
Solución 17: 8 4 2 2 2 2 2 2 2 2 2
Solución 18: 8 2 2 2 2 2 2 2 2 2 2 2
Solución 19: 6 6 6 6 2
Solución 20: 6 6 6 6 4 2 2
Solución 21: 6 6 6 6 2 2 2 2
Solución 22: 6 6 6 4 2 2 2 2 2
Solución 23: 6 6 6 2 2 2 2 2 2 2
Solución 24: 6 6 4 2 2 2 2 2 2 2
Solución 25: 6 6 2 2 2 2 2 2 2 2 2
Solución 26: 6 4 2 2 2 2 2 2 2 2 2 2
Solución 27: 6 2 2 2 2 2 2 2 2 2 2 2 2 2
Solución 28: 4 2 2 2 2 2 2 2 2 2 2 2 2 2 2
Solución 29: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

Esto, en sí mismo, fue un reto, pero hay restricciones adicionales:

A. El orden SÍ importa. Es decir, algo como [8,8,6,6,4] sí se considera una solución diferente a [8,8,6,4,6].

B. Cualquier solución que utilice el número 4, debe COMENZAR con el número 4.

Si considero que cualquier elemento que tenga el mismo valor que otros elementos dentro de una solución dada es único, puedo tomar n Donde n es el número de elementos de cada solución. Naturalmente, para las soluciones que contienen el número 4, utilizo ( n -1)! en su lugar. Eso me proporciona la friolera de 21.104.423.119.848 soluciones.

Tomando los elementos que se repiten como no únicos, usando n!/(n1! x n2! x n3! x ... x nk!) para todas las soluciones que no contienen el número 4, y lo mismo pero usando (n-1)! en el numerador para las soluciones que sí contienen el número 4, encuentro unas 1.577 soluciones muy reducidas.

Esta es la parte con la que tengo problemas.

C. Hay dos formas únicas de incluir el valor 2 en una solución.

D. Hay cuatro formas únicas de incluir el valor 8 en una solución.

E. Hay cinco formas únicas de incluir el valor 6 en una solución.

Es decir, hay diferentes "versiones" de cada valor.

F. No se pueden repetir versiones de 6 u 8 en una misma solución

Para mayor claridad, supongamos que tenemos [8,8]. Hay 4 "versiones" de 8 que pueden usarse, pero que no se repiten dentro de una solución. Por ejemplo, [8a,8a] no es válido. Podría ser [8a,8b] o [8a,8c] o [8a,8d] o [8b,8a] o [8b,8c] etc.

Supongamos que tienes [2,2]. Como puedes repetir "versiones" de 2, podrías usar [2a,2b] o [2b,2a] o [2a,2a] o [2b,2b].

Ahí lo tienes.

Siguiendo todas las restricciones, ¿de cuántas formas diferentes puedes sumar 32?

Answer 1

El recuento es $7424856$ .

El enfoque natural, ya que el orden importa, es utilizar una función generadora exponencial (utilizaremos una variable $t$ ). Como cada símbolo tiene un valor, y queremos que el valor total sea $32$ utilizamos una segunda variable $x$ para llevar la cuenta del valor: si un símbolo tiene valor $v$ y se puede utilizar como máximo $r$ veces, introducimos un factor $$\left(1+x^v t + x^{2v}\frac{t^2}{2!} + \cdots + x^{rv}\frac{t^r}{r!}\right)$$ correspondiente a ese símbolo. (Si $r=\infty$ este factor es $\exp(x^v t)$ .)

Dejemos que $f(x,t)$ sea el producto de estos factores sobre todos los símbolos. (En tu problema habrá múltiples factores para un valor dado $v$ ya que tenemos varios símbolos con el mismo valor). Dada una suma $s$ y una longitud $l$ el número de cadenas de longitud $l$ y el valor total $s$ es el coeficiente de $x^s t^l/l!$ en $f(x,t)$ .

Para su ejemplo, ignoraremos el $4$ por ahora, como sugieres. Tenemos $$f(x,t)=e^{2 t x^2} \left(1+t x^6\right)^5 \left(1+t x^8\right)^4;$$ obtenemos nuestra respuesta calculando el coeficiente de $x^{32}$ (que es un polinomio en $t$ ), y el coeficiente de $x^{28}$ (para tener en cuenta las cadenas con un $4$ delante), sumando estos dos, y sustituyendo $t^k$ por $k!$ .

Encontramos $[x^{28}]f(x,t)$ y $[x^{32}]f(x,t)$ son $$=\frac{8 t^{14}}{42567525}+\frac{8 t^{12}}{31185}+\frac{16 t^{11}}{14175}+\frac{4 t^{10}}{63}+\frac{32 t^9}{63}+\frac{16 t^8}{5}+\frac{80 t^7}{3}+50 t^6+88 t^5+60 t^4$$ y $$\frac{2 t^{16}}{638512875}+\frac{8 t^{14}}{1216215}+\frac{16 t^{13}}{467775}+\frac{8 t^{12}}{2835}+\frac{16 t^{11}}{567}+\frac{92 t^{10}}{315}+\frac{32 t^9}{9}+\frac{34 t^8}{3}+56 t^7+122 t^6+60 t^5+t^4$$ respectivamente. Sumando estos datos, y sustituyendo $k!$ para $t^k$ da la respuesta $7424856$ .

Observación. En lugar de ignorar el $4$ podemos incorporarlo a $f(x,t)$ con el factor $(1+x^4)$ el poder de $t$ ya no mide la longitud de la cadena, sino sólo la longitud del permutable parte de la cadena (donde el orden importa). El resultado es el mismo.

Ejemplo. Resulta instructivo verificar el cálculo observando un caso más pequeño, sustituyendo $32$ por $8$ (y digamos que no hay $4$ 's.) Tenemos $$[x^8]f(x,t)=\frac{2 t^4}{3}+10 t^2+4 t,$$ por lo que el argumento anterior implica que debe haber $4$ cadenas de longitud $1$ , $10(2!)=20$ de longitud $2$ y $2/3(4!)=16$ de longitud $4$ . Estos son correctos: el $4$ cadenas de longitud $1$ son los $4$ "versiones" del $8$ símbolo; el $20$ cadenas de longitud $2$ son permutaciones de a $6$ y un $2$ en varias versiones, y el $16$ cadenas de longitud $4$ parecer $2222$ donde hay $2$ posibles versiones de cada una $2$ .