Função Sobrejetora
Enviado: Ter 14 Jan, 2020 23:59
Sejam [tex3]A=\{x_1,x_2,x_3,\dots,x_n\}[/tex3]
e [tex3]B=\{y_1,y_2,y_3,\dots,y_m\}[/tex3]
, qual a quantidade de funções de A em B que sejam sobrejetoras?
Fórum TutorBrasil - Matemática, Português, Física, Química e Biologia
Fórum de Matemática, Português, Física, Química e Biologia para o vestibular, ensinos fundamental, médio e superior, concursos públicos e olimpíadas.
https://www.tutorbrasil.com.br/forum/
Função Sobrejetora
https://www.tutorbrasil.com.br/forum/viewtopic.php?f=3&t=78660
Página 1 de 1
Re: Função Sobrejetora
Enviado: Qua 15 Jan, 2020 09:56
Seria [tex3]A^n_m\cdot m^{n-m}[/tex3]
, com [tex3]n\geq m[/tex3]
?
Re: Função Sobrejetora
Enviado: Qua 15 Jan, 2020 10:03
Não, não é... deixa eu pensar um pouco mais...
Re: Função Sobrejetora
Enviado: Qua 15 Jan, 2020 11:33
csmarcelo, também tem que perceber que pra n=m e n>m tem duas respostas diferentes.
Re: Função Sobrejetora
Enviado: Qua 15 Jan, 2020 15:56
Olá, pessoal.
Para ficar mais fácil, vamos fazer um exemplo menor para depois generalizarmos. Seja [tex3]A=\{1,\,2,\,3,\,4,\,5\}[/tex3] e [tex3]B=\{a,\,b,\,c, \,d\}[/tex3] , podemos calcular o número de funções sobrejetoras calculando o número de funções possíveis e retirar as funções que não são sobrejetoras. Assim, para uma função não ser sobrejetora, devemos excluir um subconjunto de [tex3]B[/tex3] da imagem da função. Para isso, primeiro, excluímos [tex3]1[/tex3] elemento de cada vez e calculamos todas as funções possíveis, em seguida, excluímos [tex3]2 [/tex3] elementos até chegar o caso que excluímos [tex3]m-1[/tex3] elementos.
Nesse exemplo, o número total de funções é [tex3]4^5[/tex3] . Agora, temos que subtrair as funções que se relacionam om subconjuntos de [tex3]B[/tex3] . No primeiro caso, começamos com [tex3]1[/tex3] elemento, ou seja, , temos [tex3]4[/tex3] possibilidades e para cada uma delas, temos uma função. Assim, temos 4 funções não sobrejetoras que se relacionam apenas com um elemento.
Após isso, calcula-se o número de funções que se associam em subconjuntos de B com 2 elementos. Para esse caso, temos [tex3]4\choose 2[/tex3] subconjuntos e temos [tex3]2^5[/tex3] funções para cada um deles. Entretanto, estamos contando duas vezes algumas funções, pois para um subconjunto com [tex3]\{a,\,b\}[/tex3] , o [tex3]2^5[/tex3] contou funções que só se associam exclusivamente com [tex3]a[/tex3] e com [tex3]b[/tex3] , ou seja, funções que já foram contadas no caso anterior. Assim, o número de funções que se conectam com exatamente 2 elementos é
[tex3]{4\choose 3}{3\choose 2}=\frac{2\,!}{1\,!\,(2-1)!}{4\choose 2}=2{4\choose 2}[/tex3]
[tex3]{4\choose 3}{3\choose 1}=\frac{3\,!}{1\,!\,(3-1)!}{4\choose 1}=3{4\choose 1}[/tex3]
Além disso, [tex3]4 = {4\choose1}[/tex3] , então chegamos a
Espero ter ajudado. Abraço.
Deu um trabalhão!
Para ficar mais fácil, vamos fazer um exemplo menor para depois generalizarmos. Seja [tex3]A=\{1,\,2,\,3,\,4,\,5\}[/tex3] e [tex3]B=\{a,\,b,\,c, \,d\}[/tex3] , podemos calcular o número de funções sobrejetoras calculando o número de funções possíveis e retirar as funções que não são sobrejetoras. Assim, para uma função não ser sobrejetora, devemos excluir um subconjunto de [tex3]B[/tex3] da imagem da função. Para isso, primeiro, excluímos [tex3]1[/tex3] elemento de cada vez e calculamos todas as funções possíveis, em seguida, excluímos [tex3]2 [/tex3] elementos até chegar o caso que excluímos [tex3]m-1[/tex3] elementos.
Nesse exemplo, o número total de funções é [tex3]4^5[/tex3] . Agora, temos que subtrair as funções que se relacionam om subconjuntos de [tex3]B[/tex3] . No primeiro caso, começamos com [tex3]1[/tex3] elemento, ou seja, , temos [tex3]4[/tex3] possibilidades e para cada uma delas, temos uma função. Assim, temos 4 funções não sobrejetoras que se relacionam apenas com um elemento.
Após isso, calcula-se o número de funções que se associam em subconjuntos de B com 2 elementos. Para esse caso, temos [tex3]4\choose 2[/tex3] subconjuntos e temos [tex3]2^5[/tex3] funções para cada um deles. Entretanto, estamos contando duas vezes algumas funções, pois para um subconjunto com [tex3]\{a,\,b\}[/tex3] , o [tex3]2^5[/tex3] contou funções que só se associam exclusivamente com [tex3]a[/tex3] e com [tex3]b[/tex3] , ou seja, funções que já foram contadas no caso anterior. Assim, o número de funções que se conectam com exatamente 2 elementos é
[tex3]{4\choose 2} (2^5-2)[/tex3]
Por fim, calculamos as funções que se ligam a exatamente 3 elementos, com esse intento, devemos criar subconjuntos com apenas 3 elementos, cuja quantidade será [tex3]{4\choose 3}[/tex3]
e das [tex3]3^5[/tex3]
funções, retirar as funções que se relacionam exatamente com 1 e 2 elementos, calculados nos casos anteriores. Assim, temos
[tex3]{4\choose 3}\left(3^5-3-{3\choose 2} (2^5-2)\right)={4\choose 3}\left(3^5-{3\choose 2} 2^5+{3\choose 2}2-3\right)={4\choose 3}\left(3^5-{3\choose 2} 2^5+{3\choose1}1^5\right)[/tex3]
Antes de continuar, uma propriedade importante que será usado na conta:
[tex3]{m\choose m-a}{m-a\choose m-b}=\frac{b\,!}{a\,!\,(b-a)!}{m\choose m-b}[/tex3]
Com isso, o número de funções sobrejetoras será o número de funções possíveis entre [tex3]A[/tex3]
e [tex3]B[/tex3]
subtraída da soma do total de funções se ligam a somente [tex3]1[/tex3]
, somente [tex3]2[/tex3]
e somente [tex3]3[/tex3]
elemento de [tex3]B[/tex3]
.[tex3]4^5-\left[{4\choose 3}\left(3^5-{3\choose 2} 2^5+{3\choose1}1^5\right)+{4\choose 2} (2^5-2)+4\right][/tex3]
[tex3]4^5-\left[{4\choose 3}3^5-{4\choose 3}{3\choose 2} 2^5+{4\choose 3}{3\choose1}1^5+{4\choose 2} 2^5-{4\choose 2}2+4\right][/tex3]
Pela propriedade mostrada, temos [tex3]4^5-\left[{4\choose 3}3^5-{4\choose 3}{3\choose 2} 2^5+{4\choose 3}{3\choose1}1^5+{4\choose 2} 2^5-{4\choose 2}2+4\right][/tex3]
[tex3]{4\choose 3}{3\choose 2}=\frac{2\,!}{1\,!\,(2-1)!}{4\choose 2}=2{4\choose 2}[/tex3]
[tex3]{4\choose 3}{3\choose 1}=\frac{3\,!}{1\,!\,(3-1)!}{4\choose 1}=3{4\choose 1}[/tex3]
Além disso, [tex3]4 = {4\choose1}[/tex3] , então chegamos a
[tex3]4^5-\left[{4\choose 3}3^5-{4\choose 2} 2^5+{4\choose 1}\right]=4^5-{4\choose 3}3^5+{4\choose 2} 2^5-{4\choose 1}1^5[/tex3]
Dessa forma, podemos notar um padrão nessa contagem e a generalização se dá por indução, visto que o caso para um conjunto de 3 elementos tem o mesmo padrão de 4 e sempre irá aparecer a propriedade mostrada acima. Logo, se [tex3]A[/tex3]
possuir [tex3]n[/tex3]
elementos e [tex3]B[/tex3]
possuir [tex3]m[/tex3]
, sendo [tex3]n\geq m[/tex3]
a quantidade de funções sobrejetoras será
[tex3]m^n-{m\choose m-1}(m-1)^n+{m\choose m-2}(m-2)^n-{m\choose m-3}(m-3)^n+\cdots +{m\choose 1}(1)^n[/tex3]
Para [tex3]n< m[/tex3]
não existe função sobrejetora.Espero ter ajudado. Abraço.
Deu um trabalhão!
Re: Função Sobrejetora
Enviado: Qua 15 Jan, 2020 18:35
A ideia era essa mesma, jrneliodias. Faltou um [tex3](-1)^{m-1}[/tex3]
ali no último termo, mas a ideia era essa.