[laurasanchez]

Hola, sean \( A \), \( B \) dos conjuntos tales que \( |A|=n \), \( |B|=k \), \( k<n \), me piden,
(a) Demostrar que el número de aplicaciones sobreyectivas \( f:A\rightarrow{}B \) es
\( \displaystyle\sum_{j=0}^{k-1}{}(-1)^j\displaystyle\binom{k}{j}(k-j)^n \)
(b) ¿Qué ocurre si \( k=n \)?


Para (a) he utilizado el complementario: las aplicaciones que no sean sobreyectivas, o bien se saltarán el elemento 1, o bien el 2, etc., así hasta el k. Así que, si defino los conjuntos
\( A_{j}= \)\( \{ \)aplicaciones \( A\rightarrow{}B \) que se saltan el elemento j\( \} \), para cada \( j=1,...,k \),
el número de aplicaciones sobreyectivas resulta ser \( k^n-|A_{1}\cup A_{2}\cup ... \cup A_{k}| \)
Calculo, en primer lugar, el tamaño de cada uno de los \( A_{j} \). Una aplicación que esté en \( A_{j} \) no toma el valor \( j \) como imagen. En términos de listas, es una n-lista en la que podemos utilizar cualquier elemento de B menos el símbolo \( j \). Esto nos dice que
\( |A_{j}|=(k-1)^n \), para cada \( j=1,...,k \).
Si una aplicación está en \( A_{i}\cap A_{j} \), entonces no tomará como imagen ni a i ni a j. Es decir, la lista correspondiente se formará con cualesquiera de los otros\(  k-2 \) símbolos. Por tanto,
\( |A_{i}\cap A_{j}|=(k-2)^n \), para cada \( i\not=j \).
El mismo argumento para las intersecciones tres a tres, cuatro a cuatro, etc. Como el número de sumandos en cada suma de la expresión del principio de inclusión/exclusión viene dado por un coeficiente binómico, se tiene que, si \( |A|=n \) y \( |B|=k \), con \( n\geq{k} \),
El número de aplicaciones sobreyectivas de \( A\rightarrow{}B \) es
\( k^n-|A_{1}\cup A_{2}\cup ... \cup A_{k}|= \)
\( =k^n-\left[\displaystyle\binom{k}{1}(k-1)^n-\displaystyle\binom{k}{2}(k-2)^n+...\pm \displaystyle\binom{k}{k}(k-k)^n\right]= \)
\( =\displaystyle\sum_{j=0}^{k-1}{}(-1)^j\displaystyle\binom{k}{j}(k-j)^n \)
Mi pregunta es sobre el apartado (b), qué hay de diferente con (a), el caso en que \( k=n \) se podría utilizar también lo visto en (a).? El número de aplicaciones sobreyectivas debería de ser \( n! \), ya que una vez que he fijado la imagen del primer elemento(n posibles) tengo n-1 para el segundo, n-2 para el tercero y así sucesivamente.

Muchas gracias, un saludo.

[Luis Fuentes]

Hola

Hola, sean \( A \), \( B \) dos conjuntos tales que \( |A|=n \), \( |B|=k \), \( k<n \), me piden,
(a) Demostrar que el número de aplicaciones sobreyectivas \( f:A\rightarrow{}B \) es
\( \displaystyle\sum_{j=0}^{k-1}{}(-1)^j\displaystyle\binom{k}{j}(k-j)^n \)
(b) ¿Qué ocurre si \( k=n \)?


Para (a) he utilizado el complementario: las aplicaciones que no sean sobreyectivas, o bien se saltarán el elemento 1, o bien el 2, etc., así hasta el k. Así que, si defino los conjuntos
\( A_{j}= \)\( \{ \)aplicaciones \( A\rightarrow{}B \) que se saltan el elemento j\( \} \), para cada \( j=1,...,k \),
el número de aplicaciones sobreyectivas resulta ser \( k^n-|A_{1}\cup A_{2}\cup ... \cup A_{k}| \)
Calculo, en primer lugar, el tamaño de cada uno de los \( A_{j} \). Una aplicación que esté en \( A_{j} \) no toma el valor \( j \) como imagen. En términos de listas, es una n-lista en la que podemos utilizar cualquier elemento de B menos el símbolo \( j \). Esto nos dice que
\( |A_{j}|=(k-1)^n \), para cada \( j=1,...,k \).
Si una aplicación está en \( A_{i}\cap A_{j} \), entonces no tomará como imagen ni a i ni a j. Es decir, la lista correspondiente se formará con cualesquiera de los otros\(  k-2 \) símbolos. Por tanto,
\( |A_{i}\cap A_{j}|=(k-2)^n \), para cada \( i\not=j \).
El mismo argumento para las intersecciones tres a tres, cuatro a cuatro, etc. Como el número de sumandos en cada suma de la expresión del principio de inclusión/exclusión viene dado por un coeficiente binómico, se tiene que, si \( |A|=n \) y \( |B|=k \), con \( n\geq{k} \),
El número de aplicaciones sobreyectivas de \( A\rightarrow{}B \) es
\( k^n-|A_{1}\cup A_{2}\cup ... \cup A_{k}|= \)
\( =k^n-\left[\displaystyle\binom{k}{1}(k-1)^n-\displaystyle\binom{k}{2}(k-2)^n+...\pm \displaystyle\binom{k}{k}(k-k)^n\right]= \)
\( =\displaystyle\sum_{j=0}^{k-1}{}(-1)^j\displaystyle\binom{k}{j}(k-j)^n \)
Mi pregunta es sobre el apartado (b), qué hay de diferente con (a), el caso en que \( k=n \) se podría utilizar también lo visto en (a).? El número de aplicaciones sobreyectivas debería de ser \( n! \), ya que una vez que he fijado la imagen del primer elemento(n posibles) tengo n-1 para el segundo, n-2 para el tercero y así sucesivamente.

Todo lo que dices está bien.

Lo que ocurre es que cuando \( k=n \) se cumple que:

\( \displaystyle\sum_{j=0}^{n-1}{}(-1)^j\displaystyle\binom{n}{j}(n-j)^n=n! \)

Lo puedes probar por inducción.

Saludos.

[laurasanchez]

Hola, me estoy liando al probarlo
Veo que se cumple para \( n=1 \)
\( \displaystyle\sum_{j=0}^{1-1}(-1)^j\displaystyle\binom{1}{j}(1-j)^{1}=1! \)
Pero ahora tengo que ver que suponiendo cierto para n=k\( \Rightarrow{} \) cierto para n=k+1.
Entonces se tiene:
\( (-1)^{0}\displaystyle\binom{k}{0}(k-0)^k+(-1)^{1}\displaystyle\binom{k}{1}(k-1)^k+(-1)^{2}\displaystyle\binom{k}{2}(k-2)^k+...+(-1)^{k-1}\displaystyle\binom{k}{k-1}(k-k+1)^k=k! \)
He de ver que implica que se cumple:
\( \displaystyle\sum_{j=0}^k{}(-1)^j\displaystyle\binom{k+1}{j}(k+1-j)^k=(k+1)! \)
\( (-1)^{0}\displaystyle\binom{k+1}{0}(k+1)^k+(-1)^{1}\displaystyle\binom{k+1}{1}(k)^k+(-1)^{2}\displaystyle\binom{k+1}{2}(k-1)^k+...+(-1)^{k}\displaystyle\binom{k+1}{k}(1)^k=(k+1)! \)

[Luis Fuentes]

Hola

Pensé que salía sencillo por inducción, pero ahora no lo veo.

Realmente el propio argumento de todo el ejercicio es una demostración de la igualdad.

Es decir en el primer apartado has demostrado que el número de aplicaciones sobreyectivas de un conjunto de \( n \) elementos en otro de \( k \) es:

\( f(n,k)=\displaystyle\sum_{j=0}^{k-1}{}(-1)^j\displaystyle\binom{k}{j}(k-j)^n \)

Por otra parte también sabemos que si \( k=n \) las aplicaciones sobreyectivas coinciden con las biyectivas y estas son \( n! \).

Entonces se deduce que:

\( n!=f(n,n)=\displaystyle\sum_{j=0}^{n-1}{}(-1)^j\displaystyle\binom{n}{j}(n-j)^n \)

Saludos.

[laurasanchez]

Entendido, muchas gracias por la ayuda.