Ola' pessoal, vou usar os simbolos "+" significando uniao, e "^" significando intersecao entre alguns conjuntos formados pelos casais A,B,C,D e E.
Usando-se o "principio da inclusao-exclusao" sobre os conjuntos formados por todas as permutacoes em que cada casal aparece "junto" (o homem ao lado da esposa), podemos escrever o seguinte: #permut(A+B+C+D+E) = [C(5,1) * #permut(A)] - [C(5,2) * #permut(A^B)] + [C(5,3) * #permut(A^B^C)] - [C(5,4) * #permut(A^B^C^D)] + [C(5,5) * #permut(A^B^C^D^E)] onde: #permut(A+B+C+D+E) = cardinalidade da uniao dos conjuntos em que algum casal aparece junto. #permut(A) = numero de permutacoes em que o casal A aparece junto. #permut(A^B) = numero de permutacoes em que o casal A aparece junto e o casal B aparece junto. ... #permut(A^B^C^D^E) = numero de permutacoes em que cada um dos casais A,B,C,D e E aparece junto. Para calcularmos #permut(A^B), por exemplo, basta fixarmos a mulher do casal A (com 2 opcoes de encaixe do homem), apos o que, temos o casal B (com 2 opcoes de encaixe do homem) e mais 6 pessoas para permutarmos ( 7! opcoes ). Dessa forma, o termo generico da expressao para n casais vale: [(-1)**(n+1)] * [C(5,n) * 2^n * (9-n)!] Assim, #permut(A+B+C+D+E) = [C(5,1) * 2^1 * 8!] - [C(5,2) * 2^2 * 7!] + [C(5,3) * 2^3 * 6!] - [C(5,4) * 2^4 * 5!] + [C(5,5) * 2^5 * 4!] Fazendo as contas, obtemos: #permut(A+B+C+D+E) = [5 * 2 * 40320] - [10 * 4 * 5040] + [10 * 8 * 720] - [5 * 16 * 120] + [1 * 32 * 24] #permut(A+B+C+D+E) = 250368 Como o total de permutacoes possiveis para os 5 casais vale 9!, o numero de permutacoes em que nenhum casal aparece junto corresponde a 9! - #permut(A+B+C+D+E) = 362880 - 250368 = 112512 Assim, o numero de permutacoes procurado vale 112512. []'s Rogerio Ponce > > Não entendi seu raciocínio :( > Fiz um programa de computador que calcula todas as possibilidades da > função f(x), para x casais > obtive:f(0) = 0f(1) = 0f(2) = 2f(3) = 32f(4) = 1488f(5) = 112512 > > Se considerar que a formação horária é igual a anti-horária, divida > ainda por 2 > Até o f(2) é fácil de se achar > Aqui vai todas as 192 (que é 32*6) possibilidades do f(3) em linha > (ou seja ,ignorando a igualdade por rotação e considerando que o primeiro > termo senta ao lado do último)Sendo 0,1 o primeiro casal, 2,3 o segundo... > ['021435', '021534', '024135', '024153', '024315', '025134', '025143', > '025314', '031425', '031524', '034125', '034152', '034215', '035124', > '035142', '035214', '041253', '041352', '042135', '042153', '042513', > '043125', '043152', '043512', '051243', '051342', '052134', '052143', > '052413', '053124', '053142', '053412', '120435', '120534', '124035', > '124053', '124305', '125034', '125043', '125304', '130425', '130524', > '134025', '134052', '134205', '135024', '135042', '135204', '140253', > '140352', '142035', '142053', '142503', '143025', '143052', '143502', > '150243', '150342', '152034', '152043', '152403', '153024', '153042', > '153402', '203415', '203514', '204135', '204315', '204351', '205134', > '205314', '205341', '213405', '213504', '214035', '214305', '214350', > '215034', '215304', '215340', '240315', '240351', '240531', '241305', > '241350', '241530', '243051', '243150', '250314', '250341', '250431', > '251304', '251340', '251430', '253041', '253140', '302415', '302514', > '304125', '304215', '304251', '305124', '305214', '305241', '312405', > '312504', '314025', '314205', '314250', '315024', '315204', '315240', > '340215', '340251', '340521', '341205', '341250', '341520', '342051', > '342150', '350214', '350241', '350421', '351204', '351240', '351420', > '352041', '352140', '402153', '402513', '402531', '403152', '403512', > '403521', '405213', '405312', '412053', '412503', '412530', '413052', > '413502', '413520', '415203', '415302', '420351', '420513', '420531', > '421350', '421503', '421530', '425031', '425130', '430251', '430512', > '430521', '431250', '431502', '431520', '435021', '435120', '502143', > '502413', '502431', '503142', '503412', '503421', '504213', '504312', > '512043', '512403', '512430', '513042', '513402', '513420', '514203', > '514302', '520341', '520413', '520431', '521340', '521403', '521430', > '524031', '524130', '530241', '530412', '530421', '531240', '531402', > '531420', '534021', '534120'] > > Para o f(3) tenho um método para achar o 32 (muito pouco prático), > serve também para qualquer x, mas depois do f(3) fica quase impossível de > se fazer as coisas sem um computador. > Tentei achar uma recursão mas não consegui (aliás pela fatoração dos > resultados, tal recursão teria que ter muitas somas já que 112512 por > exemplo tem fator 293, ou seja, provavelmente não seria viável > Para o caso específico de homem sentar ao lado de mulher achei uma > recursão e uma fórmula fácil (se você entende de teoria do caos). > []'sJoão > Date: Sun, 5 Feb 2012 16:39:02 -0200 > Subject: [obm-l] Re: [obm-l] Permutação circular > From: gmerencio.san...@gmail.com > To: obm-l@mat.puc-rio.br > > Meu raciocínio é considerar cada casal como uma reta, sendo definida por > dois pontos: um é o assento do marido e o outro o da esposa. Temos um total > de C(10, 2) retas para representar o primeiro casal. Para descontar as > configurações iguais por rotação, dividimos esse número por 5. Finalmente, > sabemos que exatamente 2 dessas retas são inválidas, pois nelas o marido > fica ao lado de sua esposa (já descontamos as outras obtidas por rotação) . > > Continuando a lógica para os 8 assentos restantes, vemos que agora dividimos > por 4, já que um casal já está à mesa. Resultados semelhantes podem ser > inferidos para 6 e depois 4 assentos restantes, só restando 1 possibilidade > para o último par. Portanto: > > [C(10,2)/5 - 2] * [C(8,2)/4 - 2] * [C(6,2)/3 - 2] * [C(4,2)/2 - 2] * 1 = = 7 > * 5 * 3 * 1 * 1 == 105 > 2012/1/27 Carlos Gomes <cgomes...@gmail.com> > > > > > > > > > Olá amigos...alguém poderia me ajudr com a > questão: > > De quantas formas distintas 5 casais podem ser > dispostos em torno de uma mesa circular, supondo que cada marido não fique > ao > lado da sua respectiva esposa? > > (Duas conficurações são consideradas iguais se uma > puder ser obtida da outroa por um movimento de rotação!) > > > Obrigado, Cgomes. > > ========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =========================================================================
