Autor Tema: Número de aplicaciones con imagen de cardinalidad dada

0 Usuarios y 1 Visitante están viendo este tema.

20 Mayo, 2021, 11:06 pm
Leído 109 veces

carambola

  • $$\Large \color{#5372a0}\pi\,\pi$$
  • Mensajes: 73
  • País: es
  • Karma: +0/-0
Sean $$A$$ y $$B$$ conjuntos de cardinal $$n$$ y $$m$$, resoectivamente. Cuantas aplicaciones hay de $$A$$ a $$B$$ tal que su conjunto imagen tenga cardinal $$k$$ (suponed que $$k \leq{n,m}$$)


Gracias!!

21 Mayo, 2021, 08:54 am
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 49,577
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Sean $$A$$ y $$B$$ conjuntos de cardinal $$n$$ y $$m$$, resoectivamente. Cuantas aplicaciones hay de $$A$$ a $$B$$ tal que su conjunto imagen tenga cardinal $$k$$ (suponed que $$k \leq{n,m}$$)

Llama \( A(n,k) \) al número de aplicaciones sobreyectivas de un conjunto de cardinal \( n \) sobre uno de cardinal \( k \). Dado que el conjunto \( B \) tiene \( \displaystyle\binom{m}{k} \) posibles subconjuntos de k elementos, el número total de aplicaciones en las condiciones que buscas es:

\( \displaystyle\binom{m}{k}A(n,k) \)

Ahora es un resultado bastante conocido que:

\( A(n,k)=\displaystyle\sum_{k=0}^n(-1)^k\displaystyle\binom{n}k(n-k)^m. \)

La idea de esta fórmula es:

1) Hay \( n^k \) aplicaciones de un conjunto de \( n \) elementos en otro de \( k \) elementos.

2) Como nos interesan las sobreyectivas le restamos las que han dejado al menos un elemento fuera de la imagen. Hay \( \displaystyle\binom{n}1 \) formas de elegir ese elemento y una vez elegido \( n^{k-1} \) aplicaciones posibles.

\( -\displaystyle\binom{n}1n^{k-1} \)

3) Pero hemos restado dos veces el número de aplicaciones que deja fuera un par de elementos dado. Por ejemplos las que dejan fuera de la imagen el \( 1 \) y el \( 2 \) las hemos contado como las que dejan fuera el \( 1 \) y después como las que dejan fuera el \( 2 \). Entonces se las volvemos a sumar. Las formas de elegir pares de elementos son \( \displaystyle\binom{n}2 \) y una vez elegido \( n^{k-2} \) aplicaciones posibles.

\( +\displaystyle\binom{n}2n^{k-2} \).

Reiterando el argumento usando el principio de inclusión exclusión se obtiene el resultado.

Saludos.

21 Mayo, 2021, 08:54 am
Respuesta #2

Fernando Revilla

  • Es más fácil engañar a alguien que convencerle de que ha sido engañado.
  • Administrador
  • Mensajes: 11,526
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
  • Las matemáticas son demasiado humanas (Brouwer).
    • Fernando Revilla
Sean $$A$$ y $$B$$ conjuntos de cardinal $$n$$ y $$m$$, resoectivamente. Cuantas aplicaciones hay de $$A$$ a $$B$$ tal que su conjunto imagen tenga cardinal $$k$$ (suponed que $$k \leq{n,m}$$)

Existen \( \displaystyle\binom{m}{k} \) subconjuntos de \( B \) con \( k \) elementos. Si \( B_1 \) es uno de estos subconjuntos, y \( S_{A,B_1} \) es el conjunto de las aplicaciones sobreyecivas de \( A \) en \( B_1 \), entonces la solución al problema es \( \displaystyle\binom{m}{k}\cdot \text{card}\left(S_{A,B_1}\right) \). Para hallar \( \text{card}\left(S_{A,B_1}\right) \) mira Number of onto functions.

P.D. Luis se adelantó por algún nanosegundo.