Número finito de secuencias monótonas

Question

Deje $X = \{1, 2,\ldots ,n\}, n\in\mathbb{N}$. Encontrar el número de $f: X\to X$ tal que $f$ es monótona y yo.e $$i<j\Longrightarrow f(i)\leq f(j)$$

Dicho de otra manera, encontrar el número de la monotonía secuencias finitas. Contando con ellos es tan doloroso incluso para $n=5$, para que el principio es fácil...

Si $f(1)=5$, sólo hay una manera: $f(j)=5$ por cada $j$.
Si $f(1) = 4$, luego comienza a depender de las siguientes opciones. $f$ ni siquiera tiene que ser en.

Este será sin duda un dolor de cabeza, por lo que yo estaba esperando para hacer el razonamiento inductivo/recursiva (de alguna manera).
Si $1\mapsto 5$, 1 posibilidad.

Si $1\mapsto 4$, luego nos permitir $f(2)\in\{4,5\}$
Ya tenemos ($k$) cuatro elementos de la izquierda a la mapa, obtenemos un total de $5$ posibilidades de hacerlo [contados manualmente desde diagrama]. ($k+1$?).

Si $1\mapsto 3$$2\mapsto 5$, 1 posibilidad.
Si $1\mapsto 3$$2\mapsto 4$, luego $f(3)\in\{4,5\}$. $4$ posibilidades hipótesis (resultado, tal vez?).
Si $1\mapsto 3$$2\mapsto 3$,$f(3)\in\{3,4,5\}$:

Perdido la esperanza en este punto. Puedo aplicar el resultado por set con 2 elementos de forma recursiva, pero todavía sería necesario volver a calcular las posibilidades para establecer con $3$ elementos y, a continuación, $4$ el etc$\ldots$

¿Hay consejos/sugerencias sobre cómo, tal vez, simplificar el recuento?

Answer 1

Dado $n$ números elegidos de $\{1,...,n\}$ sólo hay una manera de ponerlos en la monotonía orden creciente. Por lo tanto, no es un bijection entre el conjunto de funciones de $f$ que estás buscando y el número de tamaño de $n$ subconjuntos de a $\{1,...,n\}$ con repeticiones permitidas.

Por lo tanto la respuesta es

$${2n-1 \choose n}.$$

Answer 2

Sugerencia No es un bijection entre el conjunto y el conjunto fo estrictamente creciente de las funciones de $ g: \{1,2,.., n\} \to \{2,3,.., 2n\}$ que son estrictamente creciente dada por $$g(k)=f(k)+k$$