Combinaciones de flores utilizando el método de contar para particiones enteras.

Question

Tengo este problema por resolver que quiere saber cuántas combinaciones de flores pueden haber en un ramo de 25 flores, de tal manera que:

$r+c+d+t=25$ donde $r=$rosas, $c=$clavel, $d=$margaritas y $t=$tulipanes.

Las condiciones son:

• entre 1 y 7 margaritas
• entre 2 y 11 claveles
• al menos 4 rosas
• como máximo 6 tulipanes

Las desigualdades deberían verse así, creo:

• $1\leq d \leq 7$
• $2\leq c \leq 11$
• $4\leq r \leq 25$
• $0\leq t \leq 6$

He llegado hasta arreglar los límites, por lo que los límites inferiores son 0 para cada flor. Dejé que $r'=r-4$, $c'=c-2$ y $d'=d-1$. Si ajusto la ecuación para seguir estas nuevas asignaciones, entonces tengo: $r'+c'+d'+t=18$

Esto me hizo pensar que tal vez no puedo ajustar las rosas, ya que la condición es que haya al menos 4 rosas en el ramo. Si ajusto los límites, entonces obtengo esto:

• $0\leq d' \leq 6$
• $0\leq c' \leq 9$
• $0\leq r' \leq 21$
• $0\leq t \leq 6$

Después de ajustar los límites, debo usar este principio:

$$S(d'\leq 6 \cap c'\leq 9 \cap r'\leq 21 \cap t\leq 6) = S_{total}-S(d'\leq 6 \cap c'\leq 9 \cap r'\leq 21 \cap t\leq 6)^c$$

Esto ya tiene un problema, ya que el nuevo total es 18, por lo que las rosas no pueden estar entre 0 y 21. No hay forma de que haya 21 rosas cuando solo hay 18 posiciones disponibles para ser llenadas.

Otra razón por la que sé que esto está mal, es cuando intento usar $n-A+k-1 \choose k-1$, obtengo un número negativo cuando llego a $S(r'\leq 21)^c=S(r'\geq 22)$, porque $A=22$ y así que $18-22+4-1\choose 4-1$ da un número negativo. Así que hice algo mal en algún lugar.

¿Estoy haciendo algo mal? No sé cómo ajustar las rosas específicamente.

Actualización*: Cuando estaba ajustando los límites, olvidé que al ajustar las margaritas y los claveles, debería haber tenido en cuenta cuántas flores quedaban para restar de las rosas. Entonces, las rosas solo podrían tener $0\leq r' \leq 18$.

Answer 1

No sé si este método está disponible para ti, pero aquí hay una forma agradable de resolver problemas como este.

Utiliza funciones generadoras para codificar las posibles ocurrencias de flores en el ramo. Para las margaritas, es $d+d^2+d^3+d^4+d^5+d^6+d^7$ (no necesitamos hacer la conversión a $d'$). Para las claveles, es $c^2+\cdots+c^{11}$, para los rosas $r^4 + \cdots + r^{25}$ (ni siquiera necesitamos la cápsula correcta de rosas como menciona @saulspatz), y para los tulipanes $1+t+\cdots+t^6$ donde $1 = t^0$ indica que no hay tulipanes.

Al multiplicar estos cuatro polinomios, habrá términos como $d^5 c^{10} r^5 t^5$ que significan un ramo con 5 margaritas, 10 claveles, 5 rosas y 5 tulipanes. Pero eso no hace mucho por contar las posibilidades. Dado que cada flor contribuye a los 25, queremos reemplazar cada variable de flor por $x$ de modo que $d^5 c^{10} r^5 t^5$ se convierta en $x^{25}$. Cada ramo permitido contribuirá con otro $x^{25}$, por lo que el número total de ramos posibles de 25 flores será el coeficiente de $x^{25}$.

Un sistema álgebraico computacional como Wolfram Alpha puede calcular el siguiente producto (usar "expandir"):

\begin{align*} (x+\cdots+x^7)&(x^2+\cdots+x^{11})(x^4 + \cdots + x^{25})(1+x+\cdots+x^6) \\ &= x^7 + 4x^8 + 10x^9 + 20 x^{10} + \cdots + 470x^{24} + 480x^{25} +\cdots \end{align*}

El solo $x^7$ significa que solo hay una forma de hacer un ramo de 7 flores: $d^1 c^2 r^4 t^0$ en nuestro sistema con cuatro variables. El $4x^8$ significa que hay cuatro formas de hacer un ramo de 8 flores: $d^2 c^2 r^4 t^0$, $d^1 c^3 r^4 t^0$, $d^1 c^2 r^5 t^0$, $d^1 c^2 r^4 t^1$. El número de ramos de 25 flores es 480, el coeficiente de $x^{25}$.

Con cuatro tipos de flores, probablemente se podría resolver este problema con las técnicas de conteo que comenzaste. Pero la técnica de funciones generadoras proporciona más información (cuenta para diversos tamaños de ramos) de una manera mucho más simple (una vez que se configura la maquinaria): la cuenta difícil se hace en el álgebra cuando se multiplican los polinomios.

Para otro ejemplo, mira esta pregunta sobre contar posibles posiciones iniciales de Scrabble, que es como tener 27 tipos de flores con varias restricciones (por ejemplo, como máximo 2 fichas en blanco, 6 fichas A) y un ramo de 7 flores. Ese problema requiere funciones generadoras o un enfoque de fuerza bruta con computadora; argumentos de conteo cuidadosos no serían factibles.