¿Cuántas secuencias no decrecientes hay de longitud$M$, siempre que el número en las secuencias se permita desde$1,2,3,...,N$?
Respuestas
¿Demasiados anuncios?
karthick
Puntos
111
La elaboración de user2255279's respuesta:
Para $k=1,2,3 \cdots N$, vamos a $k$ aparecer $n_k$ número de veces que en un determinado permitió $M$ de la longitud de la secuencia.
Ya que queremos que la $M$ de la longitud de la secuencia no decreciente, $n_1$ número de $1$s tienen que aparecer en el inicio de la secuencia, seguido por $n_2$ número de $2$s y así sucesivamente. Así el conjunto de los números $n_k$ únicamente determina una secuencia.
Por lo que sigue siendo para contar el número de conjuntos de $n_k$s. La única restricción es la longitud de la secuencia es $M$.
Por lo tanto el número de entero no negativo soluciones a $n_1 + n_2 + \cdots + n_N = M$ es la respuesta a su pregunta. Por las estrellas y las barras, la respuesta es $\binom{N+M-1}{M}$.
Abhra Abir Kundu's respuesta coincide con lo anterior, si usted escribe $\dbinom{M-1}{r-1}$ $\dbinom{M-1}{M - r}$ y, a continuación, el uso de Vandermonde de la identidad.
Saludos!
Abhra Abir Kundu
Puntos
6773
La respuesta es $\displaystyle \sum_{r=1}^{M}{N \choose r}{M-1 \choose r-1}$
La razón como sugerencias:
Sugerencia 1:cuántos números pueden estar allí?Puede ser $>$ M ?
Sugerencia 2:Considere la posibilidad de seleccionar algunas $M$ números de la serie dada .Cuántas secuencias distintas se pueden formar con ella?
Sugerencia 3:Para cada conjunto de distintas $r$ números con $(r\le ...)$ ¿cuántas $M$ denominado secuencias puede formar de esta $r$ distintos números.(Deje $p_1,p_2,\dots p_r$ ser los números seleccionados y dejar que cada una de las $p_i$ ocurren $x_i\ge 1$ veces luego tenemos a $x_i+x_2+x_3\dots +x_r=M$.Ahora piense en el número de soluciones de esta ecuación.)
También tenemos,
$\displaystyle \sum_{r=1}^{M}{N \choose r}{M-1 \choose r-1}={N+M-1 \choose N-1}={N+M-1 \choose M}$(por qué?)
freethinker
Puntos
283
Anton
Puntos
3129
