Contar el número de funciones crecientes, funciones no decrecientes $f: \{1, 2, 3, \ldots, n\} \to \{1, 2, 3, \ldots, m\}$ con $m \geq n$ .

Question

Me encontré con una pregunta dada como:

Dejemos que $m$ y $n$ sean dos enteros tales que $m \geq n \geq 1$ .

Cuente el número de funciones $$f: \{1, 2, · · · , n\} \to \{1, 2, · · · , m\}$$ de los dos tipos siguientes:

(a) estrictamente creciente; es decir, siempre que $x < y, f(x) < f(y)$ y

(b) no decreciente, es decir, siempre que $x < y, f(x) \leq f(y)$ .

Lo he intentado de la siguiente manera.

Para (a). Podemos decir $f(n)>f(n-1)$ Y $f(n)>f(n-2) \ldots f(n)>f(1)$ (total $n-1$ elementos)

Del mismo modo, para $f(n-1)>f(n-2), f(n-1)>f(n-3) \ldots f(n-1)>f(1)$ (total $n-2$ elementos)...

y $f(2)>1$

Así $$(n-1) + (n-2) + \ldots + (1) = \frac{n(n-1)}{2}$$

¿Es esto correcto?

Para (b). Como hay igualdad, será $$n + (n-1) + ... (1) = \frac{n(n+1)}{2}$$

¿Es correcto mi planteamiento? Se agradece cualquier ayuda. Gracias de antemano.

Answer 1

Cuántas funciones estrictamente crecientes $f:\{1, 2, 3, \ldots, n\} \to \{1, 2, 3, \ldots, m\}$ ¿están ahí?

Una función $$f: \{1, 2, 3, \ldots, n\} \to \{1, 2, 3, \ldots, m\}$$ se determina por la forma en que los valores $$f(1), f(2), f(3), \ldots, f(n)$$ están asignados. Dado que $f$ es una función estrictamente creciente, $$f(1) < f(2) < f(3) < \ldots < f(n)$$ Así, para una función estrictamente creciente, cada valor del dominio se asigna a un elemento distinto del codominio. Dado que hay $n$ elementos en el dominio y $m$ elementos en el codominio, el número de formas en que podemos seleccionar los elementos en el rango es $\binom{m}{n}$ . Una vez que hemos seleccionado estos elementos, sólo hay una forma de asignarlos para que la función sea estrictamente creciente, es decir, asignando el elemento más pequeño del rango a ser $f(1)$ el siguiente más pequeño en ser $f(2)$ y así sucesivamente. Por lo tanto, el número de funciones estrictamente crecientes es $$\binom{m}{n}$$

¿Cuántas funciones no decrecientes $f: \{1, 2, 3, \ldots, n\} \to \{1, 2, 3, \ldots, m\}$ ¿están ahí?

Desde $f$ es una función no decreciente, la función está completamente determinada por cuántos valores de $j \in \{1, 2, 3, \ldots, n\}$ se asignan a igual $k \in \{1, 2, 3, \ldots, m\}$ . Para ver por qué, considere las funciones $$f: \{1, 2, 3, 4, 5\} \to \{1, 2, 3, 4, 5, 6, 7\}$$ Si se asignan dos valores iguales $3$ se asigna un valor igual a $4$ y se asignan dos valores iguales a $7$ Entonces, como $f$ no es decreciente, $f$ debe ser la función definida por $f(1) = f(2) = 3$ , $f(3) = 4$ , $f(4) = f(5) = 7$ .

Dejemos que $x_k$ , $1 \leq k \leq m$ sea el número de valores de $j \in \{1, 2, 3, \ldots, n\}$ tal que $f(j) = k$ . Entonces $$x_1 + x_2 + x_3 + \ldots + x_m = n$$ que es una ecuación en los enteros no negativos. Una solución particular corresponde a la colocación de $m - 1$ signos de adición en una fila de $n$ los.

Para concretar esto, consideremos funciones no decrecientes $$f: \{1, 2, 3, 4, 5\} \to \{1, 2, 3, 4, 5, 6, 7\}$$ Entonces tenemos $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 = 5$$ El encargo $$+ + 1 1 + 1 + + + 1 1$$ corresponde al ejemplo anterior que $x_1 = x_2 = 0$ , $x_3 = 2$ , $x_4 = 1$ , $x_5 = x_6 = 0$ y $x_7 = 2$ es decir, la función definida por $f(1) = f(2) = 3$ , $f(3) = 4$ , $f(4) = f(5) = 7$ . En este caso, el número de tales funciones es el número de maneras en que podemos insertar seis signos de adición en una fila de cinco unos, que es $$\binom{5 + 6}{6} = \binom{11}{6}$$ ya que debemos elegir qué seis de los once símbolos (cinco unos y seis signos de adición) serán signos de adición.

Por un razonamiento similar, el número de funciones no decrecientes $$f: \{1, 2, 3, \ldots, n\} \to \{1, 2, 3, \ldots, m\}$$ es igual al número de formas en que podemos insertar $m - 1$ signos de adición en una fila de $n$ que es $$\binom{n + m - 1}{m - 1}$$ ya que debemos seleccionar qué $m - 1$ de la $n + m - 1$ símbolos ( $n$ y $m - 1$ signos de adición) deben ser signos de adición.

Answer 2

Un enfoque diferente para el caso no decreciente.

Set $F(n,m) = |\{ f : \{1, \ldots, n\} \to \{1,\ldots,m\} \mid f \mbox{ is non-decreasing. } \}|$ . Entonces, $F(n,1) = 1$ . Además, tenemos la siguiente relación de recurrencia: $$ F(n,m) = \sum_{i=0}^n F(n - i, m - 1). \quad (*) $$ Prueba. Si $f : \{1,\ldots,n\} \to \{1,\ldots,m\}$ es no decreciente, configure $k = |f^{-1}(1)|$ . Entonces, $f^{-1}(1) = \{1,\ldots, k \}$ (posiblemente vacío) y $f$ restringido a $\{ k + 1, \ldots, n \}$ (también posiblemente vacía) podría verse como una función no decreciente de $\{k+1,\ldots,n\}$ a $\{2,\ldots,m-1\}$ . Para la restricción, tenemos $F(n - k, m - 1)$ muchas posibilidades (la denominación concreta de los números no importa, sólo que formen un orden consecutivo) y cada posibilidad se determina de forma única. A la inversa, a partir de cualquier función no decreciente $g : \{1,\ldots,n\}\to \{1,\ldots,m\}$ y $0 \le k \le n$ podemos construir de forma única una función no decreciente $f : \{1,\ldots,n+k\} \to \{1,\ldots, m+1\}$ al establecer $$ f(x) = \left\{ \begin{array}{ll} 1 & 1 \le x \le k \\ g(x) + 1 & \mbox{otherwise.} \end{array} \right. $$ Así, hemos mostrado la ecuación de recurrencia. QED

Ahora, para el coeficiente binomial, es válida la siguiente fórmula: $$ \binom{m}{m} + \binom{m + 1}{m} + \binom{m + 2}{m} + \ldots + \binom{m + n}{m} = \binom{n + m + 1}{m+1}, $$ que es fácil de demostrar por inducción. Estableciendo $$ G(n,m) = \binom{n + m - 1}{m-1}, $$ vemos que $G$ cumple la ecuación (*) anterior, y $G(n,1) = 1$ . Por lo tanto, inductivamente, $F(n,m) = G(n,m)$ .

Un ejemplo concreto. Sea $a < b < c$ entonces, las funciones no decrecientes con codominio de tamaño tres podrían interpretarse como cadenas ordenadas sobre $\{a,b,c\}$ . Entonces, para el dominio de tamaño tres, tenemos las cadenas $$ aaa, aab, aac, abb, abc, acc, bbb, bbc, bcc, ccc. $$ Espero que se pueda ver cómo construir estas cadenas a partir de las cadenas ordenadas sobre $\{b,c\}$ de una longitud máxima de tres, añadiendo series de $a$ 's frente a ellos.

Answer 3

El problema de su enfoque es que la función no puede asignar un número a varios números diferentes. Por otro lado, puedes asignar varios números diferentes a un número.