Considere um conjunto de N artigos, dos quais u são de um modelo antigo. Quantos ordenamentos lineares são possíveis, se duas modelos antigos não devem estar dispostos consecutivamente?

Passo 1

O enunciado pede o número de ordenamentos lineares de N artigos, dos quais u são “antigos”, de modo que nenhum par de artigos antigos fique em posições consecutivas. O conteúdo usado será contagem de permutações com restrição de não-consecutividade, via “método dos vãos” ou “stars and bars”.

Passo 2

Primeiro, organizamos os N-u artigos novos livremente entre si. Como todos os artigos são distintos, há
(N - u)!
maneiras de permutar somente os novos. Depois de colocá-los, reconhecemos que existem exatamente N-u+1 vãos onde podemos inserir artigos antigos (antes do primeiro novo, entre dois novos quaisquer, e após o último).

Passo 3

Para garantir que nenhum par de u artigos antigos fique junto, precisamos escolher u desses N-u+1 vãos, colocando em cada vão escolhido exatamente um artigo antigo. O número de maneiras de escolher quais vãos usar é
\binom{\,N - u + 1\,}{\,u\,}.

Passo 4

Feita a escolha dos u vãos, ainda temos de ordenar os u artigos antigos entre si. Como são todos distintos, há u!
maneiras de permutar esses artigos dentro dos vãos selecionados.

Passo 5

Pelo Princípio Fundamental da Contagem, multiplicamos o número de formas de permutar os novos, o número de escolhas de vãos e o número de permutações dos antigos. Assim o total é
(N - u)!\;\times\;\binom{\,N - u + 1\,}{\,u\,}\;\times\;u!.

Resposta

(N - u)!\;\binom{N - u + 1}{u}\;u!.

Exercícios relacionados