[rrrto2005]

Calcular el número de funciones monótonas de un conjunto totalmente ordenado de tamaño n a otro también de orden total de tamaño m. Alguna idea?

[Juan Pablo Sancho]

Una idea que seguramente esté mal, no se me ocurre nada mejor:
Primero tenemos que aceptar que \(  m \geq n  \).
La fórmula que me sale es:


\(  \sum_{i_0=1}^{m+1-n} \sum_{i_1=i_0+1}^{m+2-n} \sum_{i_2=i_1+1}^{m+3-n} \cdots \sum_{i_n =i_{n-1}+1}^{m} 1  \).   

[Juan Pablo Sancho]

Posiblemente sea:
\(  {\red Editado 2}  \).
MAL

Spoiler

\(  \sum_{i=1}^{m-n+1} \dfrac{(m+2-n-i)\cdot (m+3-n-i)}{2}  \).
\(  m \geq n  \).
Viendo la solución de soneu y después la de el manco no captaba la idea del uso  combinatorio, cuando he comprendido el concepto de dicho uso
quería morirme, el rato que he estado haciendo sumas a las tantas de la madrugada.

[cerrar]

MAL

[soneu]

Hola,

se trata de hallar todas las funciones monótonas \( f:\{1,\cdots, n\}\rightarrow \{1,\cdots, m\}. \)

Obviamente debe ser \( m\geq n. \) Comenzamos determinando el número de funciones inyectivas. Para que una función sea inyectiva su imagen debe estar formada por n números diferentes. Tenemos \( C_m^n \) formas de hacerlo. De todas las imágenes sólo dos están ordenadas (una creciente y otra decreciente). Por tanto, el número pedido es:

\( \displaystyle \frac{2C_m^n}{n!}=\frac{2\cdot m!}{(m-n)! n!^2}. \)

Saludos

[Luis Fuentes]

Hola

Obviamente debe ser \( m\geq n. \) Comenzamos determinando el número de funciones inyectivas. Para que una función sea inyectiva su imagen debe estar formada por n números diferentes. Tenemos \( C_m^n \) formas de hacerlo. De todas las imágenes sólo dos están ordenadas (una creciente y otra decreciente). Por tanto, el número pedido es:

\( \displaystyle \frac{2C_m^n}{n!}=\frac{2\cdot m!}{(m-n)! n!^2}. \)

Realmente no estás contando las funciones inyectivas (serían las variaciones y no las combinaciones) sino directamente las imágenes de las funciones inyectivas. Entonces el resultado sería simplemente:

\( 2C_m^n=2\displaystyle\binom{m}{n}=\dfrac{2m!}{n!(m-n)!} \)

Saludos.

P.D. De hecho \( \displaystyle \frac{2C_m^n}{n!} \) ni siquera da un número entero en general. Por ejemplo:

\( \dfrac{2C_5^3}{3!}=\dfrac{20}{6}=\dfrac{10}{3} \)

[soneu]

Hola,

gracias el_manco por la corrección.

Saludos

[rrrto2005]

La verdad es que me faltó definir lo que era monótona. Al parecer la definición que ustedes manejan era \( a\leq{b}\Longleftrightarrow{f(a)\leq{f(b)}} \)  lo cual se deducía que era una función inyectiva. La definición de monotonía del problema era: \( a\leq{b}\Longrightarrow{f(a)\leq{f(b)} \). Entonces contar los subconjuntos de m en n elementos como que ya no funciona, no?

[Luis Fuentes]

Hola

La verdad es que me faltó definir lo que era monótona. Al parecer la definición que ustedes manejan era \( a\leq{b}\Longleftrightarrow{f(a)\leq{f(b)}} \)  lo cual se deducía que era una función inyectiva. La definición de monotonía del problema era: \( a\leq{b}\Longrightarrow{f(a)\leq{f(b)} \). Entonces contar los subconjuntos de m en n elementos como que ya no funciona, no?

Si, nosotros (soneu y yo) calculamos las funciones estrictamente monótonas.

Para modificar el argumento ten en cuenta que la imagen de una función monótona consiste en elegir \( n \) elementos entre las \( m \) posibles imágenes pudiendo repetir pero sin importar el orden. Son combinaciones con repetetición de \( m \) tipos de elementos tomados de \( n \) en \( n \):

\( \displaystyle\binom{m+1-n}{n} \)

Entonces:

- el número de funciones monótonas crecientes sería \( \displaystyle\binom{m+1-n}{n} \)

- el número de funciones monótonas decrecientes sería \( \displaystyle\binom{m+1-n}{n} \)

- el número de funciones monótonas (decrecientes o crecientes) sería: \( 2\displaystyle\binom{m+1-n}{n}-m \) (descontamos las constantes porque son simultáneamente crecietnes y decrecientes y las contaríamos dos veces).

Saludos.

[rrrto2005]

Ya entendí. Solo basta usar un conjunto con repeticiones. Muchas gracias