- (Simon & Blume - Exercício 8.9) Quantas matrizes de permutação
existem?
Passo 1
O enunciado pergunta quantas matrizes de permutação existem de tamanho
. Esse é um problema de contagem ligado ao conceito de permutações: cada matriz de permutação corresponde a uma permutação de
objetos.
Passo 2
Uma matriz de permutação é uma matriz binária que tem exatamente um elemento igual a 1 em cada linha e em cada coluna, e zeros nos demais lugares. Para construí-la de forma sistemática, siga este raciocínio:
– Na primeira linha podemos escolher em qual das colunas colocar o único 1 (há
possibilidades).
– Na segunda linha restam colunas livres para posicionar o seu 1.
– Na terceira linha restam colunas, e assim por diante, até a última linha, que terá apenas 1 coluna livre.
Portanto, o número total de matrizes de permutação é
– Na primeira linha podemos escolher em qual das
– Na segunda linha restam
– Na terceira linha restam
Portanto, o número total de matrizes de permutação é