Analise Comb.

Olá Pessoal, preciso de uma ajuda bem didática para resolver a questão abaixo:

De quantas maneiras n casais podem sentar em 2n cadeiras diferentes em torno de um círculo de modo que pessoas do mesmo sexo não se sentem juntas e que nenhum homem fique ao lado de sua mulher?

Para essas pessoas sentarem sem que pessoas do mesmo sexo fiquem juntas, devem estar em um circulo desta forma: (....HMHMHM... ). Vamos considerar agora que cada HM desses seja uma pessoa. 
Ignoremos as cadeiras e pensemos que os casais agora sentarão em círculos no chão. Consideremos cada casal como um ponto no círculo. Certo, agora teremos n! formas de organizar esses pontos no círculo. No entanto, para cada combinação existente, haverá n repetições dela. Assim, n!/ n = (n-1)!, que é justamente a fórmula de permutação circular. Okay, agora, temos que levar em conta que cada casal pode ser combinado de duas formas: ou HMHMHM... ou MHMHMH.... 
Portanto, há 2x(n-1)! maneiras desses n casais sentarem em torno do círculo sem que pessoas do mesmo sexo sentem juntas.

Você possui a resposta da questão para conferir?

Olá Lucas.
Não tenho respostas.

Olá Mônica, agora percebi que tive uma interpretação incompleta da questão. Portanto, minha resposta anterior está incorreta.
A condição "que nenhum homem fique ao lado de sua mulher"  é onde está toda complexidade do problema, também conhecido como "Problema de Lucas". Para o resolvermos, podemos seguir alguns passos:

1) Numerar as cadeiras em posições de 1 a 2n.
2) Distribuir as mulheres em posições ímpares ou posições pares (para garantir que não haja pessoas do mesmo sexo juntas). Temos 2 possibilidades. 
3) Permutar as mulheres entre as posições escolhidas, que corresponde a n!. Temos o total de 2.n! posições para posicionar as n mulheres. 
4) Alocar os homens nas cadeiras restantes, sem que eles fiquem ao lado de sua esposa.

Assim, a solução L(n) desse problema se dará da seguinte forma: 



Un é a quantidade de modos de se alocar os n homens, sem que fiquem ao lado de sua esposa.
-------------------------------------------------------------------------------------------------------------------------------


A = n!, visto que são as alocações dos n homens, sem restrição; 
Ai é o conjunto das permutações dos homens, onde o i-ésimo homem está à esquerda de sua mulher. 
Ai' é o conjunto das permutações de homens, onde o i-ésimo homem está à direita de sua mulher.
Sendo que 1≤I≤n.


I)   Se fizermos as interseções entre os conjuntos consecutivos de (A1,A1',A2,A2',...,An,An'), teremos que elas serão sempre vazias. Por exemplo, A1ՈA1': interseção vazia, pois o primeiro homem não pode sentar ao lado esquerdo e direito da sua mulher ao mesmo tempo; AnՈA1': vazia, pois a posição n-ésima é igual à posição nº 1', logo não pode haver mais de um homem nela. Isto posto, sabendo que temos 2n elementos no conjunto (A1,A1',A2,A2',...,An,An'), podemos usar o 2º Lema de Kaplansky para calcular o número de interseções possíveis.

Relembrando o 2º Lema de Kaplansky: "o número de p-subconjuntos de {1,2,...,m} elementos nos quais não há números consecutivos é, considerando 1 e m como consecutivos": 



Como em nosso conjunto (A1,A1',A2,A2',...,An,An') temos 2n elementos e queremos tomá-los em subconjuntos com k elementos não consecutivos, fica: 




II) Pensemos ainda que, a cada k homens (k≤n) que fixamos ao lado de sua mulher, teremos n-k homens para permutar no conjunto, o que corresponde a (n-k)! maneiras distintas.


Então, a interseção dos conjuntos, tomados k a k, corresponde a  (n-k)! parcelas de  . No total, fica:   

Pelo Princípio da Inclusão e Exclusão, chegaremos a:


Assim,






Sendo: 



Então,

Para n = 2, isto é para dois casais não existe solução:

Sejam A, a um casal e B, b outro  sendo A, B os homens e a, b as mulheres.
Existem duas possibilidades, considerando apenas a ordem na rotação:

.... A ................ A

a ...... b ...... b ........ a

.... B ................ B

Note que homens não ficaram juntos e mulheres também não.
Mas cada cada marido sentou ao lado da sua esposa

Obrigado, mestre, esqueci de estabelecer n>2.

Só como curiosidade

Para n = 3 casais ---> (A, a), (B, b), (C, c) existem apenas duas possibilidades


......... A ................................ A

b ................ c ...............c ............... b


C ................ B ............. B ............... C


......... a ................................. a

Mas mestre, o fato das cadeiras serem diferentes não faz com que as rotações sejam possíveis? Então, no caso, as possibilidades seriam 6 x 2 = 12. Inclusive esse é o resultado que se encontra ao aplicarmos n = 3 na fórmula.

Eu não atentei para o fato das cadeiras serem diferentes. Desconsiderem minhas soluções.