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