Ensino Médio

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?

Mensagem não lida por **csmarcelo** » 15 Jan 2020, 09:56

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

Mensagem não lida por **csmarcelo** » 15 Jan 2020, 10:03

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

15 Jan 2020, 11:33

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

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 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!

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.

Ensino Médio ⇒ Função Sobrejetora Tópico resolvido

Função Sobrejetora

Re: Função Sobrejetora

Re: Função Sobrejetora

Re: Função Sobrejetora

Re: Função Sobrejetora

Re: Função Sobrejetora

Crie uma conta ou entre para participar dessa discussão

Crie uma nova conta

Entrar

Ensino Médio ⇒ Função Sobrejetora Tópico resolvido

Função Sobrejetora

Re: Função Sobrejetora

Re: Função Sobrejetora

Re: Função Sobrejetora

Re: Função Sobrejetora

Re: Função Sobrejetora

Crie uma conta ou entre para participar dessa discussão

Crie uma nova conta

Entrar

EntrarcRegistrar