Creo que la clave es entender que $0$ puede ir a donde sea y que cada número debe ir a alguna parte. Dejen a un lado $0$ por el momento.
Cuando $n=5$ tenemos $s=9$ . Podemos utilizar un razonamiento inductivo como el siguiente:
- $9$ debe estar solo, por lo que obtenemos $\{9\}$ y eso deja $\{1,2,3,4,5,6,7,8\}$ .
- $8$ sólo puede emparejarse con $1$ para alcanzar $s=9$ , por lo que obtenemos $\{1,8\}$ y eso deja $\{2,3,4,5,6,7\}$ .
- $7$ sólo puede emparejarse con $2$ para alcanzar $s = 9$ , por lo que obtenemos $\{2,7\}$ y eso deja $\{3,4,5,6\}$ .
- Procediendo de esta manera, encontramos que los subconjuntos tienen el siguiente aspecto $\big\{\{9\}, \{1,8\}, \{2,7\}, \{3,6\}, \{4,5\}\big\}$ .
Lo único que queda es asignar $0$ a algún subconjunto, por lo que obtenemos $5$ posibilidades de $s=9$ .
Cuando $n=3$ tenemos $s=15$ y las cosas se complican un poco más. Seguimos estableciendo $0$ para esto.
En primer lugar, observe que $9$ y $8$ deben ir hacia diferentes subconjuntos. A continuación, encontraremos la forma de rellenar el $9$ subconjunto, y para cada una de esas maneras, encontraremos cómo llenar el $8$ subconjunto. Los números restantes formarán su propio subconjunto.
La idea que subyace es que empezar por el número más grande es mejor porque la suma restante es menor, por lo que hay menos opciones que considerar.
Por lo tanto, tenemos $\{1,2,3,4,5,6,7\}$ y tenemos que averiguar de cuántas maneras podemos escoger elementos de ella para llegar a una suma de $6$ . Ahora, procediendo como antes, encontramos que las posibilidades son $\big\{\{6\}, \{1,5\}, \{2,4\}, \{1,2,3\}\big\}$ .
-
Si el $9$ susbset es $\{6,9\}$ nos quedamos con $\{1,2,3,4,5,7\}$ y tenemos que averiguar de cuántas maneras podemos escoger elementos de ella para llegar a una suma de $7$ (para completar el $8$ subconjunto). Procedemos como antes y llegamos a $\big\{\{7\}, \{2,5\}, \{3,4\}, \{1,2,4\}\big\}$ . Esto nos da $4$ posibilidades adicionales antes de añadir $0$ .
-
Si el $9$ susbset es $\{1,5,9\}$ nos quedamos con $\{2,3,4,6,7\}$ y tenemos que averiguar en cuántas podemos escoger elementos de ella para llegar a una suma de $7$ . Procedemos como antes y llegamos a $\big\{\{7\}, \{3,4\}\big\}$ . Esto nos da $2$ posibilidades adicionales antes de añadir $0$ .
-
Si el $9$ susbset es $\{2,4,9\}$ nos quedamos con $\{1,3,5,6,7\}$ y tenemos que averiguar en cuántas podemos escoger elementos de ella para llegar a una suma de $7$ . Procedemos como antes y llegamos a $\big\{\{7\}, \{1,6\}\big\}$ . Esto nos da $2$ posibilidades adicionales antes de añadir $0$ .
-
Por último, si el $9$ susbset es $\{1,2,3,9\}$ nos quedamos con $\{4,5,6,7\}$ y tenemos que averiguar en cuántas podemos escoger elementos de ella para llegar a una suma de $7$ . Claramente, la única manera es elegir un solo $7$ que nos da $1$ posibilidad adicional antes de añadir $0$ .
Así que tenemos $9$ posibilidades sin $0$ . Para cada una de estas configuraciones, tenemos $3$ formas de asignar $0$ a un subconjunto, lo que nos da $9\times 3 = 27$ posibilidades totales en el $n=3$ caso.
En total, esto nos da $27+5 = 32$ posibilidades.
Ahora bien, esta es una forma estructurada de pensar para abordar este problema (abordar los números grandes para reducir las posibilidades de suma sobrantes), pero existe, por supuesto, un enfoque más... operativo. Las funciones generadoras son una herramienta muy útil para cualquier combinador.
Una forma de considerar este problema si se dispone de potencia de cálculo es la siguiente.
Cuando $n=3$ consideramos el producto
$$\prod_{i=0}^9 (x_1^i+x_2^i+x_3^i).\tag{$ * $}$$
Expandiendo este producto, encontraremos una suma de monomios de la forma $c\cdot x_1^ax_2^bx_3^c$ . Cada uno de estos monomios puede interpretarse como sigue: hay $c$ formas de dividir el conjunto $\{0,1,2,\dots,9\}$ de manera que el primero El subconjunto suma a $a$ El segundo El subconjunto suma a $b$ y el tercera El subconjunto suma a $c$ .
En efecto, al ampliar el producto, en cada paso debemos elegir qué $x_i^j$ que estamos tomando. Elección de $x_i^j$ significa asignar el elemento $j$ de $\{0,1,2,\dots,9\}$ a la $i$ -año de subgrupo.
Como queremos que todos nuestros subconjuntos sumen $s=15$ entonces nos interesa el coeficiente de $x_1^{15}x_2^{15}x_3^{15}$ en la expansión de $(*)$ . Por supuesto, como tampoco nos importa el orden de nuestros subconjuntos, tenemos que dividir el resultado final por $3!$ .
Cuando digo que no nos importa el orden de nuestros subconjuntos, quiero decir que la familia de subconjuntos $\big\{\{0,6,9\}, \{7,8\}, \{1,2,3,4,5\}\big\}$ es tan bueno como $\big\{\{7,8\}, \{1,2,3,4,5\}, \{0,6,9\}\big\}$ o cualquier otra permutación.
Puede consultar con Cuadernos Wolfram en línea (o el software matemático de su elección) utilizando 1/3! * Coefficient[Product[(x^i+y^i+z^i),{i,0,9}], x*y*z,15] que la respuesta es $27$ como hacíamos cuando contábamos a mano.
Del mismo modo, para contar el número de posibilidades de $n=5$ miraríamos
$$\frac1{5!}\left[x_1^9x_2^9x_3^9x_4^9x_5^9\right]\left(\prod_{i=0}^9 (x_1^i+x_2^i+x_3^i+x_4^i+x_5^i)\right).$$
Puede consultar con 1/5! * Coefficient[Product[(a^i+b^i+c^i+d^i+e^i),{i,0,9}], a*b*c*d*e, 9] que la respuesta es $5$ como hacíamos cuando contábamos a mano.
Diré, sin embargo, que esta no es una forma computacionalmente barata o rápida de obtener la respuesta (si estás interesado en computacionalmente formas factibles de abordar este problema, tradicionalmente se maneja con una técnica llamada programación dinámica). Así que, si puedes permitirte dejar que el ordenador haga los cálculos por ti mientras tú haces otra cosa, adelante. Por supuesto, también puede ampliar el producto a mano usted mismo si lo prefiere.
También se pueden combinar ambos métodos. Este método se ve claramente perjudicado en los valores más altos de $n$ porque el número de monomios en la expansión del producto crece demasiado rápido con $n$ . Por otro lado, para valores más altos de $n$ , $s$ es menor y vemos en el ejemplo que el razonamiento inductivo se simplifica, con menos combinaciones a considerar.
Por último, este enfoque también aborda otras variaciones de este problema, como la especificación de diferentes sumas para diferentes subconjuntos y también la generalización a subconjuntos ordenados.
