Quantas são as permutações de ( 1,2, ldots, 2 n ) nas quais nenhum número impar ocupa o seu lugar primitivo?

Passo 1

O enunciado pede o número de permutações de 1,2,dots,2n em que nenhum número ímpar ocupa sua posição original.
Conteúdo: Princípio da Inclusão-Exclusão aplicado a pontos fixos em permutações.

Passo 2

Vamos indexar os números ímpares por i=1,3,5,dots,2n-1. Para cada ímpar i, defina o evento Ai = “na permutação, i fica fixo” (isto é, pi(i)=i). Queremos contar as permutações que evitam todos os Ai.

Passo 3

Pelo Princípio da Inclusão-Exclusão, se há n ímpares, o número desejado é
sumk=0^n(-1)^k;l(escolher k ímpares a fixarr);times;l(permutações dos restantesr) íçõ
Escolher k ímpares a fixar: binomnk. Após fixá-los, restam 2n-k elementos livres, que podem permutar de (2n-k)! formas.

Passo 4

Logo, o total de permutações em que nenhum ímpar fica em seu lugar é
sumk=0^n(-1)^k,binomnk,(2n-k)!

Resposta

sumk=0^n(-1)^k,binomnk,(2n-k)!

Exercícios de Livros Relacionados