Problema de contagem

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

por **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.

por **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

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

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

OK, vou ler aquele pdf que você me passou. Obrigado!

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

por **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.

por **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.

por **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)$ .