¿Cuántos grupos de ramos de flores pentagonales se pueden formar?

Question

Una floristería tiene tres tipos de flores: tulipanes, rosas y margaritas. Hay 4 tulipanes, 5 rosas y 6 margaritas. Estas 15 flores deben colocarse en tres ramos de 5 flores cada uno. Supongamos que

• el orden de los tres ramos es irrelevante,
• flores del mismo tipo son indistinguibles.

¿Cuántos grupos de ramos pentagonales puede agrupar el florista?

Inténtelo

Denotemos los tulipanes, las rosas y las margaritas con T, R y D, respectivamente. Si formamos todas las cadenas de 15 letras y añadimos guiones después de cada cinco letras, podemos obtener todos los grupos posibles de ramos. Por ejemplo, una posibilidad sería $$\mathrm{TRRTR-TRDDD-DDTRD}.\tag{ex. 1}$$

Existen $\dfrac{15!}{4!\ 5!\ 6!}$ tales cadenas. Aunque, por supuesto, todos los grupos de ramos pueden obtenerse de esta manera, estamos contando más de la cuenta. Para las cadenas, $\mathrm{TRDDD-TRRTR-DDTRD}$ es diferente del ejemplo anterior, pero no supone ninguna diferencia para el grupo de ramos, ya que se ha supuesto que el orden es irrelevante. Puede resultar tentador dividir el número de ramos por $3!$ pero esto también sería incorrecto. Por ejemplo, $\mathrm{TDDDT-TDDDT-RRRRR}\tag{ex. 2}$ es un grupo válido de tres ramos que, en cambio, debería dividirse por $\dfrac{3!}{2!} = 3$ .

Por lo tanto, una forma de proceder es dividir todos los grupos de ramos en dos clases que no se entrecrucen. En primer lugar, aquellos en los que todos los grupos de tres ramos son diferentes por pares y, a continuación, los que tienen exactamente dos ramos iguales de cada tres. Obsérvese que la formación de grupos con tres ramos idénticos es imposible porque 4 tulipanes no pueden repartirse por igual entre tres ramos. Una vez particionados de esta manera, podemos dividir el primer tipo de partición con $3!$ y el segundo con $3$ .

Sin embargo, tal partición parece excesivamente tediosa, y se complica aún más por el siguiente aspecto. Tenemos que tener en cuenta que cuando hay al menos dos tipos diferentes de flores en un mismo ramo, se produce un sobreconteo con el método de la cadena. Por ejemplo, los ramos $$\mathrm{TRDDD\equiv DTRDD\equiv DDTRD\equiv DDDTR\equiv RDDDT}\tag{ex. 3}$$

son todas equivalentes, ya que pueden transformarse entre sí mediante una rotación en el espacio. (Así, una división con $5$ también puede ser adecuado para este tipo de ramos). La "complicación adicional" estriba entonces en el hecho de que los grupos de ramos que en principio parecen justificar la división por $3!$ en realidad requiere la división con $3$ como es el caso de nuestro primer ejemplo. En efecto, por ex. 3 tenemos $\mathrm{TRDDD\equiv DDTRD}$ y así $$\mathrm{TRRTR-TRDDD-DDTRD\equiv TRRTR-TRDDD-TRDDD}$$ que debe dividirse por $3$ .

Aclaración de los comentarios : los ramos que pueden transformarse unos en otros por reflexión son no equivalentes, y deben contarse como ramos diferentes.

Pregunta

La discusión anterior parece conducir a varios subcasos en los que es fácil cometer errores, y resulta tedioso generalizar. ¿Existe un enfoque más limpio? En cualquier caso, una respuesta que lleve cuidadosamente el esquema anterior hasta el final también tiene valor. Para que conste, la respuesta que obtengo con el método anterior es $898$ .

Edit : Ahora también he "confirmado" la respuesta $898$ con un programa Python independiente.

Intentar encontrar particiones del multiconjunto $\{\mathrm{T}:4, \mathrm{N}:5, \mathrm{D}:6\}$ en clases de tamaño cinco es algo en lo que reconozco no haber pensado mucho, pero que a primera vista llevaría a un recuento insuficiente, ya que, por ejemplo, el multiconjunto $\{\mathrm{D, D, R, R, T}\}$ no diferenciaría entre ramos no equivalentes $\mathrm{DDRRT}$ y $\mathrm{DTDRR}$ .

(Esta pregunta es del contexto de la combinatoria introductoria sin recurrencias, funciones generadoras, etc.).

Answer 1

Empezamos construyendo flores disposiciones ${\bf h}=(h_1,h_2,h_3)$ compuesto por tres montones $h_i=(t_i,r_i,d_i)$ $(1\leq i\leq3)$ por lo que los números $t_i$ , $r_i$ , $d_i$ están dando los números de tulipanes, rosas y margaritas en montón $h_i$ .

Por estrellas y barras el $4$ tulipanes pueden distribuirse entre los $h_i$ en ${4+2\choose 2}=15$ formas, la $5$ rosas en ${5+2\choose2}=21$ formas, y la $6$ margaritas en ${6+2\choose2}-3=25$ maneras (no queremos poner todos los $6$ margaritas en el mismo montón). De ello se deduce que hay $15\cdot 21\cdot 25=7875$ formas de construir un acuerdo de este tipo. Un pequeño programa produce todas ellas y comprueba para cada una si es admisible es decir, todos los montones tienen un tamaño $5$ . Esto significa que las condiciones adicionales $$t_i+r_i+d_i=5\qquad(1\leq i\leq3)\tag{1}$$ se cumplen. Resulta que $210$ acuerdos cumplir $(1)$ .

Por ejemplo ${\bf h}=(212, 203, 041)$ donde hemos omitido la coma interior. Este ${\bf h}$ contiene $2$ tulipanes, $1$ rosa, y $2$ margaritas en el primer montón. Entre las $210$ arreglos encontrados por el programa también hay ${\bf h}'=(203,041, 212)$ con los mismos tres montones, pero en otro orden. Dado que la OP ha deseado que los montones no estén numerados, tenemos que excluir tales duplicados. De este modo, sólo nos queda $38$ a saber $$\eqalign{&(005, 041, 410), \quad (005, 050, 401),\quad (005, 131, 320), \quad(005, 140, 311), \quad(005, 221, 230),\cr &(014, 032, 410),\quad (014, 041, 401), \quad(014, 122, 320), \quad(014, 131, 311),\quad (014, 140, 302),\cr &(014, 212, 230), \quad(014, 221, 221)^*,\quad (023, 023, 410)^*,\quad (023, 032, 401), \quad(023, 113, 320),\cr & (023, 122, 311), \quad(023, 131, 302),\quad (023, 203, 230),\quad(023, 212, 221), \quad(032, 104, 320),\cr & (032, 113, 311),\quad (032, 122, 302), \quad(032, 203, 221),\quad (032, 212, 212)^*,\quad (041, 104, 311),\cr &(041, 113, 302), \quad(041, 203, 212), \quad(050, 104, 302), \quad(050, 203, 203)^*, \quad(104, 122, 230),\cr &(104, 131, 221),\quad (104, 140, 212), \quad(113, 113, 230)^*,\quad (113, 122, 221), \quad(113, 131, 212),\cr & (113, 140, 203), \quad(122, 122, 212)^*,\quad (122, 131, 203).\cr}$$$6$ de estas disposiciones, marcadas con un asterisco, tienen dos montones iguales. Necesitan un tratamiento especial en lo que sigue.

Hasta ahora el $h_i$ eran sólo montones de cinco flores. Pero el OP quiere crear pentágonos regulares a partir de estas flores, por lo que las rotaciones de un mismo pentágono sólo deben contarse una vez. Los triples numéricos que aparecen en la lista anterior son permutaciones de los cinco triples $$500,\quad 410,\quad320,\quad 311,\quad 221\ .$$ Los tres números que aparecen dan el número de flores de cada color que hay en el montón. Cada uno de estos triples $h$ permite un cierto número $m(h)$ de pentágonos rotacionalmente diferentes. $500$ significa que las cinco flores tienen el mismo color. En este caso sólo hay un pentágono posible, y lo mismo ocurre con $410$ Por lo tanto $m(500)=m(410)=1$ . En $320$ las dos flores iguales pueden tener una distancia de $1$ o $2$ en el pentágono; hace $m(320)=2$ . Entonces $311$ : La primera flor individual se puede colocar en cualquier lugar, la segunda flor individual en cuatro lugares, hace $m(311)=4$ . Finalmente $221$ : La flor única puede colocarse en cualquier lugar, y la primera pareja de iguales puede ocupar sus lugares en ${4\choose2}$ maneras; hace $m(221)=6$ .

Ahora hay que pasar por el $38$ arreglos de la lista anterior, y multiplicar los $m$ -valores de los tres montones, cuando hay tres montones diferentes. En los arreglos estrellados es un poco más complicado: Cuando ${\bf h}=(h,h,h')$ entonces podemos mostrar los dos $h$ de forma diferente en ${m(h)\choose2}$ maneras o igualmente en $m(h)$ formas. El número total de visualizaciones posibles para este ${\bf h}$ por lo tanto es $$\left({m(h)\choose2}+m(h)\right)\cdot m(h')\ .$$

Suma todos los productos obtenidos (o valores corregidos) y tendrás el resultado final.

Answer 2

No es una respuesta, sino sólo un largo comentario, respecto a la partición del multiconjunto que mencionas, así cuando no consideramos el orden de las flores en los ramos. Sin embargo, aquí sí se tiene en cuenta el orden de los ramos, de modo que, por ejemplo, TTDDD-TTDDD-RRRRR es diferente de TTDDD-RRRRR-TTDDD. De todas formas, no creo que este cálculo pueda ayudar a resolver tu problema.

Podemos definir $t_1, t_2, t_3$ el número de tulipanes del ramo $1,2,3$ respectivamente, $r_1, r_2, r_3$ el número de rosas del ramo $1,2,3$ respectivamente, $d_1, d_2, d_3$ el número de margaritas del ramo $1,2,3$ respectivamente. Necesitamos entonces encontrar el número de soluciones enteras no negativas del siguiente sistema de ecuaciones:

$$\begin{cases} t_1+r_1+d_1=5 \\ t_2+r_2+d_2=5 \\ t_3+r_3+d_3=5 \\ t_1+t_2+t_3=4 \\ r_1+r_2+r_3=5 \\ d_1+d_2+d_3=6 \end{cases}$$

Entonces podemos utilizar funciones generadoras, y asignar las siguientes variables a cada ecuación: $x$ a la ecuación $1$ , $y$ a la ecuación $2$ , $z$ a la ecuación $3$ , $t$ a la ecuación $4$ , $u$ a la ecuación $5$ , $v$ a la ecuación $6$ . La función generadora se construye con un factor para cada variable del sistema lineal:

$$f(x,y,z,t,u,v)=\frac{x^6t^6-1}{xt-1}\frac{x^6u^6-1}{xu-1}\frac{x^6v^6-1}{xv-1}\frac{y^6t^6-1}{yt-1}\frac{y^6u^6-1}{yu-1}\frac{y^6v^6-1}{yv-1}\frac{z^6t^6-1}{zt-1}\frac{z^6u^6-1}{zu-1}\frac{z^6v^6-1}{zv-1} $$

Por ejemplo, $\frac{x^6t^6-1}{xt-1}$ tiene en cuenta la ecuación $1$ y $4$ para la variable $t_1$ . Limitamos los términos a $x^5$ porque éste es el total de la primera ecuación.

A continuación, utilizamos WolframAlpha para calcular el producto de los tres primeros factores, véase aquí . Sólo nos interesa el término con $x^5$ (los demás factores no contribuyen a $x$ ), que es:

$$x^5 (t^5 + t^4 (u + v) + t^3 (u^2 + u v + v^2) + t^2 (u^3 + u^2 v + u v^2 + v^3) + t (u^4 + u^3 v + u^2 v^2 + u v^3 + v^4) + u^5 + u^4 v + u^3 v^2 + u^2 v^3 + u v^4 + v^5)$$

y podemos sumar los otros dos factores para obtener:

$$x^5 y^5 z^5 (t^5 + t^4 (u + v) + t^3 (u^2 + u v + v^2) + t^2 (u^3 + u^2 v + u v^2 + v^3) + t (u^4 + u^3 v + u^2 v^2 + u v^3 + v^4) + u^5 + u^4 v + u^3 v^2 + u^2 v^3 + u v^4 + v^5)^3$$

Entonces, necesitamos encontrar el coeficiente de $x^5y^5z^5t^4u^5v^6$ . Para ello, seguimos utilizando WolframAlpha, pero tenga en cuenta que he tenido que sustituir $t,u,v$ con $x,y,z$ allí sólo para hacer que el motor de entender la consulta, por lo que este es un poco confuso, pero pensar en tener $t,u,v$ allí .

El resultado es $210$ Espero haberlo hecho todo correctamente. No sé si hay una manera de hacer esto a mano de una manera elegante.

Me di cuenta de que $\frac{15!}{4!5!6!}=630630=210 \times 3003$ pero no sé si esto puede significar algo.