[obm-l] Re: [obm-l] Contagem de Permutações
Até chegarmos à marcação 2783915460, temos, se entendi bem: 2*9! (permutações começando com 0, 1) 6*8! (permutações começando com 20, 21, 23, 24, 25, 26) 6*7! (permutações começando com 270, 271, 273, 274, 275, 276) 2*6! (permutações começando com 2780, 2781) 5*5! (permutações começando com 27830, 27831, 27834, 27835, 27836) 1*4! (permutações começando com 278390) 2*3! (permutações começando com 2783910, 2783914) 1*2! (permutações começando com 27839150) 1*1! (permutações começando com 278391540) Somando tudo, são 99 permutações. Então 2783915460 indica o km 100 On Mon, Nov 25, 2019 at 11:35 AM Jamil Silva wrote: > O odômetro de um carro tem exatamente dez dígitos e registra a > quilometragem com um defeito, relacionando cada quilômetro rodado a uma e > somente uma das permutações dos dez dígitos em ordem estritamente > crescente, conforme mostrado abaixo. > > Quantos quilômetros esse carro já rodou se, atualmente, a marcação está > em 2783915460 ? > > 1 km > 0123456789 > 2 km > 0123456798 > 3 km > 0123456879 > 4 km > 0123456897 > 5 km > 0123456978 > 6 km > 0123456987 > 7 km > 0123457689 > 8 km > 0123457698 > 9 km > 0123457869 > 10 km --> 0123457896 > 11 km --> 0123457968 > 12 km --> 0123457986 > 13 km --> 0123458679 > . > . > . > > ? km > 2783915460 > > -- > 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.
[obm-l] Contagem de Permutações
O odômetro de um carro tem exatamente dez dígitos e registra a quilometragem com um defeito, relacionando cada quilômetro rodado a uma e somente uma das permutações dos dez dígitos em ordem estritamente crescente, conforme mostrado abaixo. Quantos quilômetros esse carro já rodou se, atualmente, a marcação está em 2783915460 ? 1 km > 0123456789 2 km > 0123456798 3 km > 0123456879 4 km > 0123456897 5 km > 0123456978 6 km > 0123456987 7 km > 0123457689 8 km > 0123457698 9 km > 0123457869 10 km --> 0123457896 11 km --> 0123457968 12 km --> 0123457986 13 km --> 0123458679 . . . ? km > 2783915460 -- 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 =
[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Combinatória (permutações)
Sim, voce tem razao, os termos em portugues nao estao corretos... A ideia (que eu nao escrevi) eh que cada sequencia que foi contada multiplas vezes num termo vai ser descontada nos termos seguintes, por isso tudo funciona. Vejamos se dah para expressar melhor o que foi de fato feito... Considere os conjuntos A1={permutacoes que mantem o 2 fixo}, A2={permutacoes que mantem o 4 fixo}, A3={permutacoes que mantem o 6 fixo} e A4={permutacoes que mantem o 8 fixo}. Entao, agora sim, por inclusao-exclusao: #(A1UA2UA3UA4) = #(A1) + #(A2) + #(A3) + #(A4) - #(A1UA2) - #(A1UA3) - #(A1UA4) - ... -#(A3UA4) + #(A1UA2UA3) + #(A1UA2UA4) + #(A1UA3UA4) + #(A2UA3UA4) - #(A1UA2UA3UA4) Mas, por simetria, cada termo desses soh depende de QUANTOS conjuntos aparecem naquela uniao -- mais exatamente, os termos com 1 indice sao 8! (pois fixamos um termo, os outros podem ser permutados de qualquer jeito), os com 2 indices sao 7! (dois numeros fixos, os outros como quisermos), e assim por diante. Portanto: #(A1UA2UA3UA4) = C(4,1).8! - C(4,2) . 7! + C(4,3).6! - 5! Bom, isso sao as permutacoes em que PELO MENOS um dos 4 numeros estah fixo. Como queremos o contrario (NENHUM fica fixo), a reposta eh: #(permutacoes) = 9! - (4. 8! - C(4,2) . 7! + 4 . 6! - 5!) Acho que agora ficou *bem* melhor escrito! :D Abraco, Ralph. On Thu, Apr 25, 2019 at 4:44 PM Pedro Lazéra wrote: > Ralph, eu fiquei com uma dúvida. > > Apesar de a sua resposta bater com o gabarito, os termos que você > expressou com números batem mesmo com os termos que você expressou com > palavras? Por exemplo, "#(permutações que pelo menos 1 dos pares fica no > lugar)" = "4.8!" ? Eu tenho a impressão que "4.8!" é maior, porque contou, > por exemplo, a sequência (1,2,3,4,5,6,7,8,9) mais de uma vez. > > Por exemplo, se o mesmo enunciado fosse aplicado a 1,2,3,4, você acharia > como resposta, por analogia, 4! - 2*3! + C(2,2)*2! = 14, que é a resposta > certa, mas "#(permutações que pelo menos 1 dos pares fica no lugar)" = 10, > que é diferente de "2*3!". Não? Neste caso, 2*3! conta (1,2,3,4) e > (3,2,1,4) duas vezes. > > Abraços, > Pedro > > On Thu, Apr 25, 2019 at 2:32 PM Ralph Teixeira wrote: > >> Por inclusão-exclusão, eu achei: >> >> #(permutações) = #(total) - #(permutações em que pelo menos um dos pares >> fica no lugar) + #(permutações que pelo menos 2 dos pares ficam no lugar) - >> #(permutações que pelo menos 3 dos pares ficam no lugar) + #(permutações em >> que todos os pares ficam no lugar) >> = 9! - 4.8! + C(4,2).7! - C(4,3). 6! +5! = 229080 >> >> On Thu, Apr 25, 2019 at 7:03 AM Vanderlei Nemitz >> wrote: >> >>> Bom dia! >>> >>> Resolvi a questão a seguir, encontrei como resposta 229080, mas >>> encontrei essa resposta em uma lista e 133800 em outra. Gostaria de >>> confirmar qual é a correta. Para mim, 133800 é o número de permutações em >>> que pelo menos um algarismo par permanece em sua posição original. >>> >>> Muito obrigado! >>> >>> >>> *De quantas maneiras podemos permutar os inteiros 1, 2, 3, 4, 5, 6, 7, >>> 8, 9 de forma que nenhum inteiro par fique em sua posição natural?* >>> >>> -- >>> 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] Combinatória (permutações)
Ralph, eu fiquei com uma dúvida. Apesar de a sua resposta bater com o gabarito, os termos que você expressou com números batem mesmo com os termos que você expressou com palavras? Por exemplo, "#(permutações que pelo menos 1 dos pares fica no lugar)" = "4.8!" ? Eu tenho a impressão que "4.8!" é maior, porque contou, por exemplo, a sequência (1,2,3,4,5,6,7,8,9) mais de uma vez. Por exemplo, se o mesmo enunciado fosse aplicado a 1,2,3,4, você acharia como resposta, por analogia, 4! - 2*3! + C(2,2)*2! = 14, que é a resposta certa, mas "#(permutações que pelo menos 1 dos pares fica no lugar)" = 10, que é diferente de "2*3!". Não? Neste caso, 2*3! conta (1,2,3,4) e (3,2,1,4) duas vezes. Abraços, Pedro On Thu, Apr 25, 2019 at 2:32 PM Ralph Teixeira wrote: > Por inclusão-exclusão, eu achei: > > #(permutações) = #(total) - #(permutações em que pelo menos um dos pares > fica no lugar) + #(permutações que pelo menos 2 dos pares ficam no lugar) - > #(permutações que pelo menos 3 dos pares ficam no lugar) + #(permutações em > que todos os pares ficam no lugar) > = 9! - 4.8! + C(4,2).7! - C(4,3). 6! +5! = 229080 > > On Thu, Apr 25, 2019 at 7:03 AM Vanderlei Nemitz > wrote: > >> Bom dia! >> >> Resolvi a questão a seguir, encontrei como resposta 229080, mas encontrei >> essa resposta em uma lista e 133800 em outra. Gostaria de confirmar qual é >> a correta. Para mim, 133800 é o número de permutações em que pelo menos um >> algarismo par permanece em sua posição original. >> >> Muito obrigado! >> >> >> *De quantas maneiras podemos permutar os inteiros 1, 2, 3, 4, 5, 6, 7, 8, >> 9 de forma que nenhum inteiro par fique em sua posição natural?* >> >> -- >> 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] Combinatória (permutações)
Por inclusão-exclusão, eu achei: #(permutações) = #(total) - #(permutações em que pelo menos um dos pares fica no lugar) + #(permutações que pelo menos 2 dos pares ficam no lugar) - #(permutações que pelo menos 3 dos pares ficam no lugar) + #(permutações em que todos os pares ficam no lugar) = 9! - 4.8! + C(4,2).7! - C(4,3). 6! +5! = 229080 On Thu, Apr 25, 2019 at 7:03 AM Vanderlei Nemitz wrote: > Bom dia! > > Resolvi a questão a seguir, encontrei como resposta 229080, mas encontrei > essa resposta em uma lista e 133800 em outra. Gostaria de confirmar qual é > a correta. Para mim, 133800 é o número de permutações em que pelo menos um > algarismo par permanece em sua posição original. > > Muito obrigado! > > > *De quantas maneiras podemos permutar os inteiros 1, 2, 3, 4, 5, 6, 7, 8, > 9 de forma que nenhum inteiro par fique em sua posição natural?* > > -- > 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] Combinatória (permutações)
Bom dia! Resolvi a questão a seguir, encontrei como resposta 229080, mas encontrei essa resposta em uma lista e 133800 em outra. Gostaria de confirmar qual é a correta. Para mim, 133800 é o número de permutações em que pelo menos um algarismo par permanece em sua posição original. Muito obrigado! *De quantas maneiras podemos permutar os inteiros 1, 2, 3, 4, 5, 6, 7, 8, 9 de forma que nenhum inteiro par fique em sua posição natural?* -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
[obm-l] Permutações caóticas
Amigos, Discutindo a solução de uma questão que dizia: "Cinco livros caem de uma prateleira. De quantas maneiras podem ser recolocados sem que nehum livro ocupe a posição anterior?". Bom...a solução foi 5![1/0! - 1/1! +...-1/5!] = 44 Aí vem a pergunta de aluno: "Tem como calcular por exemplo anagramas de uma palavra como MISSISSIPE onde nenhuma letra está no lugar correto utilizando as permutações caóticas?" Gostaria de uma dica para pensar.. Muito obrigado. --
[obm-l] PERMUTAÇÕES CAÓTICAS!
Turma! Não percam a excelente oportunidade de conferir na RPM-15 uma elegante elucidação de autoria do Gugu à respeito do já tão debatido problema do amigo oculto com direito ao Teorema do "da Silva". De quebra, vejam a seção "probleminhas" em que fui homenageado com distinção. Seja uma brincadeira de "amigo oculto", na qual n pessoas escrevem seu nome num pedaço de papel e o depositam num recipiente, de onde cada um pega aleatoriamente um dos pedaços de papel. Qual a probabilidade de ninguém pegar seu próprio nome? E qual a probabilidade de alguém tirar a si mesmo? Tem-se em duas urnas 23 bolas numeradas. Qual a probabilidade de que saquemos as 23, uma a uma, numa ordem pré-fixada? A propósito, qual a probabilidade de alguém tirar a si mesmo dentre 9 pessoas? Boas Festas! _ Você sabia que com o seu MSN Messenger você faz ligações de PC-papa- PC, grátis e para qualquer lugar do mundo? É só acessar http://imagine-msn.com/messenger/default2.aspx?locale=pt-br = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
[obm-l] Permutações pares e ímpares
Caro João Carlos: Uma explicação simplista seria a seguinte: Considere o conjunto In = {1,2,3,...,n} Uma permutação de In nada mais é do que uma bijeção de In em In. No entanto, do ponto de vista notacional, é conveniente representar uma permutação como sendo uma matriz 2 x n, onde a primeira linha é: 1 2 3 4 ... n-1 n e a segunda linha, a permutação desejada dos elementos de In, tal como por exemplo: 2 3 1 4 ... n-1 n (ou seja, uma permutação que leva 1 em 2, 2 em 3, 3 em 1, e fixa os demais elementos de In) A fim de verificar a paridade da permutação, você só precisa "ligar pontos", ou seja, traçar n linhas ligando números iguais nas linhas superior e inferior (de forma que no máximo duas das linhas traçadas se interceptem num mesmo ponto). Se o número de pontos de interseção for par, a permutação será par, caso contrário será ímpar. Assim, a permutação do exemplo é par (2 pontos de interseçao: 1-1 com 2-2, e 1-1 com 3-3). Outros exemplos (em I5): 1 2 3 4 5 5 4 3 2 1 ==> 10 pontos de interseção ==> PAR 1 2 3 4 5 2 3 1 5 4 ==> 3 pontos de interseção ==> ÍMPAR 1 2 3 4 5 5 1 2 4 3==> 5 pontos de interseção ==> ÍMPAR Uma explicação mais detalhada deverá envolver alguns conceitos simples tais como ciclos e transposições. Por exemplo, você pode dar uma olhada em http://www.fc.up.pt/mp/clomp/chapter4.pdf - um arquivo pdf que trata disso tudo. Existem várias outras referências on-line, mas são em inglês. Se você quiser eu posso te indicar. Espero ter ajudado. Um abraço, Claudio. = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é <[EMAIL PROTECTED]> =
[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Determinantes e Permutações pares e ímpares
Olá Ricardo e demais participantes desta discussão! Considere o conjunto de todas as permutações de (1234): (1243), (3214), ... cada permutação dessas pode ser representada com uma bijeção f:{1,2,3,4}->{1,2,3,4}. Por exemplo, em (1243) a função seria f(1)=1, f(2)=2, f(3)=4, f(4)=3. Pode-se pensar, então, em construir uma operação com as permutações, através da composição de funções. Vou dar um exemplo (1243) é representado por f(1)=1, f(2)=2, f(3)=4, f(4)=3 (3214) é representado por g(1)=3, g(2)=2, g(3)=1, g(4)=4 (1243) * (3241) é representado pela composta h = f o g, h(1)=4, h(2)=2, h(3)=1, h(4)=3 portanto (1243) * (3241) = (4213) Das operações tradicionais com funções, se conclui que "*" é associativa a*(b*c)=(a*b)*c, não é em geral comutativa, se considerarmos identidade = i = (1234) temos a * i = i * a = a para todo a e toda permutação tem uma inversa a^(-1) tal que a * a^(-1) = a^(-1) * a = i. Vamos definir uma função N:permutações->naturais que conta numa determinada permutação p, quantos são os pares de números da esquerda para a direita na permutação estão com o primeiro elemento maior. Em (1234) temos cada par na ordem certa, portanto N(1234)=0. Em (3241), temos os pares (32), (31), (21), (41) com o primeiro elemento maior portanto N(3241)=4. Agora temos um resultado que é simples LEMA. Cada vez que trocamos dois números de posição numa permutação p e obtemos uma nova permutação p', o número N(p)-N(p') é ímpar. (por exemplo, de p=(1234) com N(p) = 0 substituinto 1 e 3, obtemos p'=(3214) com N(p')=3) Com base neste lema fazemos a seguinte definição, que é consistente DEFINIÇÃO. Dizemos que uma permutação p é PAR (ÍMPAR) se a quantidade de trocas que se precisa fazer com seus elementos para se chegar à i = identidade é PAR (ÍMPAR). Ou o que é no mesmo, p é PAR (ÍMPAR) se N(p) é um número PAR (ÍMPAR). O sgn(p) = 1 se p é PAR e -1 se p é ÍMPAR. Pode-se mostrar que para cada permutação p, existe uma matriz M (reordenação das colunas da identidade) que seu efeito sobre um vetor da base canônica é o mesmo que de p sobre o seu índice M(e_i) = e_(f(i)) onde f é a função associada a p, e que det(M) = sgn(p). A composição de matrizes se relaciona com a composição de funções, e daí sgn(a*b)=sgn(a)*sgn(b). Espero ter ajudado! Eduardo. From: RICARDO CHAVES Esse tal de signum da permutaçao e voce fazer o produtorio >From: [EMAIL PROTECTED] >Reply-To: [EMAIL PROTECTED] >To: [EMAIL PROTECTED] >Subject: Re: [obm-l] Re: [obm-l] Determinantes e Permutações pares e ímpares >Date: Wed, 5 Feb 2003 07:10:34 -0400 > > > "Cláudio \(Prática\)" > > ora.com.br> cc: > Enviado Por: Assunto: [obm-l] Re: [obm-l] Determinantes e Permutações > [EMAIL PROTECTED] pares e ímpares > .puc-rio.br > > > 04/02/2003 06:12 > Favor responder a > obm-l > > > > > > > > > Querido Cláudio, > > > > Obrigado! Com sinceridade, obrigado! O conhecimento real, presente, é > > o que possuímos, fora isto, estamos no passado. Por isso, agradeço sua > > colaboração, com a qual atualizo-me e avanço. > > Cláudio, não sei a definição de permutações pares e ímpares, não sei > > quando o sinal ? sgn(p) - será positivo ou negativo. > > Desta forma, gostaria de receber mais de suas belas explicações. > > Desde já, muito grato, João Carlos. > O signum e uma especie de produtorio com uns termos do tipo p(x)-p(y)/x-y . > > >Caro João Carlos: > >A fórmula geral para o determinante de uma matriz A (n x n) é a seguinte: > >det(A) = SOMATÓRIO sgn(p) * A(1,p(1)) * A(2,p(2)) * ... * A(n,p(n)) > p em Sn > >onde A(i,j) é o elemento da linha i e coluna j, sgn(p) = sinal da >permutação >"p" (+1 se p é par, -1 se p >é ímopar) e onde a soma é tomada sobre cada permutação p dos números 1, 2, >..., n (o conjunto de todas estas permutações é comumente denominado Sn) >ou >seja, é uma soma de n! termos, cada um deles igual ao produto de n >elementos >da matriz. > >Assim, para n >= 4 esta fórmula, apesar de correta (é, de fato, a definição >de determinante) é muito trabalhosa de se aplicar. No entanto, existem >alguns teoremas sobre determinantes - tais como expansão de Laplace ou >sobre >o efeito de operações elementares com linhas e colunas - que permitem que >você reduza o problema ao cálculo de determinantes de ordem menor. > >O que deve estar acontecendo é que, com n >= 4, o número de termos é >= 24 >e >talvez você esteja esquecendo algum termo ou trocando algum sinal. > >Espero que isso ajude. > >Um abraço, >Claudio. > > >- Original Message - >From: >To: >Sent: Monday, February 03, 2003 4:08 PM >Subject: [obm-l] Determinantes e Permutações pares e ímpares > > >No volume 3, A Matemática do Ensino Médio da SBM, p. 137, há regra
[obm-l] Re: [obm-l] Re: [obm-l] Determinantes e Permutações pares e ímpares
Esse tal de signum da permutaçao e voce fazer o produtorio >From: [EMAIL PROTECTED] >Reply-To: [EMAIL PROTECTED] >To: [EMAIL PROTECTED] >Subject: Re: [obm-l] Re: [obm-l] Determinantes e Permutações pares e ímpares >Date: Wed, 5 Feb 2003 07:10:34 -0400 > > > "Cláudio \(Prática\)" > > ora.com.br> cc: > Enviado Por: Assunto: [obm-l] Re: [obm-l] Determinantes e Permutações > [EMAIL PROTECTED] pares e ímpares > .puc-rio.br > > > 04/02/2003 06:12 > Favor responder a > obm-l > > > > > > > > > Querido Cláudio, > > > > Obrigado! Com sinceridade, obrigado! O conhecimento real, presente, é > > o que possuímos, fora isto, estamos no passado. Por isso, agradeço sua > > colaboração, com a qual atualizo-me e avanço. > > Cláudio, não sei a definição de permutações pares e ímpares, não sei > > quando o sinal ? sgn(p) - será positivo ou negativo. > > Desta forma, gostaria de receber mais de suas belas explicações. > > Desde já, muito grato, João Carlos. > O signum e uma especie de produtorio com uns termos do tipo p(x)-p(y)/x-y . > > >Caro João Carlos: > >A fórmula geral para o determinante de uma matriz A (n x n) é a seguinte: > >det(A) = SOMATÓRIO sgn(p) * A(1,p(1)) * A(2,p(2)) * ... * A(n,p(n)) > p em Sn > >onde A(i,j) é o elemento da linha i e coluna j, sgn(p) = sinal da >permutação >"p" (+1 se p é par, -1 se p >é ímopar) e onde a soma é tomada sobre cada permutação p dos números 1, 2, >..., n (o conjunto de todas estas permutações é comumente denominado Sn) >ou >seja, é uma soma de n! termos, cada um deles igual ao produto de n >elementos >da matriz. > >Assim, para n >= 4 esta fórmula, apesar de correta (é, de fato, a definição >de determinante) é muito trabalhosa de se aplicar. No entanto, existem >alguns teoremas sobre determinantes - tais como expansão de Laplace ou >sobre >o efeito de operações elementares com linhas e colunas - que permitem que >você reduza o problema ao cálculo de determinantes de ordem menor. > >O que deve estar acontecendo é que, com n >= 4, o número de termos é >= 24 >e >talvez você esteja esquecendo algum termo ou trocando algum sinal. > >Espero que isso ajude. > >Um abraço, >Claudio. > > >- Original Message ----- >From: <[EMAIL PROTECTED]> >To: <[EMAIL PROTECTED]> >Sent: Monday, February 03, 2003 4:08 PM >Subject: [obm-l] Determinantes e Permutações pares e ímpares > > >No volume 3, A Matemática do Ensino Médio da SBM, p. 137, há regra de >cálculo determinantes por meio de permutações pares e ímpares. Porém, não >estou conseguindo aplicá-la para matrizes quadradas de ordem maior ou igual >a 4. Expliquem-me. > > > ATT. João Carlos > >= >Instruções para entrar na lista, sair da lista e usar a lista em >http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html >O administrador desta lista é <[EMAIL PROTECTED]> >= > >= >Instruções para entrar na lista, sair da lista e usar a lista em >http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html >O administrador desta lista é <[EMAIL PROTECTED]> >= > > > > >= >Instruções para entrar na lista, sair da lista e usar a lista em >http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html >O administrador desta lista é <[EMAIL PROTECTED]> >= MSN Hotmail, o maior webmail do Brasil. Faça o seu agora. smart spam protection and 2 months FREE* = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é <[EMAIL PROTECTED]> =
[obm-l] Re: [obm-l] Determinantes e Permutações pares e ímpares
Caro João Carlos: A fórmula geral para o determinante de uma matriz A (n x n) é a seguinte: det(A) = SOMATÓRIO sgn(p) * A(1,p(1)) * A(2,p(2)) * ... * A(n,p(n)) p em Sn onde A(i,j) é o elemento da linha i e coluna j, sgn(p) = sinal da permutação "p" (+1 se p é par, -1 se p é ímopar) e onde a soma é tomada sobre cada permutação p dos números 1, 2, ..., n (o conjunto de todas estas permutações é comumente denominado Sn) ou seja, é uma soma de n! termos, cada um deles igual ao produto de n elementos da matriz. Assim, para n >= 4 esta fórmula, apesar de correta (é, de fato, a definição de determinante) é muito trabalhosa de se aplicar. No entanto, existem alguns teoremas sobre determinantes - tais como expansão de Laplace ou sobre o efeito de operações elementares com linhas e colunas - que permitem que você reduza o problema ao cálculo de determinantes de ordem menor. O que deve estar acontecendo é que, com n >= 4, o número de termos é >= 24 e talvez você esteja esquecendo algum termo ou trocando algum sinal. Espero que isso ajude. Um abraço, Claudio. - Original Message - From: <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> Sent: Monday, February 03, 2003 4:08 PM Subject: [obm-l] Determinantes e Permutações pares e ímpares No volume 3, A Matemática do Ensino Médio da SBM, p. 137, há regra de cálculo determinantes por meio de permutações pares e ímpares. Porém, não estou conseguindo aplicá-la para matrizes quadradas de ordem maior ou igual a 4. Expliquem-me. ATT. João Carlos = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é <[EMAIL PROTECTED]> = = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é <[EMAIL PROTECTED]> =
[obm-l] Determinantes e Permutações pares e ímpares
No volume 3, A Matemática do Ensino Médio da SBM, p. 137, há regra de cálculo determinantes por meio de permutações pares e ímpares. Porém, não estou conseguindo aplicá-la para matrizes quadradas de ordem maior ou igual a 4. Expliquem-me. ATT. João Carlos = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é <[EMAIL PROTECTED]> =
[obm-l] Re: [obm-l] permutações circulares com repetição
licar as propriedades verificaveis das coisas e nao para impor propriedades a elas " (NEWTON) Um abraco Paulo Santa Rita 3,1304,210502 >From: Rafael WC <[EMAIL PROTECTED]> >Reply-To: [EMAIL PROTECTED] >To: [EMAIL PROTECTED] >Subject: Re: [obm-l] permutações circulares com repetição >Date: Mon, 20 May 2002 14:55:57 -0700 (PDT) > >Olá Pessoal! > >Obrigado Morgado e Paulo pela ajuda. > >Paulo, entrei na página que você indicou. Encontrei a >demonstração de um teorema de Moreau que sinceramente >não consegui associar nem de longe com permutações >circulares com repetição. > >Como você falou que conhece um caminho alternativo, >acho que vou abusar da sua boa vontade e perguntar >qual é. Se puder me ajudar, agradeço muito. Hoje fui à >biblioteca da faculdade e andei procurando alguns >livros, mas todos param nas permutações circulares >simples!! > >Muito obrigado, > >Rafael. _ Converse com amigos on-line, conheça o MSN Messenger: http://messenger.msn.com = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é <[EMAIL PROTECTED]> =
Re: [obm-l] permutações circulares com repetição
Olá Pessoal! Obrigado Morgado e Paulo pela ajuda. Paulo, entrei na página que você indicou. Encontrei a demonstração de um teorema de Moreau que sinceramente não consegui associar nem de longe com permutações circulares com repetição. Como você falou que conhece um caminho alternativo, acho que vou abusar da sua boa vontade e perguntar qual é. Se puder me ajudar, agradeço muito. Hoje fui à biblioteca da faculdade e andei procurando alguns livros, mas todos param nas permutações circulares simples!! Muito obrigado, Rafael. --- Paulo Santa Rita <[EMAIL PROTECTED]> wrote: > Ola Rafael e demais > colegas desta lista, > > Voce pode ver o TEOREMA DE MOREAU em : > > http://anduril.eupvg.upc.es/~joan/documents/moreau.htm > > Se mesmo assim voce nao se esclarecer eu conheco um > caminho alternativo a > este teorema. > > Um abraco > Paulo Santa Rita > 2,1245,200502 > > > >From: Augusto Cesar de Oliveira Morgado > <[EMAIL PROTECTED]> > >Reply-To: [EMAIL PROTECTED] > >To: [EMAIL PROTECTED] > >Subject: Re: [obm-l] permutações circulares com > repetição > >Date: Mon, 20 May 2002 12:05:15 -0300 (EST) > > > >Procure o Teorema de Moreau. > > > >Em Sat, 18 May 2002 18:51:57 -0700 (PDT), Rafael WC > <[EMAIL PROTECTED]> > >disse: > > > > > Estou com problemas para resolver esse > exercício: > > > > > > "De quantas maneiras distintas podemos dispor ao > longo > > > de um circulo, suposto fixo, 6 bolas brancas, 8 > bolas > > > azuis, 16 bolas verdes e 24 bolas amarelas?" > > > O círculo fica fixo em nossa frente, mas as > bolas > > > ficam livres para serem rotacionadas como em uma > > > catraca de bicicleta. > > > > > > Pra mim, entendi como sendo uma permutação > circular > > > com repetição. Nunca estudei isso e o que pensei > que > > > seria mais lógico não deu muito certo. Pensei > que > > > faríamos as permutações com repetições e > dividiríamos > > > pelo total de bolas por causa de ser circular. > Em > > > alguns casos até que conferiu com a resposta, > mas aí > > > coloquei um teste com apenas 4 bolas, duas > brancas e > > > duas azuis. > > > > > > Se eu fosse fazer como pensei, seria: > > > PC4(2,2) = 4!/4.2!.2! = 3/2 > > > > > > Nem inteiro dá!!! > > > > > > Ao fazer escrevendo mesmo, vejo que só temos 6 > > > permutações: > > > 1 - AABB > > > 2 - ABAB > > > 3 - ABBA > > > 4 - BAAB > > > 5 - BABA > > > 6 - BBAA > > > > > > E destas, se considerarmos como circulares, > vemos que > > > 1 = 3 = 4 = 6 e 2 = 5. O que nos dá apenas 2 > > > permutações. > > > > > > Alguém sabe como resolvo esse tipo de problema? > O > > > único livro que tenho aqui sobre análise > combinatória > > > (Introdução à Análise Combinatória; Santos, J. > P. O.; > > > Mello, M. P.; Murari, I. T. C.; 2ª edição; > Campinas, > > > SP; Ed. da Unicamp, 1988) que aliás é muito bom, > não > > > fala sobre permutações circulares com > combinação. > > > > > > Agradeço qualquer dica. > > > > > > Rafael. > > > > > > = > > > Rafael Werneck Cinoto > > >ICQ# 107011599 > > > [EMAIL PROTECTED] > > >[EMAIL PROTECTED] > > >[EMAIL PROTECTED] > > > http://www.rwcinoto.hpg.com.br/ > > > > > > > __ > > > Do You Yahoo!? > > > LAUNCH - Your Yahoo! Music Experience > > > http://launch.yahoo.com > > > > >= > > > Instruções para entrar na lista, sair da lista e > usar a lista em > > > > http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html > > > O administrador desta lista é > <[EMAIL PROTECTED]> > > > > >= > > > > > > > > > >= > >Instruções para entrar na lista, sair da lista e > usar a lista em > >http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html > >O administrador desta lista é > <[EMAIL PROTECTED]> > >= > > > > > _ > Envie e receba emails com o Hotm
Re: [obm-l] permutações circulares com repetição
Procure o Teorema de Moreau. Em Sat, 18 May 2002 18:51:57 -0700 (PDT), Rafael WC <[EMAIL PROTECTED]> disse: > Estou com problemas para resolver esse exercício: > > "De quantas maneiras distintas podemos dispor ao longo > de um circulo, suposto fixo, 6 bolas brancas, 8 bolas > azuis, 16 bolas verdes e 24 bolas amarelas?" > O círculo fica fixo em nossa frente, mas as bolas > ficam livres para serem rotacionadas como em uma > catraca de bicicleta. > > Pra mim, entendi como sendo uma permutação circular > com repetição. Nunca estudei isso e o que pensei que > seria mais lógico não deu muito certo. Pensei que > faríamos as permutações com repetições e dividiríamos > pelo total de bolas por causa de ser circular. Em > alguns casos até que conferiu com a resposta, mas aí > coloquei um teste com apenas 4 bolas, duas brancas e > duas azuis. > > Se eu fosse fazer como pensei, seria: > PC4(2,2) = 4!/4.2!.2! = 3/2 > > Nem inteiro dá!!! > > Ao fazer escrevendo mesmo, vejo que só temos 6 > permutações: > 1 - AABB > 2 - ABAB > 3 - ABBA > 4 - BAAB > 5 - BABA > 6 - BBAA > > E destas, se considerarmos como circulares, vemos que > 1 = 3 = 4 = 6 e 2 = 5. O que nos dá apenas 2 > permutações. > > Alguém sabe como resolvo esse tipo de problema? O > único livro que tenho aqui sobre análise combinatória > (Introdução à Análise Combinatória; Santos, J. P. O.; > Mello, M. P.; Murari, I. T. C.; 2ª edição; Campinas, > SP; Ed. da Unicamp, 1988) que aliás é muito bom, não > fala sobre permutações circulares com combinação. > > Agradeço qualquer dica. > > Rafael. > > = > Rafael Werneck Cinoto >ICQ# 107011599 > [EMAIL PROTECTED] >[EMAIL PROTECTED] >[EMAIL PROTECTED] > http://www.rwcinoto.hpg.com.br/ > > __ > Do You Yahoo!? > LAUNCH - Your Yahoo! Music Experience > http://launch.yahoo.com > = > Instruções para entrar na lista, sair da lista e usar a lista em > http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html > O administrador desta lista é <[EMAIL PROTECTED]> > = > > = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é <[EMAIL PROTECTED]> =
[obm-l] permutações circulares com repetição
Estou com problemas para resolver esse exercício: "De quantas maneiras distintas podemos dispor ao longo de um circulo, suposto fixo, 6 bolas brancas, 8 bolas azuis, 16 bolas verdes e 24 bolas amarelas?" O círculo fica fixo em nossa frente, mas as bolas ficam livres para serem rotacionadas como em uma catraca de bicicleta. Pra mim, entendi como sendo uma permutação circular com repetição. Nunca estudei isso e o que pensei que seria mais lógico não deu muito certo. Pensei que faríamos as permutações com repetições e dividiríamos pelo total de bolas por causa de ser circular. Em alguns casos até que conferiu com a resposta, mas aí coloquei um teste com apenas 4 bolas, duas brancas e duas azuis. Se eu fosse fazer como pensei, seria: PC4(2,2) = 4!/4.2!.2! = 3/2 Nem inteiro dá!!! Ao fazer escrevendo mesmo, vejo que só temos 6 permutações: 1 - AABB 2 - ABAB 3 - ABBA 4 - BAAB 5 - BABA 6 - BBAA E destas, se considerarmos como circulares, vemos que 1 = 3 = 4 = 6 e 2 = 5. O que nos dá apenas 2 permutações. Alguém sabe como resolvo esse tipo de problema? O único livro que tenho aqui sobre análise combinatória (Introdução à Análise Combinatória; Santos, J. P. O.; Mello, M. P.; Murari, I. T. C.; 2ª edição; Campinas, SP; Ed. da Unicamp, 1988) que aliás é muito bom, não fala sobre permutações circulares com combinação. Agradeço qualquer dica. Rafael. = Rafael Werneck Cinoto ICQ# 107011599 [EMAIL PROTECTED] [EMAIL PROTECTED] [EMAIL PROTECTED] http://www.rwcinoto.hpg.com.br/ __ Do You Yahoo!? LAUNCH - Your Yahoo! Music Experience http://launch.yahoo.com = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é <[EMAIL PROTECTED]> =
Re: Permutações caóticas
Olá Nicolau e Franklin, A referência pedida pelo Nicolau vai abaixo: LIVRO: ANALISE COMBINATÓRIA E PROBABILIDADE DA COLEÇÃO DO PROFESSOR DE MATEMÁTICA DA SOCIEDADE BRASILEIRA DE MATEMÁTICA AUTORES: AUGUSTO MORGADO JOÃO PITOMBEIRA DE CARVALHO, PAULO CEZAR PINTO CARVALHO PEDRO FENANDEZ LER DA PAGINA 49 A 62. PONCE > On Sat, 2 Sep 2000, Franklin de Lima Marquezino wrote: > > > Olá, > > > > Há algum tempo eu perguntei nesta lista, como se calcula permutações > > caóticas, e ninguém me respondeu até hoje. Estou no 3º ano do ensino > > médio, e sei que minha pergunta pode ter sido um pouco idiota. Porém, eu > > já havia comentado esta minha dúvida com alguns de meus amigos, que > > também participam desta lista, e nenhum deles soube responder. Então, > > como vocês dizem que aqui predomina a solidariedade e a cooperação, eu > > pensei que não houvesse problema em compartilhar minha dúvida, por mais > > simples que fosse. Caso alguém tenha tempo, por favor, responda. > > > > > >Até logo, > > > > > > Franklin > > > > > > Sua pergunta não tem nada de idiota. Não sei mais se você foi a pessoa > que perguntou sobre os anagramas da palavra MATEMATICA onde não há > nenhuma coincidência de letra em nenhuma das posições: > esta pergunta eu pensei um pouco sobre ela e só não respondi por que > achei trabalhosa (apesar de ser interessante). > Mas se você está perguntando sobre permutações caóticas na situação > simples, nenhum elemento repetido, a resposta é: > > n!(1/0! - 1/1! + 1/2! - 1/3! + ... + (-1)^n 1/n!) > > que é o inteiro mais próximo de n!/e. > A demonstração é feita pelo princípio da inclusão e exclusão > e só não repito aqui agora pq acho que alguém já tem isso pronto > escrito em algum lugar. Se ninguém der referência ou se a referência > não for acessível eu demonstro aqui. > > []s, N.
Re: Permutações caóticas
Leia o meu artigo "O problema do amigo oculto", na revista do Professor de Matematica, no 28, que eh exatamente sobre isto. JP -Mensagem original-De: Franklin de Lima Marquezino <[EMAIL PROTECTED]>Para: [EMAIL PROTECTED] <[EMAIL PROTECTED]>Data: Sábado, 2 de Setembro de 2000 09:08Assunto: Permutações caóticas Olá, Há algum tempo eu perguntei nesta lista, como se calcula permutações caóticas, e ninguém me respondeu até hoje. Estou no 3º ano do ensino médio, e sei que minha pergunta pode ter sido um pouco idiota. Porém, eu já havia comentado esta minha dúvida com alguns de meus amigos, que também participam desta lista, e nenhum deles soube responder. Então, como vocês dizem que aqui predomina a solidariedade e a cooperação, eu pensei que não houvesse problema em compartilhar minha dúvida, por mais simples que fosse. Caso alguém tenha tempo, por favor, responda. Até logo, Franklin
Re: Permutações caóticas
On Sat, 2 Sep 2000, Franklin de Lima Marquezino wrote: > Olá, > > Há algum tempo eu perguntei nesta lista, como se calcula permutações > caóticas, e ninguém me respondeu até hoje. Estou no 3º ano do ensino > médio, e sei que minha pergunta pode ter sido um pouco idiota. Porém, eu > já havia comentado esta minha dúvida com alguns de meus amigos, que > também participam desta lista, e nenhum deles soube responder. Então, > como vocês dizem que aqui predomina a solidariedade e a cooperação, eu > pensei que não houvesse problema em compartilhar minha dúvida, por mais > simples que fosse. Caso alguém tenha tempo, por favor, responda. > > >Até logo, > > > Franklin > > Sua pergunta não tem nada de idiota. Não sei mais se você foi a pessoa que perguntou sobre os anagramas da palavra MATEMATICA onde não há nenhuma coincidência de letra em nenhuma das posições: esta pergunta eu pensei um pouco sobre ela e só não respondi por que achei trabalhosa (apesar de ser interessante). Mas se você está perguntando sobre permutações caóticas na situação simples, nenhum elemento repetido, a resposta é: n!(1/0! - 1/1! + 1/2! - 1/3! + ... + (-1)^n 1/n!) que é o inteiro mais próximo de n!/e. A demonstração é feita pelo princípio da inclusão e exclusão e só não repito aqui agora pq acho que alguém já tem isso pronto escrito em algum lugar. Se ninguém der referência ou se a referência não for acessível eu demonstro aqui. []s, N.
Permutações caóticas
Olá, Há algum tempo eu perguntei nesta lista, como se calcula permutações caóticas, e ninguém me respondeu até hoje. Estou no 3º ano do ensino médio, e sei que minha pergunta pode ter sido um pouco idiota. Porém, eu já havia comentado esta minha dúvida com alguns de meus amigos, que também participam desta lista, e nenhum deles soube responder. Então, como vocês dizem que aqui predomina a solidariedade e a cooperação, eu pensei que não houvesse problema em compartilhar minha dúvida, por mais simples que fosse. Caso alguém tenha tempo, por favor, responda. Até logo, Franklin
Permutações caóticas
Por favor, gostaria que alguém me explicasse como se calcula permutações caóticas. Desde já, agradeço. Franklin
Permutações
Desculpem, eu cometi um erro crasso no último e-mail. Como devem ter visto, eu calculei permutações de 2 "b"s e um "c" e esqueci de considerar os elementos repetidos. As possibilidades só são 3. {b,b,c,a,a,a} {b,c,b,a,a,a} {c,b,b,a,a,a}. E o que o Grande Nicolau observou está certo. Isso equivale a achar anagramas em que a posição de uma letra qualquer deve mudar.Por exemplo, Matematica -> tamitacema não seria uma resposta. Quanto à divisão da lista, eu não acho que isso deveria acontecer. Não há motivo para se oprimir com as integrais e os limites. Veja o meu caso. Estou na oitava e estão tão dispostos a resolver minhas dúvidas (inclusive Nicolau, o Grande) de uma forma que eu possa entender que às vezes eu acho que devia mandar menos e-mails, para tomar-lhes menos tempo.
Re: Permutações caóticas
On Thu, 17 Aug 2000, Jorge Peixoto Morais wrote: > Nicolau, eu achei estranha a pergunta que você fez, pois você, em um e-mail, > é quem me ensinou o que é permutação caótica quando eu estava na sétima. A > sua definição foi exatamente igual (até as palavras foram semelhantes) à do > Marcos Paulo. E, se o conjunto tem elementos repetidos, dois elementos iguais > não podem (na minha definição) ocupar o lugar um do outro nem o lugar > original. As dúvidas surgem por causa dos elemento repetidos. > Por exemplo, em {a,a,a,b,b,c} as possibilidades são 6, pois os 3 > elementos "a" têm que ir para as posições finais, e qualquer permutação de 3 > elementos iguais em três lugares possíveis é a permutação identidade. Os "Bs" > e o "c" podem ficar em qualquer dos 3 primeiros lugares, o que dá 3!=6 > possibilidades. Esta resposta por exemplo eu não entendi. A única formulação que até agora me foi clara foi quanto ao número de anagramas de uma dada palavra tais que em uma dada posição a letra que aparece na palavra original e no anagrama devem ser distintas. Ainda estou devendo resposta. []s, N.
Permutações caóticas
Nicolau, eu achei estranha a pergunta que você fez, pois você, em um e-mail, é quem me ensinou o que é permutação caótica quando eu estava na sétima. A sua definição foi exatamente igual (até as palavras foram semelhantes) à do Marcos Paulo. E, se o conjunto tem elementos repetidos, dois elementos iguais não podem (na minha definição) ocupar o lugar um do outro nem o lugar original. Por exemplo, em {a,a,a,b,b,c} as possibilidades são 6, pois os 3 elementos "a" têm que ir para as posições finais, e qualquer permutação de 3 elementos iguais em três lugares possíveis é a permutação identidade. Os "Bs" e o "c" podem ficar em qualquer dos 3 primeiros lugares, o que dá 3!=6 possibilidades. Marcos Eike, ainda estou ansiosamente esperando pela teoria da Gama! Por exemplo, por que ela converge para x negativo? como fatorial de x, x negativo, pode ser finitoE ainda por cima negativo!
Permutações caóticas
Dado um conjunto {1, 2, 3, 4, ..., n} entendo por permutação caótica qualquer permutação onde nenhum dos elementos encontra-se na ordem original. Ex.: 312 eh uma permutacaum caotica do conjunto {1, 2,3} e 321 naum eh pois o 2 estah na ordem inicila. Espero ter ajudado. []'s MP