Duda sobre dos problemas de permutaciones y combinaciones

Question

Aquí hay dos preguntas de permutaciones y combinaciones:

1. Hay 10 mantas idénticas. Hay que repartirlas entre 4 mendigos (distintos). ¿De cuántas maneras puedes hacerlo para que cada mendigo tenga al menos 1 manta?

2. Hay 10 (distintos) turistas y 4 (distintos) hoteles. ¿De cuántas formas pueden alojarse los turistas en el hotel para que ningún hotel se quede sin turistas?

Mi enfoque:

1. Que el número de mantas recibidas por cada mendigo sea $x_1, x_2, x_3, x_4$ respectivamente. Tendremos $x_1+x_2+x_3+x_4=10$ con la restricción de que cada uno de $x_1, x_2, x_3, x_4$ son $\geq$ 1.

Considere la ecuación $x_1 + x_2 + x_3 + ... x_n = k$ , donde $\min(x_1)\leq x_1\leq \max(x_1)$ , $\min(x_2)\leq x_2\leq \max(x_2)$ , ... $\min(x_n)\leq x_n\leq \max(x_n)$ .

Consideramos la expansión $$(x^{\min(x_1)} + x^{\min(x_1)+1} + ... x^{\max(x_1)} )\cdot(x^{\min(x_2)} + x^{\min(x_2)+1} + ... x^{\max(x_2)} )...(x^{\min(x_n)} + x^{\min(x_n)+1} + ... x^{\max(x_n)} )$$ El coeficiente de $x^k$ en esta expansión será el número de soluciones integrales de nuestra ecuación.

El motivo es el siguiente:

Cuando abrimos la expansión completa, cada término que obtenemos se obtiene elevando x a la potencia de la suma de cierta combinación distinta de valores de $x_1, x_2, x_3 ... x_n$ . Cuando la suma de estas combinaciones únicas suma k, obtenemos una solución a nuestra ecuación. Como el coeficiente corresponde al número de formas en que estas combinaciones pueden sumar k, el coeficiente de $x^k$ es nuestra respuesta.

Volvamos ahora a nuestra pregunta. Tenemos $x_1 + x_2 + x_3 + x_4 = 10$ . Calculemos el número máximo de mantas que puede recibir cada persona; para ello, el resto de las 3 personas debe recibir sólo una manta, por lo que el límite superior del número de mantas que puede recibir una persona es 10-3=7. Así que consideramos el coeficiente de $x^10$ en $(x+ x^2 + x^3 +... x^7 ) ^4$

Obsérvese que también podemos introducir términos de potencia superior a 7, como podemos considerar la expansión de $(x + x^2 + x^3 + x^4 ... + x^7 + x^8 + ... ) ^4$

Esto no supondrá ninguna diferencia porque los términos de potencia superior a 7, no pueden de ninguna manera sumarse con potencias de otros paréntesis para dar lugar a la potencia de 10. Pero supongamos que, si $x<1$ (no importa realmente cuál sea x, porque sólo necesitamos encontrar el coeficiente de una determinada potencia de x). Se trata de una serie geométrica infinita que converge a $x^4 (1-x)^{-4}$

Así que podemos encontrar el coeficiente de $x^{10}$ en este término, o simplemente el coeficiente de $x^6$ en $(1-x)^{-4}$ que por el teorema del binomio resulta $^9C_6$ (resultado utilizado: coeficiente de $x^r$ en $(1-x)^{-n}$ (n y r son enteros positivos) es $^{(n+r-1)}C_r$ .

Así que obtenemos $$number \ of \ ways = \ ^9C_6 \ = \ 84$$

2. Estoy utilizando el principio de inclusión-exclusión. Primero calculamos el número total de formas en que 10 turistas distintos pueden alojarse en 4 hoteles distintos, que es 4^10. Pero esto incluye los casos en que 1, 2 o 3 hoteles están vacíos, lo que no queremos. Así que primero restamos el número de casos en los que 1 hotel está vacante, que es $^4C_1\cdot(3^{10})$ , lo que significa básicamente que se elige uno de los 4 hoteles para excluirlo, y luego se aloja a los turistas en los 3 restantes.

Observe, sin embargo, que esta resta también incluye los casos en los que dos hoteles están vacíos, y en realidad dos copias de cada uno de esos casos (digamos que usted elige excluir el hotel A, y aloja al resto de los turistas en C y D de una manera determinada, pero su resta también incluye el caso en el que elige excluir el hotel B, y aloja a los turistas en los hoteles C y D de esa misma manera determinada).

Así que como tenemos que restar los casos de 2 hoteles que están vacantes sólo una vez, y en realidad estamos restando dos veces, añadimos el término de dejar dos hoteles vacantes, que es $^4C_2\cdot (2^{10} )$ a nuestra respuesta.

De nuevo, fíjese en que cuando restamos los casos en los que teníamos que alojar a los turistas en 3 hoteles, también incluimos el caso de alojar a los turistas en un solo hotel, y tres copias del mismo (considere la posibilidad de excluir A, B y C en diferentes escenarios, pero sólo alojar a todos los turistas en D).
Asimismo, cuando añadimos el término correspondiente al alojamiento de turistas en sólo 2 hoteles, volvimos a añadir tres copias del caso de alojamiento de turistas en un solo hotel (imaginemos que excluimos AB, BC, CA en diferentes escenarios y alojamos a los turistas sólo en D). Así que, efectivamente, no tratamos el caso de alojar turistas en sólo 1 hotel, por lo que lo restamos al final como el término $^4C_1\cdot(1^{10} )$ .

Así que nuestra respuesta final es $$number \ of \ ways \ = \ 4^{10} - (^4C_3)\cdot3^{10} + (^4C_2)\cdot2^{10} - (^4C_1)\cdot1^{10} \ = \ 818520$$

¿Estoy enfocando esto de la manera correcta? Alguna confirmación u orientación sería estupenda.

Answer 1

Un atajo puede ser encontrar directamente las soluciones integrales no negativas de esta ecuación $x_1+x_2+x_3+x_4=6$ . La base es que le das a cada una de las personas una manta y entonces tu problema sigue siendo encontrar las soluciones integrales no negativas de la ecuación anterior. Espero que conozcas la fórmula. Tu método, aunque largo, es absolutamente correcto.

Answer 2

Para el caso etiquetado (turista distinto en lugar de mantas idénticas) se puede utilizar el función generadora exponencial

$(x + {x^2 \over 2!} + {x^3 \over 3!} + {x^4 \over 4!} ... + {x^7 \over 7!} + {x^8 \over 8!} + ... ) ^4$

Ahora nos interesa el coeficiente de $x^{10} \over 10!$ que es $818520$ .

¿Cómo llegó esto?

1. Supongamos que los 10 turistas se distribuyen como $\ 2+2+2+4 \ $ . Entonces, existe el llamado coeficiente multinomial,

${10 \choose 2,2,2,4} = {10! \over 2!2!2!4!}$ que es el coeficiente de

$x^2y^2x^2t^4 \ $ en $\ (x+y+z+t)^{10} \ $ y dice de cuántas maneras se puede hacer esto.

2. Supongamos ahora que tenemos que distribuir a los turistas de manera que cada hotel tenga $\ 2..4 \ $ de ellos.

La respuesta sería la suma de $\ 10 \ $ coeficientes multinomiales

${10 \choose 2,2,2,4} + {10 \choose 2,2,3,3} + \cdots + {10 \choose 4,2,2,2}$

Dos x contribuyen a esta suma con términos como $\ 1 \ \over 2! \ $ , tres x con $\ 1 \ \over 3! \ $ cuatro x generan términos como $\ 1 \ \over 4! \ $ .

3. Ahora toma una variable de contador $\ a \ $ y observe la expresión

$10! ( { a^2 \over 2!} + { a^3 \over 3!} + { a^4 \over 4!})( { a^2 \over 2!} + { a^3 \over 3!} + { a^4 \over 4!})( { a^2 \over 2!} + { a^3 \over 3!} + { a^4 \over 4!})( { a^2 \over 2!} + { a^3 \over 3!} + { a^4 \over 4!})$

esta expresión contendrá los diez multinomios como un término entre los 81 términos. Para seleccionar los "buenos multinomios" sólo tenemos que mirar el coeficiente de $\ a^{10}$ . Para multiplicarlo por $10!$ tenemos que considerar el coeficiente de $\ a^{10} \over 10! \ $