5 votos

Inclusión-Exclusión

Cuántos enteros son las soluciones a la ecuación de $x_1 + x_2 + x_3 + x_4 = 32$$0 \leq x_i \leq 10$$i = 1, 2, 3, 4$?

Cuántos enteros son las soluciones a la desigualdad $$ y_1 + y_2 + y_3 + y_4 < 184 $$

con $y_1 > 0$, $0 < y_2 \leq 10$, $0 \leq y_3 \leq 17$, y $0 \leq y_4 < 19$?

Aquí hay dos problemas. Puedo ver esta combinación de $(32+4-1,4-1)$ pero estoy teniendo problemas para encontrar lo que restar de que.

También, el segundo problema está buscando una más complicada solución. Entiendo que $y_1+y_2+y_3+y_4+y_5 = 182$ $(182,4)$ para la combinación, pero ¿qué tiene que restar de que?

Gracias.

10voto

DiGi Puntos 1925

Lo que usted tiene que restar de la $\binom{35}3$ son las soluciones (en enteros no negativos) en los que al menos uno de los $x_k$ supera el límite de $10$. ¿Cuántas soluciones tiene $x_1>10$? Estas son las soluciones que han $x_1\ge 11$, por lo que existe un natural bijection entre ellos y no negativo soluciones a $$y_1+y_2+y_3+y_4=21\;:$$ just let $x_1=y_1+11$ and $x_k=y_k$ for $k=2,3,4$. Thus, there are $\binom{21+4-1}{4-1}=\binom{24}3$ solutions to the original equation in which $x_1>10$. Similarly, there are $\binom{24}3$ in which $x_2>10$, $\binom{24}3$ in which $x_3>10$, and $\binom{24}3$ in which $x_4>10$, así como una segunda aproximación hay

$$\binom{35}3-4\binom{24}3\tag{1}$$

soluciones a$x_1+x_2+x_3+x_4=32$$0\le x_k\le 10$$k=1,2,3,4$.

Por desgracia, algunos de los 'malos' soluciones han restado dos veces. Específicamente, cualquier solución en la que dos de las variables que superan el límite de $10$ han restado dos veces. Por ejemplo, la solución de $11+11+10+0=32$ se resta una vez porque $x_1>10$ y una segunda vez, debido a $x_2>10$. Para compensar esta sobrecorrección, debemos añadir a $(1)$ el número de soluciones en el que dos de las variables exceder $10$.

Soluciones en las que las $x_1>10$ $x_2>10$ corresponden a los no-negativos solución a $$y_1+y_2+y_3+y_4=10\;:$$ just let $x_1=y_1+11$, $x_2=y_2+11$, $x_3=y_3$, and $x_4=y_4$. There are $\binom{10+4-1}{4-1}=\binom{13}3$ such solutions, and there are $\binom42=6$ possible pairs of variables, so we can improve the approximation $(1)$ a

$$\binom{35}3-4\binom{24}3+6\binom{13}3\;.\tag{2}$$

No hay más correcciones necesarias, ya que no es posible que más de dos de las variables que superan el límite de $10$, e $(2)$ es por lo tanto la respuesta.

La segunda pregunta requiere un truco con el fin de compensar la desigualdad: añadir una quinta variable a tomar la diferencia entre el$y_1+y_2+y_3+y_4$$183$, por lo que usted está contando entero de soluciones a

$$y_1+y_2+y_3+y_4+y_5=183\tag{3}$$

que satisfacer $y_1>0$, $0<y_2\le 10$, $0\le y_3\le 17$, $0\le y_4<19$, y $y_5\ge 0$. Siguiente, tenga en cuenta que si nos vamos a $z_1=y_1-1$, $z_2=y_2-1$, y $z_k=y_k$$k=3,4,5$, soluciones a $(3)$ con sus condiciones de contorno corresponden a las soluciones para

$$z_1+z_2+z_3+z_4+z_5=181$$

la satisfacción de $z_1,z_5\ge 0$, $0\le z_2<10$, $0\le z_3<18$, y $0\le z_4<19$. Ignorando los límites superiores por un momento, tenemos como punto de partida

$$\binom{181+5-1}{5-1}=\binom{185}4$$

soluciones, pero por supuesto, algunos de ellos violar los límites superior. Vea si usted puede utilizar las ideas de la primera solución para llevar a cabo la inclusión-exclusión en el argumento que aquí se necesitan. Es un poco más complicado, porque los límites no son las mismas, y más de dos de ellos puede ser superado, pero las ideas son exactamente los mismos.

5voto

Calvin Lin Puntos 33086

Para la primera parte, me sugieren el uso de un cambio de variables $a_i = 10 - x_i $. Entonces, todavía tenemos $ 0 \leq a_i \leq 10 $, pero la condición se convierte ahora en el

$$a_1 + a_2 + a_3 + a_4 = 8 $$

Por lo tanto, la condición de que $a_i \leq 10$ es realmente no es necesario! Por lo tanto, por las estrellas y las barras, el número de soluciones es $ { 8 + 4 - 1 \choose 4-1 } = 165.$

Esto está de acuerdo con Brian solución, después de evaluar los coeficientes binomiales. (¡Uf!) Por supuesto, este truco sólo funciona porque los números son pequeños (grandes), y en general, usted tiene que utilizar la TARTA como Brian hizo.

3voto

Kieran Cooney Puntos 748

Uso de funciones de generación. Deje $f(x)=1+x+...+x^{10}$, a continuación, encontrar el coeficiente de $x^{32}$$(f(x))^4$.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X