[obm-l] Um tabuleiro de xadrez diferente! Combinatória

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

> (FGV-SP) Um tabuleiro especial de xadrez possui 16 casas, dispostas em 4
> linhas e 4 colunas. Um jogador deseja colocar 4 peças no tabuleiro, de tal
> forma que, em cada linha e cada coluna, seja colocada apenas uma peça. De
> quantas maneiras as peças poderão ser colocadas?

Sei que um monte de gente já respondeu esta mas não resisto a mandar
a minha resposta já que acho que ela é de certa forma mais simples.

Para começar vamos trocar 4 por n e 16 por n^2 no enunciado.
O enunciado não deixa muito claro se devemos considerar as n peças
como iguais (n torres brancas) ou diferentes (as torres são numeradas
de 1 a n); vamos resolver as duas versões.

Se as peças são iguais as suas posições são o gráfico de uma permutação
de {1,2,...,n} (ou seja, para cada linha i, 1 <= i <= n,
uma peça ocupa a posição (i,f(i)) onde f: {1,2,...,n} -> {1,2,...,n}).
Assim há n! soluções.

Se as peças são diferentes precisamos de uma segunda permutação
para indicar o índice da peça. Se preferirem, podem também considerar
que uma permutação indica a linha e outra a coluna. De qq forma a
resposta é (n!)^2.

4! = 24, (4!)^2 = 576

[]s, N.
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================