El número de soluciones enteras de las ecuaciones

Question

El número de soluciones enteras de las ecuaciones

Una aproximación consiste en encontrar el número de no negativo vectores de valores enteros $(x_1,x_2,...,x_r)$ tal que $$x_1 + x_2 + ... + x_r = n$$

• En primer lugar, teniendo en cuenta el número de positivo soluciones de valores enteros.

  Una aproximación a la resolución de este problema para soluciones con valores enteros positivos es imaginar que se tiene $n$ objetos indistinguibles alineados y que quieres dividirlos en $r$ grupos no vacíos. Para ello, puede seleccionar $r-1$ de la $n-1$ los espacios entre objetos adyacentes como puntos de separación. Véase el diagrama siguiente para una representación visual.

$$0_\wedge0_\wedge0_\wedge..._\wedge0_\wedge0$$

$$n\,\, objects\,\,0$$ $$Choose\,\,r-1\,\,of\,\,the\,\,spaces\,\,_\wedge.$$

Por ejemplo, si tiene $n=8$ y $r=3$ y se eligen los 2 divisores para obtener $$000|000|00$$ entonces el vector resultante es $x_1 = 3. x_2 = 3, x_3 = 2.$ Como hay $n-1\choose r-1$ posibles selecciones, tiene la siguiente proposición.

• Propuesta 1: Hay $n-1\choose r-1$ vectores distintos de valor entero positivo $(x_1, x_2,...,x_r)$ que satisface la ecuación $$x_1 + x_2 + ... + x_r = n, \,\,\, x_i > 0,\,\,\, i = 1,...,r$$

• Finalmente, a partir de la proposición 1 se puede obtener la siguiente proposición

• Propuesta 2: Hay $n+r-1\choose r-1$ distinto no negativo vectores de valores enteros $(x_1, x_2,...,x_r)$ que satisface la ecuación $$ x_1 + x_2 + ... + x_r = n$$

• Pregunta: Entiendo todos los pasos previos a la Proposición 2, así que lo que quiero saber es cómo se deriva la Proposición 2 de la Proposición 1. He dibujado múltiples diagramas utilizando el espacios entre objetos analogía añadiendo $r$ posiciones posibles adicionales para un divisor, pero ninguna de ellas es válida para todos los vectores posibles.

Answer 1

Para concretar, trabajemos con los números específicos $8$ y $3$ mencionado en el post, aunque el argumento es general.

Tenemos $8$ caramelos idénticos, y queremos distribuirlos entre $3$ niños, con algunos niños que posiblemente no reciban ningún caramelo. Llamemos a esto Tarea A.

La tarea B es la siguiente. Distribuir $8+3$ caramelos entre los niños, con cada niño recibiendo al menos $1$ caramelo. Entonces quitar un caramelo de cada niño.

Está claro que hay tantas formas de realizar la tarea B como de realizar la tarea A. Y por el análisis de la proposición 1, hay $\binom{8+3-1}{3-1}$ formas de llevar a cabo la Tarea B.

De otra manera: Imagina $8+3-1$ ranuras en una fila, así: $$\square\quad\square\quad\square\quad\square\quad\square\quad\square\quad\square\quad\square\quad\square\quad\square$$ Pondremos en marcha $8$ caramelos ("estrellas") en estas ranuras, con el otro $2$ ranuras que sirven de separadores ("barras"), posiblemente adyacentes. El número de formas de colocar los caramelos es $\binom{8+3-1}{8}$ . Es lo mismo que el número de formas de elegir el $2$ ranuras que deben dejarse en blanco.

Así que el número de soluciones es $\binom{10}{8}$ o, por el contrario $\binom{10}{2}$ .

En general, el mismo análisis muestra que el número de formas de distribuir $n$ caramelos entre $r$ niños es $\binom{n+r-1}{n}$ o, por el contrario $\binom{n+r-1}{r-1}$ .

Answer 2

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ Con $\ds{ 0 < a < 1}$ : \begin{align} &\color{#66f}{\large\sum_{x_{1} = 0}^{n}\ldots\sum_{x_{r} = 0}^{n}\delta_{x_{1} + \cdots + x_{r},n}} =\sum_{x_{1} = 0}^{\infty}\ldots\sum_{x_{r} = 0}^{\infty} \delta_{x_{1} + \cdots + x_{r},n} \\[3mm]&=\sum_{x_{1} = 0}^{\infty}\ldots\sum_{x_{r} = 0}^{\infty} \oint_{\verts{z}\ =\ a}{1 \over z^{-x_{1}\ -\ \cdots\ -\ x_{r}\ +\ n\ +\ 1}} \,{\dd z \over 2\pi\ic} \\[3mm]&=\oint_{\verts{z}\ =\ a}{1 \over z^{n + 1}} \pars{\sum_{x = 0}^{\infty}z^{x}}^{r}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ a}{1 \over z^{n + 1}}\pars{1 \over 1 - z}^{r} \,{\dd z \over 2\pi\ic} \\[3mm]&=\oint_{\verts{z}\ =\ a}{1 \over z^{n + 1}} \sum_{k = 0}^{\infty}{-r \choose k}\pars{-1}^{k}z^{k}\,{\dd z \over 2\pi\ic} =\sum_{k = 0}^{\infty}{r + k - 1 \choose k} \oint_{\verts{z}\ =\ a}{1 \over z^{n - k + 1}}\,{\dd z \over 2\pi\ic} \\[3mm]&=\sum_{k = 0}^{\infty}{r + k - 1 \choose k}\delta_{kn} =\color{#66f}{\large{r + n - 1 \choose n}} \end{align}

Answer 3

Sólo deja que $y_i=x_i+1$ y $x_1+\cdots+x_r=n$ se convierte en $y_1+\cdots+y_r=n+r$ , cuyo positivo Las soluciones con valores enteros corresponden a no negativo soluciones a la anterior.

Answer 4

Una explicación alternativa (basada en la primera parte de la respuesta aceptada):

Digamos que hay 8 caramelos en una fila y 3 niños. Cada niño recibe todos los caramelos a su izquierda, hasta el niño anterior (o hasta el principio, para el primer niño).

Para la Propuesta 1, los niños sólo pueden colocarse entre los caramelos, por lo que hay 8-1 posiciones posibles para que se coloquen. Para la Propuesta 2, los niños también pueden colocarse fuera de la fila de caramelos - hay 3 posiciones posibles fuera del borde derecho de la fila de caramelos que ahora son posiciones permitidas para colocarse. Por lo tanto, hay 8-1+3 posiciones para elegir, por lo que el número de formas de dividir los caramelos es ahora $\binom{8-1+3}{3-1}$ .

---

También añadiré otra forma de derivar la fórmula (aunque aquí, la fórmula real fue calculada por Wolfram Alpha - esto sólo deriva una suma cuyo resultado es la fórmula en la pregunta):

La diferencia entre la Proposición 1 y la Proposición 2 es que, P1 sólo permite valores positivos para $x_i$ mientras que P2 permite cualquier valor no negativo, es decir, para P2, algún $x_i$ pueden ser 0.

Digamos que hay $k$ valores en el vector $(x_1,x_2,...,x_r)$ que son 0. Entonces, sólo los restantes $(r-k)$ los valores positivos y no nulos del vector contribuyen a la suma. Por lo tanto, el número de vectores distintos se reduce aquí al número de vectores distintos con $(r-k)$ valores positivos (distintos de cero) que suman n. A partir de la Proposición 1, sabemos que para ser $n-1\choose r-k-1$ . Por lo tanto, el número de vectores distintos $(x_1,x_2,...,x_r)$ en el que un conjunto dado de $k$ los valores son 0 es $n-1\choose r-k-1$ .

Ahora, esos $k$ Los ceros pueden ser cualquiera de los $r$ valores en el vector. Por lo tanto, hay $r\choose k$ formas de elegir los lugares donde $x_i$ es cero. Para cada elección, hay $n-1\choose r-k-1$ vectores distintos. Por lo tanto, el número de vectores distintos $(x_1,x_2,...,x_r)$ en la que cualquier $k$ los valores son 0 es $n-1\choose r-k-1$$ r\Nelegir k$.

$k$ puede oscilar entre 0 (todos los valores positivos no nulos del vector) y $r-1$ (1 valor positivo no nulo, todos los demás valores 0 en el vector). Así, el número total de vectores distintos $(x_1,x_2,...,x_r)$ con valores no negativos es: $\large{\sum_{k=0}^{r-1} \binom{n-1}{r-k-1} \binom{r}{k}}$ .
Esta suma, según Wolfram|Alpha+for+k+%3D+0+to+(r-1)) se evalúa como $(n+r-1)!\over n!(r-1)!$ que es lo mismo que ${\large{n + r - 1 \choose r - 1}}$ .

Answer 5

Pues bien, este problema concreto puede resolverse pensando de la siguiente manera:

Paso 1: Primero encuentra el número total de soluciones en las que ninguna de las variables de x1, x2 y x3 es cero.

Paso 2: A continuación, encuentra el número de soluciones en las que sólo una de x1, x2 y x3 es cero.

Paso 3: A continuación, encuentra el número de soluciones en las que sólo dos de x1, x2 y x3 son cero.

Paso 4: Por último, se suma todo el número de soluciones encontradas en los pasos anteriores. Esta es la respuesta final.

Este método se puede generalizar y llegaremos a la misma fórmula.

PD: No tengo ni idea de cómo se escriben las ecuaciones matemáticas aquí, y por lo tanto mi contribución puede parecer, con razón, fea para algunos de los contribuyentes aquí.