Obtenha o número total de permutações de (1,2, ldots, 2 n) em que 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 tais que nenhum dos n números ímpares fica em sua posição original. O conteúdo é o Princípio da Inclusão e Exclusão aplicado a restrições de “pontos fixos” apenas nas posições ímpares.

Passo 2

Chamemos de Ai o conjunto de permutações em que o número ímpar 2i-1 está fixo na posição 2i-1, para i=1,2,dots,n. Sem restrição, há (2n)! permutações. Se exigirmos que exatamente um subconjunto Jsubseteq1,dots,n de tamanho lvert Jrvert=j fique fixo, então todos os j ímpares correspondentes estão em suas posições, e os demais (2n-j) elementos podem permutar livremente.

Passo 3

Para um dado j, há binomnj escolhas de J e, com esses j fixos, (2n-j)! permutações. Pelo Princípio da Inclusão e Exclusão, o total desejado é
sumj=0^n(-1)^jbinomnj,(2n-j)!

Resposta

sumj=0^n(-1)^jbinomnj,(2n-j)!

Exercícios relacionados