Ponerle calcetines y zapatos a una araña

Question

Una araña necesita un calcetín y un zapato para cada una de sus ocho patas. De cuántas maneras puede ponerse los zapatos y los calcetines, si los calcetines deben ponerse antes que el zapato?

Mi intento:

Si considero que sus patas son indistinguibles, entonces es exactamente el $8^{\text{th}}$ término de la secuencia catalana. Sin embargo, los tramos son distinguibles. Así que el número total de vías es igual a $\frac1{8+1} \binom{16}{8} (8!)^2$ .

¿Es esto correcto? ¿Hay otra forma de hacerlo?

Editar: Todos los calcetines y zapatos son distinguible .

Answer 1

Puedes imaginarte haciendo esto como si escribieras una secuencia, digamos $$3453228156467781$$

¿Qué significa?

Significa que primero se pone el calcetín en la pierna $\color{red}{3}$ y en el cuarto movimiento poner el zapato en la pierna $\color{red}{3}$

luego poner el calcetín en la pierna $\color{blue}{4}$ y en el undécimo movimiento poner el zapato en la pierna $\color{blue}{4}$ y así sucesivamente...

Así que para cada pierna debes elegir un par en esta secuencia. En el número más pequeño de este par poner un calcetín y el otro zapato.

Así que tenemos $${16\choose 2}{14\choose 2}....{4\choose 2}{2\choose 2} = {16!\over 2!^8}$$

Answer 2

No, no es correcto. Multiplicando el número catalán por $8!$ El doble significa que estamos eligiendo patas de forma arbitraria para cada caso de calceta o herradura, sin tener en cuenta si esa pata tiene un calcetín, en este último caso. Es un recuento excesivo.

Multiplicando por $8!$ una vez correspondería a una restricción de "último en entrar, primero en salir"; cada vez que nos ponemos un zapato, es la pierna más recientemente calcetada. Es un recuento insuficiente, por supuesto.

Hay dos acciones por pierna: el calcetín y el zapato. Todo lo que necesitamos saber para determinar una secuencia es cuándo se trabajó en cada pierna. Eso es $\binom{16}{2}$ para la primera etapa, $\binom{14}{2}$ para el segundo, y así sucesivamente - o, equivalentemente, el coeficiente multinomial $\binom{16}{2,2,\dots,2} = \frac{16!}{(2!)^8}$ .

Answer 3

Las respuestas dadas son correctas, pero yo tengo una manera diferente (y posiblemente más fácil) de pensar en ello:

Si se relaja la condición para que el evento de calcetines/zapatos esté en orden entonces hay $2n$ ( $=16$ ) por lo tanto, los eventos $16!$ pedidos. Se trata, por supuesto, de un recuento excesivo: muchos (la mayoría) de ellos tienen un orden inválido, con al menos un calcetín por encima de un zapato. La cuestión es saber por cuántos.

Para responder a esto, supongamos que los dividimos en grupos. Concretamente un grupo para cada una de las ordenaciones de zapato/calcetín en cada pie. Por ejemplo:

• un grupo en el que: el calcetín de la pierna 1 está antes que el de la pierna 1, el calcetín de la pierna 2 está antes que el zapato de la pierna 2..., el calcetín de la pierna 8 está antes que el zapato de la pierna 8 (el que queremos)
• un grupo en el que: el calcetín de la etapa 1 es posterior a la etapa 1, el calcetín de la etapa 2 es anterior al zapato de la etapa 2, etc. (no es válido para nosotros)

Estos grupos son del mismo tamaño (ninguno es especial).

Hay $2^n$ ( $2^8$ ) de estos grupos para que cada uno de ellos, incluido el que queremos, sea de tamaño: $\frac{16!}{2^8}$ o $81,729,648,000$ .

Notas sobre la generalización:

Supongamos que $n$ piernas y $k$ objetos para poner en un orden determinado. Hay $(k n)!$ eventos, $k!$ ordenamientos de cualquiera de los objetos de la pierna. Por lo tanto, $(k!)^n$ ordenamientos de los objetos en cada pata, sólo uno de los cuales es deseado y así: $\frac{(k n)!}{(k!)^n}$ posibles ordenaciones válidas de la colocación de un objeto en una pata.

Answer 4

Otro enfoque:

Dejemos que $f(n)$ denotan el número de formas de un $n$ -Perder las piernas para poner calcetines y zapatos en todas sus patas.

Con una pierna, sólo hay un camino: Poner el calcetín y luego el zapato.

Con dos piernas (como la gran mayoría de los humanos), hay 6 posibilidades. En la notación de Greedoid, éstas son:

• 1122 = Calcetín en la pierna 1, zapato en la pierna 1, calcetín en la pierna 2, zapato en la pierna 2
• 1212 = Calcetín en la pierna 1, calcetín en la pierna 2, zapato en la pierna 1, zapato en la pierna 2
• 1221 = Calcetín en la pierna 1, calcetín en la pierna 2, zapato en la pierna 2, zapato en la pierna 1
• 2112 = Calcetín en la pierna 2, calcetín en la pierna 1, zapato en la pierna 1, zapato en la pierna 2
• 2121 = Calcetín en la pierna 2, calcetín en la pierna 1, zapato en la pierna 2, zapato en la pierna 1
• 2211 = Calcetín en la pierna 2, zapato en la pierna 2, calcetín en la pierna 1, zapato en la pierna 1

Ahora, supongamos que hemos calculado $f(k)$ para algunos $k$ . ¿Cómo se introduce un $(k + 1)$ ¿Influye la pierna en el problema?

Si se toma cualquier secuencia posible de los $2k$ eventos de sock+shoe para $k$ piernas, entonces hay $2k + 1$ posiciones posibles en la secuencia para poner el calcetín para la nueva pierna (el $2k - 1$ posiciones entre eventos existentes, al principio o al final). Supongamos que decidimos poner este nuevo evento después de $j$ de los acontecimientos originales.

Ahora, vamos a decidir cuándo poner el zapato para la nueva pierna. Esto es más complicado, porque depende de cuándo nos pongamos el calcetín. Este nuevo evento se puede insertar en el índice $j + 1$ , $j + 2$ , $j + 3$ ..., hasta $2k + 1$ , para $2k + 1 - j$ posibilidades.

Así que, eso nos da $\sum\limits_{j=0}^{2k+1} (2k + 1 - j)$ posibilidades para cuando añadir el calcetín y el zapato para la nueva pierna, lo que resulta en el $(2k + 1)$ el número triangular = $\frac{(2k + 1)(2k + 2)}{2}$ . Con $k + 1 = n$ se puede reescribir como $\frac{(2n - 1)(2n)}{2} = n(2n - 1)$ .

Ahora tenemos la relación de recurrencia $f(n) = n(2n - 1)f(n-1)$ con caso base $f(n) = 1$ . O, en sintaxis de Python.

>>> def f(n):
...     if n == 1:
...         return 1
...     else:
...         return n * (2 * n - 1) * f(n - 1)
... 
>>> f(8)
81729648000

Prueba de que esto es equivalente a la formulación no recursiva $f(n) = \frac{(2n)!}{2^n}$ se deja como ejercicio para el lector.