Dejar $S = \{1,2,3,4\}$. ¿Cuántas funciones de aumento monótono no estricto$f:S\to S$ hay?

Question

Dejar $S = \{1,2,3,4\}$. Deje que$f:S\to S$ sea una función tal que$f(x) \le f(y)$ si$x<y$. ¿Cuántos tales$f$ hay?

¿Cómo debo proceder? $f(1)$ tiene$4$ opciones. Pero el número de valores posibles de$f(2)$ depende de$f(1)$. Por ejemplo, si$f(1) =1$ entonces$f(2)$ puede ser$1,2,3,4$. Pero si$f(1)=2$, entonces$f(2)$ no puede ser$1$.

Answer 1

División de los casos según el rango de $f$. Si el rango de $f$ tiene cuatro elementos, sólo tenemos la función identidad. Si el rango de $f$ tiene tres elementos $a<b<c$, $f$ tiene tres tipos diferentes, de acuerdo a $(1,2,3,4)$ que se asigna a $(a,a,b,c),(a,b,b,c)$ o $(a,b,c,c)$. De ello se sigue que tenemos $12$ débilmente creciente en función de$S$$S$, de tal manera que $|f(S)|=3$. Si el rango de $f$ tiene sólo dos elementos $a<b$, tenemos tres tipos, de acuerdo a $(1,2,3,4)$ que se asigna a $(a,a,a,b),(a,a,b,b)$ o $(a,b,b,b)$, por lo tanto $18$ funciones. Si el rango de $f$ tiene un solo elemento, tenemos cuatro funciones. Resumiendo, la respuesta es dada por $$ 1+12+18+4 = \color{red}{35} = \binom{7}{3}.$$ Este número es también la suma de los coeficientes de $1,x,x^2,x^3$$(1+x+x^2+x^3)^4$, no por casualidad. ¿Puede usted imaginar ¿por qué?

Answer 2

El número de no-disminución de las funciones está totalmente determinado por el número de veces que cada elemento se produce en el rango. Por ejemplo, si $1$ se produce una vez, $2$ se produce dos veces, y $4$ se produce una vez, entonces el requisito de que la función no es la disminución de las fuerzas de $f(1) = 1$, $f(2) = f(3) = 2$, y $f(4) = 1$.

Deje $x_k$ ser el número de veces que el entero $k$ aparece en la gama. El número de no-disminución de las funciones de $f:\{1, 2, 3, 4\} \to \{1, 2, 3, 4\}$ es el número de soluciones de la ecuación $$x_1 + x_2 + x_3 + x_4 = 4$$ en los enteros no negativos. Una solución particular corresponde a la colocación de tres, además de los signos en una fila de cuatro. Por ejemplo, $$1 + 1 1 + + 1$$ corresponde a la solución $x_1 = 1$, $x_2 = 2$, $x_3 = 0$, y $x_4 = 4$ (y la función dada anteriormente), mientras que $$1 + 1 + 1 + 1$$ corresponde a la solución de $x_1 = x_2 = x_3 = x_4 = 1$ (y la identidad de la función $f(x) = x$). El número de este tipo de soluciones es igual al número de formas en que podemos seleccionar el que tres de los siete símbolos (cuatro y tres, además de signos) son, además de los signos, que es $$\binom{4 + 3}{3} = \binom{7}{3} = 35$$