Exemplo Resolvido - Análise Combinatória

Enunciado:

Existem 10 cadeiras numeradas de 1 a 10. De quantas formas duas pessoas podem se sentar, devendo haver ao menos uma cadeira entre elas?

Resolução:

Podemos imaginar as 10 cadeiras numeradas com a seguinte representação visual:

_  _  _  _  _  _  _  _  _  _

1  2  3  4  5  6  7  8  9  10

Se usarmos as letras A e B para representar as duas pessoas que sentarão nas cadeiras, uma possível configuração final seria assim:

_  _  _  _  _  A  _  _  _  B

1  2  3  4  5  6  7  8  9  10

Cada configuração também pode ser representada por um par ordenado (x, y); 1≤ x, y ≤10, x ∈ N, y ∈ N e x ≠ y. Por exemplo o exemplo acima seria representado pelo par (6, 10). 

Observação importante: Como o enunciado da questão não comenta se as cadeiras estão dispostas de forma circular ou não, é importante assumir que as cadeiras não estão num círculo, e portanto as cadeiras 1 e 10 não são vizinhas.

Portanto, a seguinte configuração seria válida:

A  _  _  _  _  _  _  _  _  B

1  2  3  4  5  6  7  8  9  10

Como a questão pede o número de formas onde as duas pessoas têm pelo menos uma cadeira entre elas, podemos calcular o total de possibilidades sem considerar esse fator e em seguida subtrair o número de casos onde as duas pessoas são vizinhas. Então, podemos montar a seguinte equação:

Resposta = total de possibilidades - número de possibilidades onde pessoas são vizinhas

Cálculo do total possibilidades:

Para a primeira pessoa sentar temos 10 possibilidades, pois ela pode sentar em qualquer cadeira, já para a segunda pessoa, restam apenas 9 cadeiras, então são 9 possibilidades para a segunda cadeira. Pelo princípio fundamental da contagem, o total seria então 10 x 9 = 90

Cálculo do número de possibilidades onde pessoas são vizinhas:

Temos um total de 9 pares de vizinhos sem levar em conta a ordenação:

{(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9), (9, 10)}

O par (4, 5) por exemplo, representa a seguinte configuração:

_  _  _  A  B  _  _  _  _  _

1  2  3  4  5  6  7  8  9  10

Também devemos levar em conta os pares trocados, pois não importa se A vem antes de B ou depois. Então para cada par ordenado do tipo (x, x+1), temos também o par ordenado trocado dado por (x+1, x).

Pegando o exemplo anterior, o par trocado do (4, 5) seria o par (5, 4), representando a seguinte situação:

_  _  _  B  A  _  _  _  _  _

1  2  3  4  5  6  7  8  9  10

Juntando os pares de vizinhos então ao todo temos 9 + 9 = 18 casos.

Conclusão

A resposta então será

Resposta = total de possibilidades - número de possibilidades onde pessoas são vizinhas

Resposta = 90 - 18 = 72