Re: [obm-l] Combinatória

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

>   2) Distribuindo aletoriamente os sinais "+' ou "-" a frente dos
> números 1, 2, 3, ..., 2007, quantas configurações há tal que o resultado
> final seja 0(zero).

Acho muito improvável que haja uma expressão simples para a resposta
deste problema.
Veja um pouco sobre a generalização deste problema (trocando 2007 por n) aqui:

http://www.research.att.com/~njas/sequences/A058377

Outra expressão para a probabilidade 2^(-n)*a[n] é

(1/(2*pi)) integral_0^(2 pi) cos(t) cos(2t) cos(3t) ... cos(nt) dt

Para ver isso, escreva cos(kt) = (z^k + z^(-k))/2 onde z = exp(it).
A probabilidade (ou número de combinações dividido por 2^n) é,
conforme o Paulo Santa Rita explicou, o coeficiente independente
que é obtido integrando e dividindo por 2 pi.

Esta expressão permite estimar a probabilidade pois longe de 0 e pi
o produto fica muito próximo de 0.
Para t perto de 0, fazendo
cos t ~= 1 - t^2/2 ~=  exp(-t^2/2) e portanto cos(kt) ~= exp(-k^2 t^2/2)
temos
cos(t) cos(2t) cos(3t) ... cos(nt) ~= exp(-(1^2 + .. + n^2)t^2/2) ~=
exp(-(n^3/3) t^2/2)
Ora, sabemos que integral exp(-a t^2/2) = sqrt(2 pi/a) donde a parte da integral
perto de 0 é aproximadamente sqrt(6 pi/n^3).
Se n(n+1)/2 for ímpar a integral perto de pi cancela com esta para dar 0
mas se n(n+1) for par a integral perto de pi dá igual donde a probabilidade
dá aproximadamente sqrt(24 pi/n^3)/2 pi = sqrt(6/(pi*n^3)).

Para n=63 usei o maple para calcular a probabilidade exata e para a
fórmula acima.
As resopstas foram 0.002711775516 (primeiro calculando a probabilidade exata
e depois fazendo o quocente aproximado) e 0.002763693420 (pela fórmula).
Para n = 83 obtive 0.001801463390 e 0.001827610102, respectivamente.
Para n = 2007 o maple não conseguiria fazer a conta exata (pelo menos
não da forma
como eu programei) mas a fórmula dá 0.00001537020394;
deve estar bem perto da resposta certa.

N.

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=========================================================================