De cuántas maneras podemos dejar que la gente en una sala de cine si sólo la mitad de los dólares y de dólares?

Question

Mi interés en la combinatoria recientemente se ha desatado cuando leí acerca de las muchas cosas que el catalán números de contar, como Richard Stanley. Cogí una copia de Brualdi la Combinatoria, y mientras navega por la sección de contar secuencias he encontrado un buen rompecabezas poco que tiene, definitivamente, me desconcertó.

Deje $m$ $n$ ser números enteros no negativos con $n\geq m$. Hay $m+n$ de la gente en la fila para entrar a un teatro para que la admisión si $50$ centavos. De la $m+n$ de la gente, $n$ $50$- % pieza y $m$ $\$ 1$ dólar. El cuadro de las oficinas se abre con un vacío de la caja registradora. Muestran que el número de maneras en que las personas pueden alinearse de modo que el cambio está disponible cuando se necesite es $$ \frac{n-m+1}{n+1}\binom{m+n}{m}. $$

---

Me señaló en primer lugar que la primera persona en entrar debe ser uno de los $n$ con la mitad de un dólar. Ahora el registro tiene una media de dólares al cambio. La segunda persona puede ser una persona con la mitad de un dólar o un dólar. En el primer caso, el registro tendrá ahora dos de medio de dólares, en el segundo caso, en el registro de ahora tendrá un dólar. Así que me parece que cuando uno de los $n$ de la gente con la mitad de un dólar que entra, el número de medio de dólares en el registro de los aumentos de las $1$, y cuando uno de los $m$ de personas con un proyecto de ley que entra, el número de medio de dólares disminuye por $1$, pero el número de aumentos de facturas por $1$.

Traté de modelo esta mirando rutas en $\mathbb{Z}^2$. El $x$-eje es igual que el número de medio de dólares, y el $y$-eje es el número de facturas. Empezar a $(0,0)$, y usted puede tomar los pasos hacia adelante $(1,0)$ o hacia atrás en diagonal $(-1,1)$ correspondiente a la que entra, pero debe estar siempre en el primer cuadrante del plano sin cruzar los ejes. El objetivo es hacer de $m+n$ se mueve, y pensé que tal vez el número de rutas de acceso, que se calcula por $\frac{n-m+1}{n+1}\binom{m+n}{m}$, pero no estoy seguro de cómo mostrar este. No sé si esta observación se simplifica el problema en absoluto, ya que no sé cómo terminar. Yo estaría feliz de ver cómo este problema se hace, gracias.

Answer 1

Usted está en lo correcto que usted puede pensar en esto como un problema de conteo (restringido) de caminos en el $\mathbb{Z}^2$, y que esta es probablemente una buena manera de pensar. Pero creo que es más fácil si se piensa en una matriz cuadrada, y usted está tratando de conseguir desde la parte inferior a la izquierda, $(0,0)$, en la parte superior derecha $(n,m)$, y sus pasos se deben de $(k,\ell)$ $(k+1,\ell)$o de$(k,\ell)$$(k,\ell+1)$:

Si $n$ es el número de personas con $50$ piezas, y $m$ es el número de personas con billetes de un dólar. Cuando una persona con una moneda de 50 centavos entra, usted toma un paso a la derecha. Cuando una persona con un billete de un dólar que entra, de tomar un paso hacia arriba.

Si intentas tomar un paso de$(k,\ell)$$(k,\ell+1)$, sólo tendrá suficiente cambio en la caja si $\ell+1\leq k$. De lo contrario, usted va a estar fuera de suerte (porque se necesita una persona con 50 centavos por cada persona con un dólar que ha logrado entrar).

Así, usted siempre debe permanecer en o por debajo de la diagonal. Así que las rutas de acceso que desee contar son los caminos de $(0,0)$ $(n,m)$que alojarse en o por debajo de la diagonal principal.

(Observe que $\binom{n+m}{m}$ es el número de total de las rutas de $(0,0)$ $(n,m)$tomando solo unos pasos de la derecha o de arriba: usted debe tomar $n+m$ total, y de los $m$ pasos; por lo $\binom{n+m}{m}$ los pronósticos de la $n+m$ pasos serán los pasos. Por lo que el factor de $\frac{n+1-m}{n+1}$ debe ser la fracción de los caminos que alojarse en o por debajo de la diagonal principal.)

Eso no ayuda lo suficiente, o debería ampliar más?

Answer 2

Hay una buena correspondencia uno a uno que se puede configurar aquí:

Primero de todo, es que claramente ${n+m \choose{n}}$ arreglos diferentes que la gente puede entrar en.

Deje $(i,j)$ denotar el momento en que $i+j$ personas que han pagado su boleto, donde $i$ representa el número de personas que pagan con un $50$ pieza, $j$ el número de personas que pagan con un $\$1$. Here it does not matter if everyone receives change or not. Every arrangement of people ends with $(n,m)$.

Para asegurarse de que el cambio está disponible para todo el mundo, debe ser siempre el caso de que $i \ge j$.

Se tienen en cuenta todos los arreglos que sean malos, es decir, que en algún momento alguien no recibe su cambio. Cuando la primera persona a la que no se cambie de nuevo entra, tenemos $(k,k+1)$ algunos $k$.

Aquí, hacer el siguiente truco: supongamos que todas las personas que había $\$1$'s, now wish to pay $50$ cents, and vice versa. So out of the remaining people, $m - (k+1)$ pay $50$ cents and $n - k$ pay $\$1$ las facturas. En total, se han $(k+m-(k+1),k+1+n-k) = (m-1, n+1)$.

Estamos dado que el $n \ge m$, lo $n+1 > m-1$. Así que en este caso, el número de personas que pagan $\$1$ bills is strictly greater than the number of peple paying otherwise. Now notice, that in any arrangement of people entering that ends with $(m-1,n+1)$ there must be a a first $k$, when we have $(k,k+1)$.

Ahora podemos cambiar "quién paga qué" como antes, y conseguimos llegar a un acuerdo que termina con $(n,m)$.

Esto crea un agradable bijection entre todos los arreglos malas (cuando alguien no conseguir su cambio) que terminan con $(n,m)$ y todos los posibles arreglos que terminan con $(m-1,n-1)$. Contando como antes, hay ${n+1+m-1 \choose{n+1}} = {n+m \choose{n+1}}$ posibles arreglos terminando con $(m-1, n-1)$. Por lo que el número de acuerdos donde todo el mundo recibe su cambio es:

$${n+m \choose{n}} - {n+m \choose{n+1}} = {{n+m \choose{n}}} \dfrac{n+1-m}{n+1}$$

Tenga en cuenta también que la probabilidad de que un buen arreglo que ocurren viene muy bien para

$$\dfrac{n-m+1}{n+1}$$