Quantas são as permutações de
que não têm múltiplos de
adjacentes?
Passo 1
Resumindo: temos
elementos, dos quais exatamente
são múltiplos de
e os outros
não são múltiplos. Queremos contar as permutações de
em que nenhum par de múltiplos de
aparece em posições adjacentes. Esse é um problema clássico de “nenhum objeto especial adjacente”, que resolve-se colocando primeiro os não-especiais e depois inserindo os especiais nos “espaços” (lacunas) resultantes.
Passo 2
Primeiro, permutamos os
elementos que não são múltiplos de
. Isso pode ser feito de
maneira independente em
maneira independente em
formas. Depois de arranjá-los, há exatamente
lacunas (incluindo as duas extremidades) onde podemos inserir os múltiplos de
.
Passo 3
Precisamos escolher
dessas
lacunas para colocar um múltiplo de
em cada uma, o que pode ser feito em
maneiras. Em seguida, permutamos os
múltiplos de
entre si, o que dá mais
arranjos.
arranjos.
Multiplicando todas as etapas, o número total de permutações sem dois múltiplos de
adjacentes é