10 votos

Cuántos secuencia de enteros ($j_1 , j_2 , . . . , j_k$) están allí, que $0 ≤ j_1 ≤ j_2 ≤ . . . ≤ j_k ≤ n$?

Necesito solucionar el problema,

Cuántos secuencia de enteros ($j_1 , j_2 , . . . , j_k$) están ahí tal que $0 ≤ j_1 ≤ j_2 ≤ . . . ≤ j_k ≤ n$?

Me han dado un toque,

(Sugerencia: Reducir el problema a $0 < j_1 < j_2 < . . . < j_k < n)$.

La respuesta se dará en términos de k y n.

Primero de todo, no veo la manera de reducir el problema, o qué hacer cuando es reducida. En segundo lugar, me siento mal por no tener mucho que mostrar por mi esfuerzo, pero he estado trabajando en este problema durante algún tiempo, y no estoy seguro de por dónde empezar. Si alguien me podría dar una idea general de qué método usar o algo así, se lo agradecería.

6voto

Oli Puntos 89

Tenemos $k$ personas se alinearon en una fila, y $n$ idénticos a los caramelos. Vamos a regalar algunos o todos los caramelos a la gente, tal vez no dar caramelos a algunos de ellos, o tal vez incluso todos ellos. Y vamos a comer los dulces que están a la izquierda. Pensar de nuestro representante en el final de la fila; así, (s)él es el $(k+1)$-th persona.

Deje $j_1$ el número de caramelos que a la primera persona, $j_2$ el número de caramelos que da a las dos primeras personas, $j_3$ el número de caramelos que a la primera de tres personas, y así sucesivamente hasta el $j_k$. A continuación, la secuencia de las $j_1 \le j_2\le \cdots\le j_k\le n$ identifica de forma única un dulce regalo esquema, y por el contrario los dulces de regalo esquema genera una secuencia del tipo que nos interesa.

Entonces, nos preguntamos: ¿cuántas maneras hay para regalar $n$ caramelos a $k+1$ de la gente?

Hay un argumento estándar para esto, a menudo llamados Estrellas y Barras. Es más fácil visualizar regalando $n+k+1$ caramelos a $k+1$ de la gente, al menos uno para cada uno, y luego quitarle un caramelo de todo el mundo. Así que hay muchas maneras de distribuir $n$ caramelos entre los $k+1$ de la gente, con algunos posiblemente conseguir nada, ya que hay maneras de distribuir la $n+k+1$ caramelos entre los $k+1$ de la gente, con todo el mundo cada vez en menos $1$.

La línea de la $n+k+1$ caramelos, con un poco de hueco entre los sucesivos caramelos. Hay $n+k$ tales deficiencias. Poner $k$ separadores entre los dulces, y dar todos los caramelos hasta el primer separador a la primera persona, entonces todos los caramelos entre el primer separador y el siguiente a la segunda persona, y así sucesivamente. Hay $$\binom{n+k}{k}$$ maneras de elegir donde los separadores de ir.

4voto

Alex Bolotov Puntos 249

Considere la posibilidad de

$y_i = j_i + i$.

Muestran que el $y_i$ son distintos y en el rango de $1$$n+k$.

De cuántas maneras se puede elegir el $y$?

3voto

DiGi Puntos 1925

Aryabhata ya propuso un enfoque que utiliza la sugerencia. Creo que un enfoque algo diferente es más simple.

Deje $d_0=j_1$ $i=1,\dots,k-1$ deje $d_i=j_{i+1}-j_i$, y deje $d_k=n-j_k$. Los números de $d_0,\dots,d_k$ son no negativos, y $d_0+d_1+\dots+d_k=n$.

Por el contrario, si $\langle d_0,\dots,d_k\rangle$ cualquier $(k+1)$-tupla de enteros no negativos cuya suma es $n$, podemos definir a la $j_1=d_0$$j_{i+1}=d_i+j_i$$i=1,\dots,k-1$, y el $k$-tupla $\langle j_1,\dots,j_k\rangle$ claramente satisface la condición de $$0\le j_1\le j_2\le \dots\le j_k\le n\;.$$

Por lo tanto, sólo es necesario contar el $(k+1)$-tuplas $\langle d_0,\dots,d_k\rangle$ de los enteros no negativos tales que $$\sum_{i=0}^kd_i=n\;,$$, que es un problema estándar.

1voto

GmonC Puntos 114

Considere la posibilidad de rutas de $(0,0)$ $(k,n)$que el aumento de uno de los dos componentes en cada paso, así que son los $n+k$ pasos, entre los que se $k$ horizontal (aumento de la $i$$(i,j)$) y $n$ vertical (aumento de la $j$).

Hay $\binom{n+k}k$ rutas de acceso.

Deje que el primer punto con la primera coordenada $i$$(i,j_i)$$i=1,\ldots,k$, entonces claramente $0\leq j_1\leq\cdots\leq j_k\leq n$. Por otra parte, todas estas secuencias de valores permitidos, y determinar la ruta de acceso: el horizontal pasos son, precisamente, los de$(i-1,j_i)$$(i,j_i)$$i=1,\ldots,k$.

Otros puntos de vista. Si usted toma $y_i$ a ser el índice de la horizontal paso a $(i,j_i)$ entre todos los pasos (que son numeradas de $1$$n+k$), se obtendrá su $0<y_1<\cdots<y_k\leq n+k$. Si ponen un caramelo (star) en cada punto de $(i,j)$ de la ruta de acceso y el pensar de cada uno horizontal, el paso de una separación (bar), tendrá que dividir su $n+k+1$ caramelos en $k+1$ vertical grupos ( $i=0,1,\ldots,k$ ) el último grupo $i=k$ siendo las sobras. Pero en realidad desea que cada grupo para tener tantos caramelos como se ha vertical pasos, no los puntos, por lo que eliminar uno de cada grupo para corregir este poste del cerco de error, dejando a los grupos verticales de los pasos de los tamaños de las $d_0,d_1,\ldots,d_k$ (cada una de las $d_i\geq0$)$d_0+\cdots+d_k=n$. En la final que bien podría tomar $n+k$ pasos, elija $k$ de ellos a ser horizontal (barras) y el resto de $n$ a ser vertical (de las estrellas). Pero creo que ya he dicho algo parecido al principio.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X