Suponha que haja marcianos e terráqueos em uma conferência de paz. Para garantir que os marcianos permaneçam pacíficos na conferência, devemos nos certificar de que não há dois marcianos sentados juntos, de modo que entre dois marcianos haja pelo menos um terráqueo (ver detalhes).

Responda:

a) # (n! (n + 1)!) / ((n-m + 1)!) #

b) # (n! (n-1)!) / ((n-m)!) #

Explicação:

Além de algum raciocínio extra, usaremos três técnicas comuns para contar.

Primeiro, vamos fazer uso do fato de que, se houver # n # maneiras de fazer uma coisa e # m # maneiras de fazer o outro, em seguida, assumindo que as tarefas são independentes (o que você pode fazer por um não depende do que você fez no outro), existem # nm # maneiras de fazer as duas coisas. Por exemplo, se eu tenho cinco camisas e três pares de calças, então existem #3*5=15# roupas que eu posso fazer.

Em segundo lugar, vamos usar esse o número de formas de ordenação #k # objetos é #k! #. Isso é porque existem #k # maneiras de escolher o primeiro objeto e, em seguida, # k-1 # maneiras de escolher o segundo, e assim por diante. Assim, o número total de maneiras é #k (k-1) (k-2) … (2) (1) = k! #

Finalmente, vamos usar esse número de maneiras de escolher #k # objetos de um conjunto de # n # objetos é # ((n), (k)) = (n!) / (k! (n-k)!) # (pronunciado como n escolha k). Um esboço de como chegar a esta fórmula é dado aqui.

a) Se desconsiderarmos as divisões inicialmente, há #m! # maneiras de encomendar os marcianos e #n! # maneiras de encomendar os terráqueos. Finalmente, precisamos ver onde os marcianos estão colocados. Como cada marciano precisa ser colocado em uma extremidade ou entre dois terráqueos, existem # n + 1 # locais onde eles podem se sentar (um à esquerda de cada Terra, e depois outro à direita). Como existem # m # Marcianos, isso significa que existem # ((n + 1), (m)) = ((n + 1)!) / (m! (n + 1-m)!) # possíveis maneiras de colocá-los. Assim, o total possível de assentos é

#n! m! ((n + 1)!) / (m! (n + 1-m)!) = (n! (n + 1)!) / ((n-m + 1)!) #

b) Esse problema é semelhante ao acima. Para tornar as coisas mais simples, vamos escolher um terráqueo e chamá-lo de presidente. Porque não importa como um círculo é girado, em vez de se referir a arranjos de assentos baseados em uma ordem absoluta, consideraremos os arranjos de assentos baseados em sua relação com o presidente.

Assim como acima, se partirmos do presidente e continuarmos no sentido horário ao redor do círculo, podemos contar o número de maneiras de ordenar os participantes restantes. Como existem # m # Marcianos e # n-1 # restantes terráqueos, existem #m! # maneiras de encomendar os marcianos e # (n-1)! # maneiras de pedir os terráqueos restantes.

Em seguida, mais uma vez precisamos posicionar os marcianos. Desta vez não temos mais um spot no final, por isso só há # n # locais onde eles podem se sentar. Então há # ((n), (m)) = (n!) / (m! (n-m)!) # maneiras de colocá-los. Assim, o total possível de assentos é

# (n-1)! m! (n!) / (m! (n-m)!) = (n! (n-1)!) / ((n-m)!) #