Quantas são as permutações de \{1,2, \ldots, p n\} que não têm múltiplos de p adjacentes?

Passo 1

Resumindo: temos p n elementos, dos quais exatamente n são múltiplos de p e os outros (p-1)n não são múltiplos. Queremos contar as permutações de \{1,2,\dots,pn\} em que nenhum par de múltiplos de p 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 (p-1)n elementos que não são múltiplos de p. Isso pode ser feito de
maneira independente em
((p-1)n)!
formas. Depois de arranjá­-los, há exatamente (p-1)n+1 lacunas (incluindo as duas extremidades) onde podemos inserir os múltiplos de p.

Passo 3

Precisamos escolher n dessas (p-1)n+1 lacunas para colocar um múltiplo de p em cada uma, o que pode ser feito em
\binom{(p-1)n+1}{n}
maneiras. Em seguida, permutamos os n múltiplos de p entre si, o que dá mais n!
arranjos.
Multiplicando todas as etapas, o número total de permutações sem dois múltiplos de p adjacentes é
\binom{(p-1)n+1}{n}\,\bigl((p-1)n\bigr)!\,n!.

Resposta

\boxed{\binom{(p-1)n+1}{n}\,( (p-1)n )!\,n!}.

Exercícios relacionados