Ensino MédioFunção Sobrejetora Tópico resolvido

Problemas sobre assuntos estudados no Ensino Médio devem ser postados aqui. Se o problema for de Vestibular, poste-o no fórum Pré-Vestibular

Moderador: [ Moderadores TTB ]

Avatar do usuário
Autor do Tópico
snooplammer
4 - Sabe Tudo
Mensagens: 1701
Registrado em: Seg 24 Out, 2016 14:18
Última visita: 23-03-24
Jan 2020 14 23:59

Função Sobrejetora

Mensagem não lida por snooplammer »

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?

Última edição: snooplammer (Qua 15 Jan, 2020 00:01). Total de 1 vez.



Avatar do usuário
csmarcelo
6 - Doutor
Mensagens: 5114
Registrado em: Sex 22 Jun, 2012 22:03
Última visita: 17-04-23
Jan 2020 15 09:56

Re: Função Sobrejetora

Mensagem não lida por csmarcelo »

Seria [tex3]A^n_m\cdot m^{n-m}[/tex3] , com [tex3]n\geq m[/tex3] ?




Avatar do usuário
csmarcelo
6 - Doutor
Mensagens: 5114
Registrado em: Sex 22 Jun, 2012 22:03
Última visita: 17-04-23
Jan 2020 15 10:03

Re: Função Sobrejetora

Mensagem não lida por csmarcelo »

Não, não é... deixa eu pensar um pouco mais...



Avatar do usuário
Autor do Tópico
snooplammer
4 - Sabe Tudo
Mensagens: 1701
Registrado em: Seg 24 Out, 2016 14:18
Última visita: 23-03-24
Jan 2020 15 11:33

Re: Função Sobrejetora

Mensagem não lida por snooplammer »

csmarcelo, também tem que perceber que pra n=m e n>m tem duas respostas diferentes.



Avatar do usuário
jrneliodias
5 - Mestre
Mensagens: 2578
Registrado em: Sáb 16 Jun, 2012 17:15
Última visita: 23-05-22
Localização: Belém - PA
Jan 2020 15 15:56

Re: Função Sobrejetora

Mensagem não lida por jrneliodias »

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 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\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! :lol:
Última edição: jrneliodias (Qua 15 Jan, 2020 15:59). Total de 1 vez.


Para alcançar um objetivo, não procure motivação, busque a disciplina. Ela que irá fazer você levantar todos os dias para realizar seus sonhos. A motivação é o resultado, é o que sente no final do dia, quando deitar sua cabeça no travesseiro.

Avatar do usuário
Autor do Tópico
snooplammer
4 - Sabe Tudo
Mensagens: 1701
Registrado em: Seg 24 Out, 2016 14:18
Última visita: 23-03-24
Jan 2020 15 18:35

Re: Função Sobrejetora

Mensagem não lida por snooplammer »

A ideia era essa mesma, jrneliodias. Faltou um [tex3](-1)^{m-1}[/tex3] ali no último termo, mas a ideia era essa.




Responder
  • Tópicos Semelhantes
    Respostas
    Exibições
    Última msg

Voltar para “Ensino Médio”