Cuántas soluciones naturales a $x_1+x_2+x_3+x_4=100$$x_1 \neq x_2 \neq x_3 \neq x_4$?

Question

Me he inventado un poco de ejercicio de combinatoria que no puedo resolver (sin fuerza bruta): de cuántas maneras se puede elegir 4 enteros no negativos, la suma de los cuales es de 100 y todos ellos son diferentes? Así:

$x_1+x_2+x_3+x_4=100$

$x_1, x_2, x_3, x_4 \in \mathbb N$

$x_1 \neq x_2 \neq x_3 \neq x_4$

He pensado que el resultado tiene que ser el número de total de la combinación de $\binom {100 + 4 - 1} {4 - 1}$ menos de las maneras en que puedo solucionar $2x_1 + x_2 + x_3 = 100$. De todos modos, yo no soy capaz de resolverlo.

La solución debe ser:

161664 o $\binom {100 + 4 - 1} {4 - 1} - 15187 = 176851 - 15187 = 161664$

¿Alguien sabe cómo calcular las combinaciones de este problema?

Answer 1

Aquí es una solución con funciones de generación. Deje $a_n$ el número de objetos que desea contar, es decir, la ordenada cuádruples de distintas enteros no negativos con una suma de $n$, y deje $f(x)=\sum_{n\ge0}a_nx^n$ ser el ordinario de la generación de la función de esta secuencia. Desde los enteros en la suma son distintos, la generación de esta función debe ser $$f(x)=\left[\frac{y^4}{4!}\right]\prod_{n\ge0}(1+yx^n).$$ A continuación, el problema de la informática $a_n$ se reduce a encontrar el coeficiente de $[x^n]f(x)$. Usted puede hacer esto con las técnicas estándar, pero sí tener un poco de persistencia! El resultado es una fórmula explícita para $a_n$, y, en particular, para $a_{100}$, como se solicitó.

En primer lugar, puesto que las sumas son más familiar para mí que el de los productos, voy a cambiar el producto de una suma por medio de exponenciales y logaritmos: $$f(x)=\left[\frac{y^4}{4!}\right]\exp\bigl(\sum_{n\ge0}\log(1+yx^n)\bigr).$$ Ya que con el tiempo va a extraer el coeficiente de $y^4$, podemos ampliar el logaritmo en su serie de Taylor hasta el 4 º de la orden de los poderes de $y$ con $\log(1+t)\approx t-\frac12t^2+\frac13t^3-\frac14t^4$, y, a continuación, suma el resultado serie geométrica: \begin{eqnarray*} % \nonumber to remove numbering (before each equation) f(x) &=& \left[\frac{y^4}{4!}\right]\exp\bigl(\sum_{n\ge0}yx^i-\frac12y^2x^{2i}+\frac13y^3x^{3i}-\frac14y^4x^{4i} \bigr)\\ &=& \left[\frac{y^4}{4!}\right]\exp\bigl(\frac y{1-x}-\frac12\,\frac{y^2}{1-x^2}+\frac13\,\frac{y^3}{1-x^3}-\frac14\,\frac{y^4}{1-x^4}\bigr). \end{eqnarray*} En esta etapa, es un poco más fácil la sustitución de la exponencial de la suma con el producto de las exponenciales. A continuación, vamos a ampliar cada exponencial en su serie de Taylor (de nuevo a través de la 4 º de la orden de los poderes de $y$), el uso de $\exp(t)\approx1+t+\frac12t^2+\frac1{3!}t^3+\frac1{4!}t^4$: \begin{eqnarray*} % \nonumber to remove numbering (before each equation) f(x) &=& \left[\frac{y^4}{4!}\right]\exp\bigl(\frac y{1-x}\bigr) \exp\bigl(-\frac12\frac{y^2}{1-x^2}\bigr) \exp\bigl(\frac13\frac{y^3}{1-x^3}\bigr) \exp\bigl(-\frac14\frac{y^4}{1-x^4}\bigr) \\ &=& \left[\frac{y^4}{4!}\right]\left( 1+\frac y{1-x}+ \frac12\frac{y^2}{(1-x)^2}+ \frac16\frac{y^3}{(1-x)^3}+\frac1{24}\frac{y^4}{(1-x)^4}\right)\times\\ &&\quad \left( 1-\frac12\,\frac{y^2}{1-x^2}+\frac18\frac{y^4}{(1-x^2)^2}\right) \times\left( 1+\frac13\,\frac{y^3}{1-x^3}\right) \times\left( 1-\frac14\,\frac{y^4}{1-x^4}\right) . \end{eqnarray*} En la expansión de este producto, solo hay cinco términos con un coeficiente de $y^4$, por lo que $$ f(x)=\frac 8{(1-x)(1-x^3)}-\frac6{(1-x)^2(1-x^2)} +\frac1{(1-x)^4}+\frac3{(1-x^2)^2}-\frac6{1-x^4}.$$ El uso de datos básicos acerca de la serie de expansiones de las funciones racionales, es sencillo calcular el coeficiente de $x^n$ en cada uno de los cinco términos, lo que resulta en \begin{eqnarray*} % \nonumber to remove numbering (before each equation) a_n &=&[x^n]f(x) \\ &=& 8\left(\lfloor n/3\rfloor+1\right) -\frac32\bigl(\{1\text{ if }2|n\}+ (n+3)(n+1)\bigr)+\\ &&\frac{(n+3)(n+2)(n+1)}{6}+3\left\{n/2+1\text{ if } 2|n\right\}-6\left\{1\text{ if }4|n\right\}. \end{eqnarray*} Como en otros cálculos, esto da $a_{100}=161\,664$.

Answer 2

Esto puede ser solucionado por medio de la inclusión/exclusión. Definir $X_{ij}$ a ser el conjunto de soluciones de esta ecuación que ha $x_i=x_j$ donde $\{i,j\}$ varía a lo largo de las seis de 2 elementos de los subconjuntos de a $\{1 \ldots 4\}$. Como el OP menciona, el número de soluciones a este problema sin ningún tipo de restricciones en el $x_i$'s $103 \choose 3$. Para calcular $|X_{ij}|$, $i \ne j$, observe que la suma de $x_i + x_j = 2x_i$, puede ser cualquier número en $\{0, 2, \ldots, 100\}$. Una vez que la suma de $s$ es elegido, se $101-s$ soluciones en $X_{ij}$ tener $x_i+x_j=s$, es decir, donde los dos restantes variables $x_k$ $x_\ell$ variar a lo largo de $\{(0,100-s), (1,99-s), \ldots (100-s,0)\}$. Así tenemos $$|X_{ij}| = \displaystyle\sum_{i=0}^{50} (101-2i) = 101\times51 - 2\times\frac{50\times51}{2}=2601$$

Para continuar con la inclusión/exclusión, tenemos que calcular $|X_{ij} \cap X_{k\ell}|$. Hay ${6 \choose 2} = 15$ tales intersecciones. De estas exactamente 3 tiene todas las de $i, j, k, \ell$ distintos, obligando a los dos pares de nuestros valores de igualdad, tales como 30 + 30 + 20 + 20 = 100. En este caso, no es difícil ver que $x_i+x_j$ puede ser cualquier valor en $\{0, 2, \ldots, 100\}$, y una vez elegido, no hay una única solución para$x_k$$x_\ell$, lo que significa que en este caso $|X_{ij} \cap X_{k\ell}| = 51$.

El resto de los doce pares de intersecciones se superponen en uno de los índices, por lo que son de la forma$X_{ij} \cap X_{ik}$, $i,j,k$ distintas. Cualquier solución en este cruce ha $x_i=x_j=x_k$; como por encima de la suma de $x_i+x_j+x_k$ puede ser cualquier valor en $\{0, 3, 6, \ldots 99\}$, por lo que hay 34 opciones. Una vez que esta suma es elegido, $x_\ell$ se determina de forma única, por lo $|X_{ij} \cap X_{ik}| = 34$ diferentes $i,j,k$.

Que se ocupa de los pares de las intersecciones; ahora tenemos que mirar en la 3-forma intersecciones $X_{ij} \cap X_{k\ell} \cap X_{mn}$. Hay ${6 \choose 3} = 20$ posibles intersecciones. De estos 20, exactamente 4 $|\{i,j,k,\ell,m,n\}| = 3$, por ejemplo $\{i,j\} = \{1,2\}$, $\{k,\ell\} = \{1,3\}$ y $\{m,n\} = \{2,3\}$. En estos cuatro casos, la intersección de estos tres conjuntos es igual a la intersección de dos de ellos, por lo que por encima de la intersección tiene un tamaño de 34.

En los otros 16 casos, la intersección tiene una única solución, a saber,$x_1 = x_2 = x_3 = x_4 = 25$. Una solución en $X_{ij} \cap X_{k\ell} \cap X_{mn}$ ha $x_i = x_j$, $x_k = x_\ell$ y $x_m = x_n$. Si $\{i,j\}$ $\{k, \ell\}$ de solapamiento (decir $j=\ell$), luego tenemos a $x_i = x_j = x_k$, $i,j,k$ distintas. Desde los cuatro índices deben aparecer, sabemos que uno de $m$ o $n$ debe ser en $\{i,j,k\}$, mientras que el otro es el otro índice. Esto obliga a todas las cuatro variables a ser igual. Si $\{i,j\}$ $\{k,\ell\}$ son disjuntos, entonces uno de $m$ o $n$ debe ser en $\{i,j\}$ y el otro debe estar en $\{k,\ell\}$, que a su vez se obliga a todas las variables a ser igual.

Afortunadamente, en este último caso, abarca todos los 4, 5 y 6-forma de las intersecciones de los conjuntos; todos ellos tienen el tamaño 1. Así que, usando de inclusión/exclusión, obtenemos el número de soluciones: $${103 \choose 3} - 6\times2601+ (3 \times 51 + 12 \times 34) - (4 \times 34 + 16) + 15 - 6 +1 = {103 \choose 3} - 15187$$