En la imagen que se muestra a continuación el hombre de pie en P puede moverse en cualquier dirección

Question

Supongamos que un hombre está de pie en el origen de un avión. Él puede mover una casilla a lo largo de cualquiera de los ejes en cada movimiento. Cuántos caminos distintos se encuentran allí, que el hombre hace seis mueve y vuelve al origen en el final de la sexta mover?

Mi planteamiento: Si el hombre sube tiene que bajar así. Por lo que puedo ver dibujo después de que los caminos están llegando a ser un rectángulo y en cada dirección 5 rectángulos que se forman. Así, un total de 20 maneras. Sin embargo, la respuesta me fue dada para ser de 400 maneras. Donde hacer los otros?

Answer 1

Si no hay movimientos hacia arriba y hacia abajo, luego de contar los posibles caminos con L-R sólo, sólo tienes que elegir la ubicación de la L, en $\binom{6}{3} = 20$ maneras.

Si hay un arriba-abajo par y dos de izquierda a derecha pares, elija una ubicación para la U y uno de los D ($6\cdot 5=30$ formas), a continuación, elija ubicaciones de los dos L ($\binom{4}{2}$ formas), para un total de $30\cdot\binom{4}{2} = 180$.

Uno de izquierda a derecha par y dos de arriba-abajo pares es exactamente el mismo, dando otro $180$.

Por último, todos los de arriba-abajo pares es el mismo conteo problema como todos los de izquierda-derecha pares, por la otra,$20$.

El total es de $20 + 180+ 180+ 20 = 400$.

Answer 2

La generalización de la solución para $2n$ movimientos permitidos, para ser roto en N/S o a r/W pares, es como sigue.

Usted elegirá $n$ pares ($2n$ se mueve) roto en cualquiera de los pares de N/S o a r/W, por lo que tomará $2n$ se mueve de que $2i$ N/S de la piscina, donde $i$ es de ${0,1,...,n}$.

Luego de haber recolectado la $2i$ N/S de la piscina en los pares de N y S, puede organizarlos por $2i$ pick $i$ posible de formas únicas. Mismo para el $n-i$ pares de E/W. Suma todos juntos más de $i$.

$$ \la suma de _{i=0}^n \binom{n 2 n}{2} \binom{2}{i} \binom{n 2 n-2 i}{n-i} $$

Después de hacer algunas simplificación esto se resuelve como el cuadrado de la Central de Coeficiente Binomial...

$$ \binom{n 2 n}{n}^2 $$

Para el problema en cuestión con $n$=3,

$$ \binom{6}{3}^2=20^2=400 $$

Este es Sloane secuencia http://oeis.org/A002894

Answer 3

La ruta de acceso no se necesita ser un rectángulo. Por ejemplo, usted podría mover hasta tres veces y, a continuación, tres veces hacia abajo, o dos veces arriba, a la derecha, luego a la izquierda, a continuación, dos veces hacia abajo.

Como te has dado cuenta, el número de movimientos de arriba debe ser igual al número de movimientos hacia abajo. De ello se deduce que el número de movimientos que debe estar en el conjunto $\{0,1,2,3\}.$

Supongamos que hay $0$ se mueve hacia arriba. Entonces tenemos tres a la derecha y tres a la izquierda en alguna secuencia, el número de secuencias diferentes es el número de maneras en que podemos elegir donde poner el $3$ hacia la derecha se mueve en la secuencia de $6$ se mueve, es decir, $\binom 63 = 20$ maneras.

Supongamos que hay es $1$ subir. Luego también hay un movimiento hacia abajo, dos a la izquierda y dos a la derecha. El número de maneras en que estos movimientos pueden ser secuenciados es el número de maneras en las que podemos colocar dos objetos de un tipo (a la derecha), dos de un segundo tipo (a la izquierda), y una en cada uno de los otros dos tipos (arriba y abajo) en una secuencia de $6$ objetos; esto también se conoce como coeficiente multinomial, $$ \binom{6}{2\ 2\ 1\ 1} = \frac{6!}{2!2!1!1!} = 180. $$

Por simetría, el número de maneras de tener exactamente $2$ se mueve hacia arriba es el mismo que el número de maneras de tener exactamente $1$ subir: acaba de cambiar todos arriba, abajo, a la derecha o a la izquierda mover a la derecha, izquierda, arriba o abajo, respectivamente. Por la misma razón, el número de maneras de tener exactamente $3$ se mueve hacia arriba es el mismo que el número de maneras de $0$ se mueve hacia arriba. Así que puede tomar el número de maneras de hacer $0$ se mueve hacia arriba o $1$ subir y el doble de número (a cuenta de $2$ se mueve hacia arriba y $3$ se mueve hacia arriba), para un total de $$ 2(20 + 180) = 400. $$

Answer 4

Sin embargo, muchos de N pasos se toma se debe realizar el mismo número de pasos (y viceversa). Del mismo modo, sin embargo, muchos W medidas que debe tomar el mismo número de E paso (y viceversa).

Así que debe tomar de 3 pares de opuestos pasos.

No preocuparse por el orden de los pasos que puede tomar:

1) 3 pares de N/S pasos.

2) 2 pares de N/S pasos y 1 par de W/E pasos

3) 1 par de N/S pasos y 2 pares de W/E pasos.

4) 3 pares de W/E pasos.

Ahora, ¿qué orden puede seguir los pasos?

En el Caso 1) 3 de cuenta de los pasos se pueden N. El resto debe ser S. de $6$ $3$ de ellos se puede N. No son, casi por definición, $6\choose 3$ maneras de elegir los que están N. El resto son S.

Así que hay ${6\choose 3} = \frac {6*5*4}{3*2*1} = 20$ maneras de hacer esto.

(Para ser claros, estamos hablando de lo que de orden de $N/S$ pasos que da. $N-N-N-S-S-S$ o $N-N-S-N-S-S$ o $N-S-N-N-S-S$ o $S-N-N-N-S-S$ etc.)

En el Caso 4) es exactamente lo mismo. Tres de los seis pasos puede ser W y el resto debe E. por Lo que hay ${6\choose 3} = 20$ maneras de hacerlo.

En el Caso 2) dos de los seis pasos para debe ser $N$. Hay ${6 \choose 2 }= \frac {6*5}{2*1} = 15$ maneras de hacerlo. Dos de los cuatro restantes pasos deben ser $S$. Hay ${4 \choose 2} = \frac {4*3}{2*1} = 6$ maneras de hacerlo. De los dos pasos restantes, uno debe ser W. No es ${2 \choose 1} = 2$ formas para elegir. El último paso restante debe ser E. por Lo que hay ${6\choose 2}{4\choose 2}{2 \choose 1} = 15*6*2 = 180$ maneras de hacerlo.

Para aclarar. De los seis x-x-x-x-x-x pasos, lo primero que averiguar donde podemos colocar la $2$ N pasos para obtener algo como x-N-x-x-N-x. Hay $6$ lugares para poner la primera $N$ $5$ lugares para poner el segundo bu no importa en qué orden debemos elegir el Ns por lo que hay $6*5/2 = 15$ formas de elegir el Ns. A continuación, queremos elegir cómo colocar la Ss a algo como el S-N-x-S-N-x. Hay cuatro lugares para la primera S y tres para el segundo y el orden no importa, así no $4*3/2 = 6$ maneras. A continuación, ponemos la W para obtener algo como el S-N-x-S-N-W. Hay $2$ opciones para ponerlo. El último paso restante se debe E tener S-N-E-S-N-W. (que te darás cuenta de que no es un rectángulo.)

Paso 3 se puede hacer de la misma manera exacta, pero te voy a mostrar que se puede hacer de otra manera. Primero elige cual de las $6$ pasos por el $N$ paso. Hay ${6 \choose 1 }= 6$ opciones. A continuación, elija cuál de los restantes $5$ pasos pueden ser los $2$ W pasos. Hay ${5 \choose 2} = \frac {5*4}{2*1} =10$ formas de elección. A continuación, elija cuál de los restantes $3$ pasos pueden ser los en S paso. Hay ${3 \choose 1} = 3$ maneras de elegir los. Los dos últimos pasos se deben los dos E pasos. Así que hay ${6\choose 1}{5\choose 2}{3\choose 1} = 6*10*3 = 180$ maneras de hacer esto.

Podríamos haber elegido los pasos en cualquier orden y conseguido el mismo número de maneras de hacerlo. Yo voy a dejar a usted compruebe ${6\choose 2}{4\choose 2}{2\choose 1} ={6\choose 2}{4\choose 1}{3 \choose 2} = {6\choose 2}{4 \choose 1}{3 \choose 1}={6\choose 1}{5 \choose 2}{3\choose 2}= {6\choose 1}{5\choose 2}{3\choose 1}= {6\choose 1}{5\choose 1}{4 \choose 2}=180$.

Así

1) 3 pares de N/S pasos. Hay $20$ maneras de hacer esto

2) 2 pares de N/S pasos y 1 par de W/E pasos. Hay $180$ maneras de hacer esto

3) 1 par de N/S pasos y 2 pares de W/E pasos. Hay $180$ maneras de hacer esto

4) 3 pares de W/E pasos. Hay $20$ maneras de hacer esto

Así que hay $20 + 180+ 180 + 20=400$ formas de volver a los orígenes después de 6 pasos.