Re: Combinatoria

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

On Sat, 11 Sep 1999, Fábio Costa wrote:

> Ao estudar combinatória no segundo grau, encaramos os famosos problemas de
  "pintar" poliedros com cores diferentes. No entanto, para poliedros com
  muitas faces, fica difícil contabilizar de quantas maneiras podemos
  pintar um poliedro de n faces com n cores distintas.

Oi Fabio, acho que você precisa nos explicar melhor que tipo de enunciado
você tem em mente:

(a) quando duas pinturas são consideradas a mesma?
    vale rodar o sólido? vale refletir em um espelho?

(b) que pinturas são válidas?
    é permitido pintar faces vizinhas da mesma cor?

(c) que poliedros exatamente você está usando?

> Para solucionar esse problema, me ensinaram uma fórmula que parece dar
  sempre o resultado correto: N = ( F - 1 )! / n , em que:
> N é o número de modos possíveis de se pintar o poliedro de F faces e
  n arestas em cada face.
> Será que alguém poderia me ajudar a entender de onde surge essa fórmula
  ou, se possível, enviar para a lista uma demonstração de sua validade?

Pelo resto da sua mensagem (especialmente a fórmula) adivinho que suas
respostas seriam:

(a) vale rodar mas não refletir (como se tivéssemos um objeto sólido)

(b) cada cor deve ser usada exatamente uma vez
    (como temos F cores e F faces isto é possível)

(c) consideramos apenas poliedros regulares

Supondo isto tudo, a fórmula é correta mas só pode ser usada em 5
situações diferentes, então fica meio sem graça.
Você pode simplesmente verificar os 5 casos, mas uma demonstração
direta seria: 

Inicialmente fixe o sólido e pinte a face de baixo de branco (digamos);
de quantas maneiras podemos pintar as outras faces?
Claramente de (F-1)! maneiras distintas.
Mas quantas destas devem ser identificadas?
Bem, podemos rodar o sólido de n maneiras sem tirar a face branca da mesa,
donde as pinturas vêm em classes de n identificadas. Daí a fórmula.

Fica tudo mais interessante se você mudar as respostas para pelo menos
um dos itens (a), (b) e (c).

[]s, N.
http://www.mat.puc-rio.br/~nicolau