• Anúncio Global
    Respostas
    Exibições
    Última mensagem

Problema de contagem

Problema de contagem

Mensagempor exploit » Sáb Jul 17, 2010 02:26

Olá galera, estou com dúvida em relação a um exercício de Matemática Discreta. Trata-se do seguinte:
Exiba o número de funções f com D(f) = {1, 2, 3, 4, 5, 6, 7, 8, 9} e R(f) ? { a, b, c, d, e}, e também com:
a) f(1) ? a e f(9) ? e.
b) f(1) ? f(2), f(1) ? f(3), f(1) ? f(8), f(1) ? f(9) e f(8) ? f(9).
c) R(f) = {a, b, c, d, e}.
d) Número de elementos de f-¹(a) é 3 e o número de elementos de f-¹(b) é menor ou igual a 2.

Sei que é possível resolver pelo Princípio da Inclusão/Exclusão e por Polinômios Cromáticos, mas desconheço a aplicação correta dos dois :s

Se alguém puder me dar uma força ficarei grato!
[]s,
Exploit.

Ps.: TOM, me ajuda!!!! :D
exploit
Novo Usuário
Novo Usuário
 
Mensagens: 8
Registrado em: Sex Jul 16, 2010 22:30
Formação Escolar: GRADUAÇÃO
Área/Curso: Ciências de Computação
Andamento: cursando

Re: Problema de contagem

Mensagempor exploit » Sáb Jul 17, 2010 16:18

Já que é pra haver interação, vou enunciar minhas tentativas. Seguem abaixo:

Resolução do item a:
Sejam D(f) = \{1, 2, 3, 4, 5, 6, 7, 8, 9\} e R(f) \subset \{a, b, c, d, e\}. Pelo Princípio da Inclusão/Exclusão, temos
A = \{f \in R(f)^{D(f)} : a \notin R(f)\} \subset R(f)^{D(f)}
e
B = \{f \in R(f)^{D(f)} : e \notin R(f)\} \subset R(f)^{D(f)}
onde |A| = 4^9 = |B| e |A\capB| = 3^9.
Então, tomando |U| = |R(f)^{D(f)}| = 5^9, vem
|(A\cup B)^c| = |A^c \cap B^c| = |U| - |A\cup B| = |U| - (|A| + |B| - |A\cap B|)
= 5^9 - 2*4^9 + 3^9 = 1448520
Obs.: A resposta que me foi passada é (\lambda - 1)(\lambda - 1)\lambda^7 = 78141, onde \lambda = 5.

Resolução do item b:
Neste item fiz o uso do Polinômio Cromático, montado a partir deste grafo:
Imagem
Sua lei de formação seria f(1) ? f(2), f(1) ? f(3), f(1) ? f(8), f(1) ? f(9) e f(8) ? f(9).
Eis que o polinômio encontrado foi ?(? - 2)(? - 1)^3 = 960, quando ? = 5.
Obs.: A resposta que me foi passada é 625.

Ainda estou trabalhando nos itens c e d. Mas posso afirmar de antemão que 5^9 não é a resposta do item c.

Novamente, agradeço imensamente àquele que puder me iluminar.
[]s,
Exploit.
Editado pela última vez por exploit em Sáb Jul 17, 2010 23:51, em um total de 2 vezes.
exploit
Novo Usuário
Novo Usuário
 
Mensagens: 8
Registrado em: Sex Jul 16, 2010 22:30
Formação Escolar: GRADUAÇÃO
Área/Curso: Ciências de Computação
Andamento: cursando

Re: Problema de contagem

Mensagempor Douglasm » Sáb Jul 17, 2010 16:42

EDIT: No item a eu fiz "ao contrário"...=P Agora está corrigido

Sobre o item a, usando o princípio da inclusão-exclusão, encontrei:

|A| = 5^8 (somente f(1) = a)

|B| = 5^8 (somente f(9) = e)

|A ? B| = 5^7 (intersecção das duas condições anteriores)

Logo o número procurado seria:

5^9 - 5^8 - 5^8 + 5^7 = 125000

Agora sobre o item c: Novamente devemos fazer uso do princípio da inclusão-exclusão. O que desejamos encontrar aqui é o número de funções sobrejetoras. Esse número é dado por:

\sum^p_{k=0}(-1)^k.C^p_k.(p-k)^n

Extenderia-me muito se fosse explicar essa parte, mas mandarei um link que me poupará desse trabalho:

http://www.olimpiada.ccet.ufrn.br/treinamento_2004/notas_aula/nota_aula_05.pdf

Sendo assim, o número de funções é:

5^9 - 5.4^9 + 10.3^9 - 10.2^9 + 5 = 834120

Ainda não olhei os itens b e d com o devido cuidado, então por hora é só.
Editado pela última vez por Douglasm em Sáb Jul 17, 2010 16:51, em um total de 1 vez.
Avatar do usuário
Douglasm
Colaborador Voluntário
Colaborador Voluntário
 
Mensagens: 270
Registrado em: Seg Fev 15, 2010 10:02
Formação Escolar: ENSINO MÉDIO
Andamento: formado

Re: Problema de contagem

Mensagempor exploit » Sáb Jul 17, 2010 16:50

OK, vou ler aquele pdf que você me passou. Obrigado! ;)
exploit
Novo Usuário
Novo Usuário
 
Mensagens: 8
Registrado em: Sex Jul 16, 2010 22:30
Formação Escolar: GRADUAÇÃO
Área/Curso: Ciências de Computação
Andamento: cursando

Re: Problema de contagem

Mensagempor Douglasm » Sáb Jul 17, 2010 16:52

Não deixe de reparar que eu inverti as coisas no item a, agora está corrigido e bate com o seu gabarito!
Avatar do usuário
Douglasm
Colaborador Voluntário
Colaborador Voluntário
 
Mensagens: 270
Registrado em: Seg Fev 15, 2010 10:02
Formação Escolar: ENSINO MÉDIO
Andamento: formado

Re: Problema de contagem

Mensagempor exploit » Dom Jul 18, 2010 00:04

Beleza, já notei.
A propósito, fiquei com dúvida naquela intersecção |A ? B| = 5^7, como você chegou nesses 5^7? E o que mudaria na resolução caso o enunciado tivesse me dado R(f) = { a, b, c, d, e}, ao invés de R(f) ? { a, b, c, d, e}? Ou seja, R(f) seria o próprio conjunto, e não apenas estaria contido em tal.
exploit
Novo Usuário
Novo Usuário
 
Mensagens: 8
Registrado em: Sex Jul 16, 2010 22:30
Formação Escolar: GRADUAÇÃO
Área/Curso: Ciências de Computação
Andamento: cursando

Re: Problema de contagem

Mensagempor Douglasm » Dom Jul 18, 2010 22:36

A intersecção se deve ao fato de termos considerado os casos em que f(1) = a e f(9) = e. Se fizermos uma permutação simples, vemos que esses casos são:

1 . 5 . 5 . 5 . 5 . 5 . 5 . 5 . 1 (1 possibilidade para f(1), 5 para f(2), etc.)

Sobre a R(f) ser igual ou estar contido no conjunto citado, isso não alteraria os valores encontrados, pois na conta consideramos as imagens iguais a {a, b, c, d, e}, como também todos os seus subconjuntos. Isso é independente de R(f) = R(f) = { a, b, c, d, e} ou R(f) ? { a, b, c, d, e}, já que estamos falando apenas de possibilidades.

Sobre o item b, eu não penso que a resposta seja essa (não entendo como se chega a isso), pois isso levaria a situação em que f(1), f(2), f(3), f(8) e f(9) seriam todos diferentes entre si. Ao meu ver isso não é necessariamente verdadeiro, tendo em vista as condições do enunciado.
Avatar do usuário
Douglasm
Colaborador Voluntário
Colaborador Voluntário
 
Mensagens: 270
Registrado em: Seg Fev 15, 2010 10:02
Formação Escolar: ENSINO MÉDIO
Andamento: formado

Re: Problema de contagem

Mensagempor exploit » Qua Jul 21, 2010 03:14

Muito obrigado! (:

A propósito, descobri o que havia de errado com meu polinômio cromático. Eu esqueci de considerar as cores que sobraram, ou seja, além dos valores de 1, 2, 3, 8 e 9 formadores do polinômio \lambda(\lambda - 1)^3(\lambda - 2), ainda restavam as 'cores' 4, 5, 6 e 7 que ficam de fora. Como elas podem aderir a qualquer cor, uma vez que estão desconexas no grafo, o polinômio correto seria \lambda(\lambda - 1)^3(\lambda - 2)\lambda^4 = \lambda^5(\lambda - 1)^3(\lambda - 2).
exploit
Novo Usuário
Novo Usuário
 
Mensagens: 8
Registrado em: Sex Jul 16, 2010 22:30
Formação Escolar: GRADUAÇÃO
Área/Curso: Ciências de Computação
Andamento: cursando


Voltar para Álgebra Elementar

 



  • Tópicos relacionados
    Respostas
    Exibições
    Última mensagem

Quem está online

Usuários navegando neste fórum: Nenhum usuário registrado e 9 visitantes

 



Assunto: Simplifique a expressão com radicais duplos
Autor: Balanar - Seg Ago 09, 2010 04:01

Simplifique a expressão com radicais duplos abaixo:

\frac{\sqrt[]{\sqrt[4]{8}+\sqrt[]{\sqrt[]{2}-1}}-\sqrt[]{\sqrt[4]{8}-\sqrt[]{\sqrt[]{2}-1}}}{\sqrt[]{\sqrt[4]{8}-\sqrt[]{\sqrt[]{2}+1}}}

Resposta:
Dica:
\sqrt[]{2} (dica : igualar a expressão a x e elevar ao quadrado os dois lados)


Assunto: Simplifique a expressão com radicais duplos
Autor: MarceloFantini - Qua Ago 11, 2010 05:46

É só fazer a dica.


Assunto: Simplifique a expressão com radicais duplos
Autor: Soprano - Sex Mar 04, 2016 09:49

Olá,

O resultado é igual a 1, certo?