[obm-l] Fatorial $via Stirling$
Prezado Paulo, Creio que não há como fazer a demonstração através de indução. Na internet, vi esse resultado. Não sei, contudo, se o desenvolvimento que o justifica está correto. É muito complexo. Ver, por exemplo, o site abaixo. http://en.wikipedia.org/wiki/Stirling's_approximation Grande abraço, Guilherme
[obm-l] Nosso calendario
Desculpem meter a colher torta em uma questao ja resolvida. Eh uma linda questao, e eu sempre comecava o meu curso de combinatoria com ela, para alunos do segundo ano do ensino medio. Como eles nao sao familiarizados com congruencias, eu utilizava a solucao do Niven - Ivan Niven, Mathematics of Choice, MAA (Mathematics Association of America, a minha edicao eh da decada de 70, deve haver uma mais recente). Eh linda, na verdade eh a mesma de voces, mas ele consegue evitar falar de congruencias com rara elegancia. Agora, que o cachorro morto ja foi devidamente espancado, so resta deixar osculos e amplexos de mim, olavo. Antonio Olavo da Silva Neto Date: Sun, 29 Aug 2010 10:32:59 -0300 Subject: Re: [obm-l] FW: Nosso calendario From: msbro...@gmail.com To: obm-l@mat.puc-rio.br Sim, apesar de ser imediato. Pois fevereiro ganha 1 dia.. logo, basta somar 1 nos devidos locais e ver que ainda temos todos os resíduos módulo 7. abraços, Salhab 2010/8/29 Hugo Fernando Marques Fernandes hfernande...@gmail.com Não faltou considerar os anos bissextos? Abraços. Hugo. Em 29 de agosto de 2010 00:26, marcone augusto araújo borges marconeborge...@hotmail.com escreveu: Obrigado,abraços. Date: Sat, 28 Aug 2010 23:41:47 -0300 Subject: Re: [obm-l] FW: Nosso calendario From: msbro...@gmail.com To: obm-l@mat.puc-rio.br Vamos ver a qtde de dias de cada mês, em ordem: 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 Analisando isso módulo 7, visto que são 7 dias da semana, temos: 28 == 0 (mod 7) 30 == 2 (mod 7) 31 == 3 (mod 7) Desta maneira, temos: 3, 0, 3, 2, 3, 2, 3, 3, 2, 3, 2, 3 Supondo que o primeiro dia 13 esteja em k, temos: k, k+3, k+3, k+6, k+8, k+11, k+13, k+16, k+19, k+21, k+24, k+26 Analisando mod 7, temos: k, k+3, k+3, k+6, k+1, k+4, k+6, k+2, k+5, k, k+3, k+5 Veja que temos todos os inteiros mod 7 somando com k. Desta maneira, sempre há uma sexta feira 13. abraços, Salhab 2010/8/28 marcone augusto araújo borges marconeborge...@hotmail.com From: marconeborge...@hotmail.com To: obm-l@mat.puc-rio.br Subject: Nosso calendario Date: Sun, 29 Aug 2010 02:12:05 + Mostre q em qualquer ano existe pelo menos uma sexta-feira 13.Eu acho q consegui resolver,mas gostaria de ver outra solução. Fiz assim:se o dia 13 de janeiro é um domingo,entao o dia 13 de setembro é uma sexta pois,contando apenas o numero de dias q passam de 28 em cada mes,a partir de janeiro(até agosto),encontramos 19 dias(um multiplo de 7 mais 5),dai,conside- rando o domingo como dia 1,temos 1+5=6(sexta).Usei o mesmo raciocinio para o caso do dia 13 de janeiro ser segunda,terça,quarta,quinta ou sabado e encontrei para cada caso uma sexta feira 13 no mesmo ano.
Re: [obm-l] Fatorial $via Stirling$
2010/9/16 Marcelo Salhab Brogliato msbro...@gmail.com:
Olá, Guilherme,
por indução:
Hipótese: ln(n!) = nln(n) - n + O(log(n))
Tese: ln((n+1)!) = (n+1)ln(n+1) - n + 1 + O(log(n+1))
Entretanto, vamos dar uma ajustada na tese.
Sabemos que 1 \in O(ln(n)), logo: 1 + O(ln(n+1)) = O(ln(n)).
Também sabemos que ln(n+1) + O(ln(n+1)) = O(ln(n+1)).
Assim:
Tese: ln((n+1)!) = nln(n+1) - n + O(ln(n+1))
Demo:
ln((n+1)!) = ln((n+1)n!) = ln(n+1) + ln(n!)
Usando a hipótese, temos:
ln((n+1)!) = ln(n+1) + nln(n) - n + O(ln(n))
Bem, como O(ln(n)) \subset O(ln(n+1)) e ln(n+1) \in O(ln(n+1)), temos:
ln((n+1)!) = nln(n) - n + O(ln(n+1))
Somando e subtraindo nln(n+1), temos:
ln((n+1)!) = nln(n+1) + nln(n) - nln(n+1) - n + O(ln(n+1))
Bom, agora, temos que mostrar que nln(n) - nln(n+1) \in O(ln(n+1)), e esta
fechada a demonstração.
Dei uma mexida mas ainda não saiu...
n(ln(n) - ln(n+1)) \in O(1) na verdade, já que ln'(n) = 1/n. Ou então
porque você sabe que ln(1 - eps) ~ eps, e daí fica ln( n/(n+1) ) = ln(
1 - 1/(n+1) ) ~ 1/(n+1)
Alguém ajuda?! hehehe :)
Eu atrapalho, serve ?
Deixa só eu fazer uma mudança na sua demo. Vou mostrar algo muito mais preciso:
ln(n!) = n*ln(n) + O(1)
Da mesma forma, façamos ln((n+1)!) = ln(n+1) + ln(n!) = ln(n+1) + n*ln(n) + O(1)
Somando e subtraindo n*ln(n+1), obtemos
ln((n+1)!) = (n+1)*ln(n+1) + n*ln(n) - n*ln(n+1) + O(1). Do que eu
acabei de dizer, n*[ ln(n) - ln(n+1) ] é aproximadamente -1, e
portanto está em O(1).
Bom, com *certeza* uma das demonstrações está errada (já que elas
demonstram resultados incompatíveis). Eu voto as duas... (mas a do
Marcelo dá pra corrigir, enquanto a minha, que prova algo falso, é
incorrigível). Mas a pergunta fica: onde estas demonstrações entraram
pelo cano???
abraços,
Salhab
abraços (e mesmo que eu fale bem de indução, é algo a se manipular com
mito cuidado)
2010/9/16 Guilherme Vieira rjguilhermevie...@hotmail.com
Prezado Paulo,
Creio que não há como fazer a demonstração através de indução. Na
internet, vi esse resultado. Não sei, contudo, se o desenvolvimento que o
justifica está correto. É muito complexo. Ver, por exemplo, o site abaixo.
http://en.wikipedia.org/wiki/Stirling's_approximation
O mais simples e natural (a meu ver) é obter ln(n!) ~ n*ln(n) - n +
ln(n) / 2 + O(1) por integração de 1 até n+1 do logaritmo:
integral de 1 a n+1 de log(x) dx é aproximadamente igual à soma dos
trapézios de coordenadas (i, 0), (i+1, 0), (i+1, ln(i+1)), (i,ln(i))
(faça um desenho !!!). A área dos trapézios é igual à ln(n!) + ln(n+1)
/ 2 (cada trapézio dá [ ln(i) + ln(i+1) ]/2, e daí você telescopa no
n!).
Resta estimar o erro, que é a soma das integrais de i a i+1 de log(x)
- {reta afim ligando (i,ln(i)) a (i+1, ln(i+1))}. Aqui, tem que fazer
mais contas... e ajuda fazer mudanças de variáveis nas integrais,
porque a equação da reta fica mais simples se a gente fizer a integral
de zero a 1. (pense assim: se 0 corresponde ao ponto i, temos ln(i),
no ponto 1 temos ln(i+1), isso dá direto o coeficiente diretor e o
coeficiente afim ; ao mesmo tempo, teremos agora ln(i+x) em vez de
ln(x)...)
erro(i) = integral de zero a 1 de ln(i+x) - [ ln(i) + [ln(i+1) - ln(i)]*x ] dx
= integral de ln(1 + x/i) - x*ln(1 + 1/i) dx
e aqui você vê que a diferença entre os dois termos é do tipo
phi(x)/i^2 (a derivada de ambas em 0 é a mesma, logo elas só podem
diferir em segunda ordem, que é o caso). Se você conhece equivalentes
(ou séries de Taylor) o primeiro é ~ x/i - x^2/2*i^2 + O(x^3/i^3) e o
segundo ~ x*[ 1/i -1/2*i^2 + O(1/i^3) ]. Como x está entre 0 e 1, ele
é limitado, e portanto a integral será algo do tipo Const/i^2 (mais
termos de ordem superior, claro). O legal é que a soma desses termos
(em i) é convergente, logo limitada, logo o erro é controlado por uma
constante que não depende de quantos termos de erro a gente somar.
Ufa, deu O(1). Ah, sim, tem que integrar ln(x) de 1 a n+1 também, mas
isso eu deixo para você fazer e ver que dá (n+1)*ln(n+1) - n, e usando
(de novo) que a diferença entre n*ln(n) e n*ln(n+1) é O(1) você
termina com:
Integral = Soma dos trapézios + resto
(n+1)*ln(n+1) - n = ln(n!) + ln(n+1) / 2 + O(1)
Logo
ln(n!) = n*ln(n+1) - n + ln(n+1)/2 + O(1) =
n*ln(n) - n + ln(n)/2 + O(1) + n[ln(n+1) - ln(n)] + [ln(n+1) - ln(n)]/2 =
n*ln(n) - n + ln(n)/2 + O(1) + O(1) + O(1/n) = n*ln(n) - n + ln(n)/2 + O(1)
Grande abraço,
Guilherme
Abraços,
--
Bernardo Freitas Paulo da Costa
=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=
Re: [obm-l] Fatorial $via Stirling$
Ah, eu fui guloso demais... a integral complicada na verdade é razoavelmente fácil de calcular... erro(i) = integral de zero a 1 de ln(i+x) - [ ln(i) + [ln(i+1) - ln(i)]*x ] dx = integral de ln(1 + x/i) - x*ln(1 + 1/i) dx A parte que tem o x em fator é realmente fácil: vale ln(1+1/i)/2 A parte com o x dentro do log é um pouquinho mais chata, mas a gente também calcula. E daí é só mostrar que dá O(1/i^2), o que é o caso. abraços, -- Bernardo Freitas Paulo da Costa = 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] CONCEITOS E CONTROVÉ RSIAS!
Olá, Pessoal! Vale lembrar que o símbolo do nada está entre as mais importantes descobertas feita pelo homem. É difícil acreditar que os homens levaram 5 mil anos entre escrever números e conceber o nosso sistema de numeração posicional, ponto crucial num desenvolvimento sem o qual o progresso da ciência moderna seria inconcebível. Hoje parece simples, mas a mentalidade concreta dos antigos gregos, não podia conceber o vazio, o nada, como um número. Apreciaremos ainda mais a grandeza dessa conquista se lembrarmo-nos de que ela escapou ao gênio de Arquimedes e Apolônio, dois dos maiores homens da antiguidade. Existem situações em Análise Combinatória onde há uma certa conveniência em adotar a regra 0^0=1, a fim de estender um pouco mais o campo de validez de algumas fórmulas. Nem por isso 0^0 deixa de ser uma expressão indeterminada. Um caso parecido acontece na Teoria da Medida e da Integral, onde às vezes é conveniente escrever 0*...=0, a fim de que a fórmula da área de um retângulo continue válida quando a base do retângulo é toda uma reta e a altura se reduz a um ponto. O curioso é que os defensores de 0^0=1 não reivindiquem o mesmo direito para 0/0. Algum colega saberia o motivo? Afinal! Qual das medidas é a mais precisa? E a mais exata? a)5,6m b)560m (com aproximação de 10m) c) 0,056m d)5600m (com aproximação de 100m) Quantos algarismos significativos temos nesta medida? X=(0,009050 + - 0,02) A propósito! Como se escreve zero em algarismos romanos? Abraços!
[obm-l] Re: [obm-l] CONCEITOS E CONTROVÉRSIAS!
...O curioso é que os defensores de 0^0=1 não reivindiquem o mesmo direito para 0/0. Algum colega saberia o motivo?... Acho que o motivo de associar 0^0 com 0/0 é errado, se fosse associar 0^0 com 0/0 isso também poderia ser feito com o 0, por causa do seguinte o pessoal argumenta pela regra de expoentes, supondo que fosse verdadeira para base 0 que 0^0 = 0^ (1 -1) = 0^1 /0^1 = 0/0 porém isso pode ser feito com o 0 também 0= 0^ (2-1) = 0^2/0^1 =0/0 então o 0 também seria 0/0 ? e seria então indefinido? o erro é usar isso com base 0, o que não pode ser feito . Quando se demonstra essa proprieda a^( b-c )= a^b/a^c , por exemplo, definindo potenciação pra expoente natural e base real e depois expoente inteiro, essa propriedade se demonstra, deixando fora o caso em que a=0 .
[obm-l] Fatorial via Stirling (confirmaç ão)
Caros amigos, Repito a questão a que propus. Não sei se as respostas já dadas tratam efetivamente da mesma questão. Fiquei em dúvida. Gostaria de obter uma demonstração (pode ser por indução finita) do fato abaixo, proveniente da fórmula de Stirling. Fato: Para todo número inteiro positivo n, existe um número real r, com 1/(12n+1) r 1/(12n), de modo que seja válida a igualdade: n! = [(2.n.pi)^(1/2)].[(n/e)^n].(e^r) Muito obrigado! Paulo Argolo
[obm-l] Ajuda!!!
De quantas maneiras você pode distribuir moedinhas a crianças, se supõe-se que cada criança ganhe pelo menos 5? Alguém poderia ajudar nesta questão! Desde já agradeço! Warley Souza
RE: [obm-l] Ajuda!!!
Warley, Calcule o numero total de maneiras e subtraia as possibilidades das criancas receberem 1,2,3, e 4 moedas. Acho que vai funcionar. Leandro Sent from my HTC Touch Pro2 on the Now Network from Sprint®. -Original Message- From: warley ferreira Sent: 9/17/2010 12:43:28 AM To: Lista de Discussão Subject: [obm-l] Ajuda!!! De quantas maneiras você pode distribuir [http://forum.obmep.org.br/latexrender/pictures/7b8b965ad4bca0e41ab51de7b31363a1.gif] moedinhas a [http://forum.obmep.org.br/latexrender/pictures/8ce4b16b22b58894aa86c421e8759df3.gif] crianças, se supõe-se que cada criança ganhe pelo menos 5? Alguém poderia ajudar nesta questão! Desde já agradeço! Warley Souza
