¿Cuántas formas hay de llenar $k$ ranuras con números que van desde $1$ a $n$ si los números están en orden no decreciente?

Question

¿Cuántas formas hay de llenar $k$ ranuras con números que van desde $1$ a $n$ si los números están en orden no decreciente? He oído que la respuesta es ${n + k - 1 \choose k}$ pero no sé cómo llegar a esa respuesta.

Gracias

Answer 1

Una pista:

Equivale a elegir $k$ números de $\{1,2,\dots,n\}$ y cada elección sólo tiene un orden no decreciente.

Entonces, se convierte en un estrellas y barras problema, cuya solución es $n+k-1 \choose k$ .

Answer 2

Haga un diagrama con $k$ columnas, cada una con un número de casillas determinado por la ranura correspondiente. A partir del punto $(0,1)$ la esquina superior izquierda del cuadro inferior de la primera columna (que debe estar presente porque no permite $0$ en una ranura), trazar un camino a lo largo de la parte superior de las columnas, y terminar en $(k,n)$ (así que después de haber cruzado la última columna sube al nivel $n$ si la última columna no ha alcanzado ya ese nivel). Entonces, por la condición de incremento débil, el camino sólo tiene pasos hacia la derecha y hacia arriba, y cualquier camino de $(0,1)$ a $(k,n)$ con solo pasos hacia la derecha y hacia arriba determinará un llenado de las ranuras.

Siempre hay $k$ hacia la derecha y $n-1$ pasos hacia arriba. Del total de $k+n-1$ pasos puede elegir el $k$ pasos hacia la derecha en $\binom{k+n-1}k$ posibles formas.

Answer 3

Que los números, en orden no decreciente, sean $x_1,\dots,x_k$ . Ahora definiremos nuevas cantidades $y_1,\dots,y_{k+1}$ de la siguiente manera: $y_1=x_1-1$ , $y_i=x_i-x_{i-1}$ para $i=2,\dots,k$ y $y_{k+1}=n-x_k$ . Claramente los números $y_i$ son todos no negativos. Además,

$$\begin{align*} \sum_{i=1}^{k+1}y_i&=(x_1-1)+\sum_{i=2}^k(x_i-x_{i-1})+(n-x_k)\\ &=(x_1-1)+\sum_{i=2}^kx_i-\sum_{i=2}^kx_{i-1}+(n-x_k)\\ &=(x_1-1)+\sum_{i=2}^kx_i-\sum_{i=1}^{k-1}x_i+(n-x_k)\\ &=\sum_{i=1}^kx_i-\sum_{i=1}^{k-1}x_i+n-x_k-1\\ &=x_k+n-x_k-1\\ &=n-1\;. \end{align*}$$

Así, cada solución de su problema da lugar a una solución en enteros no negativos de la ecuación

$$y_1+y_2+\ldots+y_k+y_{k+1}=n-1\;.\tag{1}$$

No es difícil ver que esta correspondencia es reversible: dada la no negativa $y_i$ es fácil reconstruir el $x_i$ 's. Pero contando las soluciones en enteros no negativos a $(1)$ es un estándar estrellas y barras problema cuya solución es

$$\binom{n-1+(k+1)-1}{(k+1)-1}=\binom{n+k-1}k\;.$$

También se puede convertir en un problema de barras y estrellas alineando los números $1,2,\dots,n$ como las estrellas e imaginando la inserción de una barra inmediatamente delante de cada número de su conjunto. (Si un número aparece más de una vez, insertarás más de una barra inmediatamente antes de él). Hay $n$ lugares para insertar las barras, y se insertará $k$ barras, por lo que terminará con una cadena de $n+k$ estrellas y barras que tiene que terminar con una estrella. Por lo tanto, usted tiene que decidir qué $k$ de la primera $n+k-1$ posiciones obtienen barras, y puedes hacerlo en $$\binom{n+k-1}k$$ formas.