1. (Simon & Blume - Exercício 8.9) Quantas matrizes de permutação n \times n existem?

Passo 1

O enunciado pergunta quantas matrizes de permutação existem de tamanho n\times n. Esse é um problema de contagem ligado ao conceito de permutações: cada matriz de permutação corresponde a uma permutação de n 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 n colunas colocar o único 1 (há n possibilidades).
– Na segunda linha restam n-1 colunas livres para posicionar o seu 1.
– Na terceira linha restam n-2 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 é
n \times (n-1) \times (n-2) \times \cdots \times 1 = n!

Resposta

n!

Exercícios relacionados