Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Análise combinatória
Muito obrigado a todos, excelentes respostas! Artur Costa Steiner Em 12/07/2013, às 09:34, Marcos Martinelli mffmartine...@gmail.com escreveu: Blza. Entendi agora. Obrigado. Em 12 de julho de 2013 09:29, Rogerio Ponce abrlw...@gmail.com escreveu: Ola' Marcos, eu escrevi errado. Como os blocos representam 4 elementos, que ocupam 7 casas, e' como se houvesse 93 casas livres e 4 ocupadas, com um total de 100-(2+2+2+1)+4=97 casas. Ou seja, existem binom(97,4) formas de distribuirmos os 4 blocos dentro de [1,100]. []'s Rogerio Ponce 2013/7/12 Marcos Martinelli mffmartine...@gmail.com Só não entendi essa parte: 100-(2+2+2+1)=97. Em 12 de julho de 2013 09:08, Marcos Martinelli mffmartine...@gmail.com escreveu: Legal. Em 12 de julho de 2013 09:02, Rogerio Ponce abrlw...@gmail.com escreveu: Ola' Artur, como queremos que a distancia minima entre os elementos seja de pelo menos 2, podemos imaginar que devemos distribuir , dentro do segmento [0,100], 3 blocos com comprimento 2 , e um bloco com comprimento 1 (o bloco mais 'a direita). Como existem 100-(2+2+2+1)=97 vagas, o resultado vale binom(97,4)=3464840. []'s Rogerio Ponce 2013/7/11 Artur Costa Steiner steinerar...@gmail.com Não consegui achar uma forma de resolver isto sem recorrer a um computador. Com os inteiros de 1 a 100, quantos conjuntos de 4 elementos podemos formar de modo que a diferença positiva entre dois elementos do conjunto seja maior ou igual a 2? Abraços. Artur Costa Steiner -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html = -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Análise combinatória
2013/7/12 Marcos Martinelli mffmartine...@gmail.com Mas vc conseguiu mostrar que existe mesmo a bijeção? Um representante do primeiro tera um único representante no segundo e vice-versa pois só é feita uma subtração/soma. A questão é somente se as restrições são respeitadas. x2-1 x1 sse x2-x1 = 2 x3-2 x2-1 sse x3-x2 = 2 x4-3 x3-2 sse x4-x3 = 2 x4 = n sse x4-3 = n-3 x1 = 1 sse x1 = 1 -- []'s Lucas -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo.
[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Análise combinatória
Ola' Marcos, eu escrevi errado. Como os blocos representam 4 elementos, que ocupam 7 casas, e' como se houvesse 93 casas livres e 4 ocupadas, com um total de 100-(2+2+2+1)+4=97 casas. Ou seja, existem binom(97,4) formas de distribuirmos os 4 blocos dentro de [1,100]. []'s Rogerio Ponce 2013/7/12 Marcos Martinelli mffmartine...@gmail.com Só não entendi essa parte: 100-(2+2+2+1)=97. Em 12 de julho de 2013 09:08, Marcos Martinelli mffmartine...@gmail.comescreveu: Legal. Em 12 de julho de 2013 09:02, Rogerio Ponce abrlw...@gmail.comescreveu: Ola' Artur, como queremos que a distancia minima entre os elementos seja de pelo menos 2, podemos imaginar que devemos distribuir , dentro do segmento [0,100], 3 blocos com comprimento 2 , e um bloco com comprimento 1 (o bloco mais 'a direita). Como existem 100-(2+2+2+1)=97 vagas, o resultado vale binom(97,4)=3464840. []'s Rogerio Ponce 2013/7/11 Artur Costa Steiner steinerar...@gmail.com Não consegui achar uma forma de resolver isto sem recorrer a um computador. Com os inteiros de 1 a 100, quantos conjuntos de 4 elementos podemos formar de modo que a diferença positiva entre dois elementos do conjunto seja maior ou igual a 2? Abraços. Artur Costa Steiner -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html = -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo.
[obm-l] Re: [obm-l] RE: [obm-l] Re: [obm-l] Análise Combinatória
Desculpa, eu não fui muito claro na hora de fazer as contas (eu devia estar com pressa na hora que escrevi o outro e-mail). Aí vai: Para calcular a interseção de dois, ou seja, as sequências com AA e BB, trate AA e BB como blocos. Aí precisamos calcular a quantidade de anagramas com 8 símbolos (dois Cs, dois Ds, dois Es, o bloco AA e o bloco BB). Como três símbolos repetem, a quantidade é 8!/2^3. Os outros são parecidos. O que você fez, escolher 4 posições entre 10, pode fazer com que os As e/ou os Bs fiquem separados. Por exemplo, se você escolher as posições 1, 2, 4 e 6 e AABB, sua sequência fica, inicialmente, AA_B_B_,_,_,_. Os As ficaram juntos, mas os Bs não. Outro exemplo é _B_B_,_A_A_. Por isso o seu resultado é maior: você está contando sequências a mais. []'s Shine From: marcone augusto araújo borges marconeborge...@hotmail.com To: obm-l@mat.puc-rio.br Sent: Monday, February 25, 2013 11:51 AM Subject: [obm-l] RE: [obm-l] Re: [obm-l] Análise Combinatória Onde estou errando? n(intersecção de dois) = ? AA e BB por exemplo. Escolho 4 posições (para essas 4 letras) entre 10 possíveis:C10,4 = 210 Para cada uma delas vale AABB ou BBAA Depois faço 6!/2^3 Dai encontro 210.2.6!/2^3 8!/2^3 Date: Sun, 24 Feb 2013 17:35:56 -0800 From: cysh...@yahoo.com Subject: [obm-l] Re: [obm-l] Análise Combinatória To: obm-l@mat.puc-rio.br Inclusão-exclusão. Sendo A, B, C, D, E os conjuntos dos anagramas com As, Bs, Cs, Ds, Es seguidos, temos que calcular 10!/2^5 - n(A U B U C U D U E). Mas n(A) = n(B) = ... = n(E) = 9!/2^4, n(interseção de dois) = 8!/2^3, n(interseção de três) = 7!/2^2, n(interseção de quatro) = 6!/2 e n(interseção dos cinco) = 5!. Aí o total é 10!/2^5 - 5.9!/2^4 + 10.8!/2^3 - 10.7!/2^2 + 5.6!/2 - 5!, e aí é fazer a conta. Não acho que haja uma fórmula bonitinha no caso geral, como é de praxe nos problemas de inclusão-exclusão. []'s Shine From: Artur Costa Steiner steinerar...@gmail.com To: obm-l@mat.puc-rio.br obm-l@mat.puc-rio.br Sent: Sunday, February 24, 2013 8:31 PM Subject: Re: [obm-l] Análise Combinatória Acho que podemos raciocinar assim: Para a 1a posição, a partir da esquerda, temos 5 opções de letra. Escolhida uma, restam 4 possibilidades para a segunda posição. E assim, até a 10a posição. Se não cometi nenhum engano, vai haver 5 x 4^9 modos atendendo ao desejado. Abraços Artur Costa Steiner Em 24/02/2013, às 19:27, Anderson Weber anderswe...@bol.com.br escreveu: Boa noite, amigos. Tem-se 10 letras: AA BB CC DD EE. De quantos modos podemos permutá-las, tal que não haja duas letras consecutivas iguais? Um abraço. Anderson = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html = = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
[obm-l] Re: [obm-l] RE: [obm-l] Re: [obm-l] Análise Combinatória - mais um
Isso mesmo. Nesse caso, você aplicaria mudança de variáveis: yi = xi-2 Em geral, para soluções inteiras maiores ou iguais a p, você deve aplicar a mudança de variável yi=xi+p-1 Abraços. Hugo Em 13 de setembro de 2011 19:55, João Maldonado joao_maldona...@hotmail.com escreveu: Valeu Hugo, Mas só pra ver se eu entendi, se fossem as soluções inteiras = -1, seria C(u+ 2w-1, w-1)? []'s João -- Date: Tue, 13 Sep 2011 15:55:09 -0300 Subject: [obm-l] Re: [obm-l] Análise Combinatória - mais um From: hfernande...@gmail.com To: obm-l@mat.puc-rio.br Seja a equação linear com coeficientes unitários x1 + x2 +...+ xw = u Escrevemos: 1 + 1 + 1 + ... + 1 = u (u parcelas iguais a 1). Cada solução inteira e positiva dessa equação corresponde a escolha de w-1 sinais mais dentre o u-1 existentes na igualdade acima. Por exemplo, a solução x1=x2=x3=...=x(w-1)=1 e xw=u-w+1 pode ser vista como: 1 *+* 1 *+* 1 *+* ... *+* 1 +1 +1... + 1 = u (onde escolhemos os primeiros w-1 sinais de mais) Ora, podemos fazer isso de C(u-1,w-1) maneiras distintas. Logo, existem C(u-1,w-1) soluções inteiras e positivas da equação. Para soluções inteiras não negativas, fazemos, para cada i variando de 1 a w yi = xi-1 Agora, a equação fica: y1 - 1 + y2 - 1 +...+ yw - 1 = u Daí, y1 + y2 + ... + yw = u+w Note que cada solução inteira positiva da equação acima corresponde uma solução não negativa da equação original. Mas já sabemos que a equação acima possui C(u+w-1, w-1) soluções inteiras positivas. Assim, a equação original possui C(u+w-1, w-1) soluções inteiras não negativas. Não sei se chega a ser uma demonstração o que escrevi, mas é uma boa maneira de ver essas fórmulas. Abraços. Hugo. Em 12 de setembro de 2011 17:11, João Maldonado joao_maldona...@hotmail.com escreveu: Olá, Queria saber como provar a que a quantidade de soluções inteiras positivas de um sistema com w variáveis da forma x1 + x2 +...+ xw = u é C(u-1, w-1) E que a quantidade de soluções inteiras não negativas é C(w+u-1, w-1) []'s João
