Problema de contagem

[exploit]

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

[exploit]

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

Resolução do item a:
Sejam e . Pelo Princípio da Inclusão/Exclusão, temos

e

onde e .
Então, tomando , vem


Obs.: A resposta que me foi passada é , onde .

Resolução do item b:
Neste item fiz o uso do Polinômio Cromático, montado a partir deste grafo:

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.

[Douglasm]

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:



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:



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 é:



Ainda não olhei os itens b e d com o devido cuidado, então por hora é só.

[exploit]

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

[Douglasm]

Não deixe de reparar que eu inverti as coisas no item a, agora está corrigido e bate com o seu gabarito!

[exploit]

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.

[Douglasm]

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.

[exploit]

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