Tazas de agua de un cubo

Question

Tenemos un contenedor vacío y $n$ tazas de agua y $m$ vasos vacíos. Supongamos que queremos averiguar cuántas maneras podemos agregar las tazas de agua en la cubeta y eliminarlos con los vasos vacíos. Usted puede utilizar cada copa una vez, pero las copas son únicos.

La pregunta: ¿En cuántas maneras puede realizar esta operación.

Ejemplo: tomemos $n = 3$$m = 2$.

Para el primer paso sólo podemos añadir agua a la cubeta de modo que tenemos 3 opciones. Para el segundo paso podemos agregar otra taza o quitar una taza de agua. Así que para los 2 primeros pasos que hemos $3\times(5-1) = 12$ posibilidades. Para el tercer paso se vuelve más difícil, porque este paso depende del paso anterior. Hay dos escenarios después del segundo paso. 1: El cubo contiene 2 tazas de agua o 2: El cubo no contiene agua.

1) podemos añadir o restar una taza de agua 2) Tenemos que añadir una taza de agua

Así que después del paso 3 $3\times(2\cdot3 + 2\cdot2) = 30$ combinaciones.

etc.

Espero que me dijo esta pregunta con claridad suficiente, puesto que este es mi primer post. Esto no es una tarea sólo curiosidad personal.

Answer 1

Deje $L=n+m$ $D=n-m \ge 0$

Sugerencia 1: considere la posibilidad de una secuencia $X=(x_1,x_2, ... x_L)$, asociado a una copa llena de con $x_i=1$ y un vacío con $x_i=-1$. Deje $C(n,m)$ recuento de todas esas secuencias binarias de longitud $L$ con las dos restricciones: $\sum_{k=1}^j x_k\ge 0$, $\forall j$ y $\sum_{k=1}^L x_k =D$

Entonces, el número total de maneras en que se $C(n,m) n! m!$

Sugerencia 2: Para obtener el $C(n,m)$ no es trivial, pero el paseo aleatorio procedimientos de conteo (espejo principio) puede ayudar (por ejemplo).

---

Editado: el uso de la reflexión principio:

Consideremos, en primer lugar contar todos los senderos que van desde $y(0)=0$ $y(L)=D$tal que $y(t+1)=y(t) \pm 1$, y con $D\ge0$. (Recordemos que $L=n+m$, $D=n-m$). Esta irrestricta recuento $C^{[u]}={n+m \choose n}={L \choose (L+D)/2}$

Ahora, considere la posibilidad de la "prohibido" caminos": estos corresponden a los que tocan el $y(t)=-1$ línea. Por el espejo principio, estos se corresponden uno a uno con el irrestricto caminos que parten de $y(0)=-2$, y este número está dado por $C^{[p]}={L \choose (L+D+2)/2}={n+m \choose n+1}$

Por lo tanto, el número de rutas es

$$C(n,m) = C^{[u]}-C^{[p]}={n+m \choose n} - {n+m \choose n+1}=\frac{1+n-m}{n+1}{n+m \choose n} = \frac{1+D}{n+1}{L \choose n}$$

Y, por último, el número de maneras es $\frac{1+D}{n+1} \,L!$

Véase también la Boleta problema.

Answer 2

Para $n=m$ la respuesta es $C_n(n!)^2$ donde $C_n=\frac 1{n+1}{2n \choose n}={2n \choose n}-{2n \choose n-1}$ $n^{\text{th}}$ catalán número. El pie en el tablero de ajedrez mantenerse por debajo de la diagonal coincide con la restricción de no tener un importe negativo de agua en la cubeta y los dos factores de $n!$ provienen de la etiqueta de tazas. Para $n \gt m$ me quiero imaginar el adicional $n-m$ vasos vacíos añadido y que requieren para ser el final de la serie, pero no puede ver ¿cómo dar cuenta de eso.