[SPAM] Res: [obm-l] boa de combinatoria

[Eduardo Estrada <eestradaitu@xxxxxxxxxxxx>]

SPAM: -------------------- Start SpamAssassin results ----------------------
SPAM: This mail is probably spam.  The original message has been altered
SPAM: so you can recognise or block similar unwanted mail in future.
SPAM: See http://spamassassin.org/tag/ for more details.
SPAM: 
SPAM: Content analysis details:   (7.90 hits, 5 required)
SPAM: X_MAILING_LIST     (-0.3 points) Found a X-Mailing-List header
SPAM: EMAIL_ATTRIBUTION  (-1.6 points) BODY: Contains what looks like an email attribution
SPAM: SPAM_PHRASE_00_01  (0.8 points)  BODY: Spam phrases score is 00 to 01 (low)
SPAM:                    [score: 0]
SPAM: MAILTO_LINK        (0.2 points)  BODY: Includes a URL link to send an email
SPAM: SUPERLONG_LINE     (0.0 points)  BODY: Contains a line >=199 characters long
SPAM: MIME_EXCESSIVE_QP  (1.0 points)  RAW: Excessive quoted-printable encoding in body
SPAM: SPAM_REDIRECTOR    (0.4 points)  URI: Uses open redirection service
SPAM: FORGED_YAHOO_RCVD  (1.4 points)  'From' yahoo.com does not match 'Received' headers
SPAM: RCVD_IN_ORBS       (2.2 points)  RBL: Received via a relay in orbs.dorkslayers.com
SPAM:                    [RBL check: found 212.201.142.68.orbs.dorkslayers.com., type: 68.178.232.99]
SPAM: RCVD_IN_OSIRUSOFT_COM (0.4 points)  RBL: Received via a relay in relays.osirusoft.com
SPAM:                    [RBL check: found 212.201.142.68.relays.osirusoft.com.]
SPAM: X_OSIRU_OPEN_RELAY (2.7 points)  RBL: DNSBL: sender is Confirmed Open Relay
SPAM: AWL                (0.7 points)  AWL: Auto-whitelist adjustment
SPAM: 
SPAM: -------------------- End of SpamAssassin results ---------------------

--0-2049830293-1197138494=:31124
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable

Ok, Ralph,=0A=0ARespondi dizendo que atentei para minha distra=C3=A7=C3=A3o=
 logo que enviei a resposta anterior. Mas n=C3=A3o conhecia essa solu=C3=A7=
=C3=A3o que voc=C3=AA apresentou. De fato, muito interessante.=0A=0AUm abra=
=C3=A7o,=0AEduardo=0A=0A----- Mensagem original ----=0ADe: Ralph Teixeira <=
ralphct@xxxxxxxxx>=0APara: obm-l@xxxxxxxxxxxxxx=0AEnviadas: Sexta-feira, 7 =
de Dezembro de 2007 17:01:06=0AAssunto: Re: [obm-l] boa de combinatoria=0A=
=0AHmmm... infelizmente, uma fun=C3=A7=C3=A3o "n=C3=A3o-decrescente" n=C3=
=A3o =C3=A9 o mesmo que "uma fun=C3=A7=C3=A3o que n=C3=A3o =C3=A9 decrescen=
te" -- =C3=A9, eu concordo que =C3=A9 uma p=C3=A9ssima p=C3=A9ssima p=C3=A9=
ssima denomina=C3=A7=C3=A3o, mas foi assim que os matem=C3=A1ticos convenci=
onaram... =0A=0A=0A =0A=0AUma fun=C3=A7=C3=A3o decrescente =C3=A9 uma que s=
atisfaz f(x)>f(y) sempre que x<y.=0A=0AUma fun=C3=A7=C3=A3o n=C3=A3o-decres=
cente =C3=A9 uma que satisfaz f(x)<=3Df(y) sempre que x<y.=0A=0A =0A=0APor =
exemplo, se f(1)=3D3, f(2)=3D1 e f(3)=3D2 ent=C3=A3o a fun=C3=A7=C3=A3o n=
=C3=A3o =C3=A9 decrescente (pois cresce de f(2) para f(3)) nem "n=C3=A3o-de=
crescente" (pois decresce de f(1)=3D3 para f(2)=3D1). Denomina=C3=A7=C3=A3o=
 horr=C3=ADvel, n=C3=A9?=0A=0A =0A=0ASolu=C3=A7=C3=A3o de (b): imagine boli=
nhas numeradas de 1 a m. Vamos colocar, entre as bolinhas, barras indicando=
 onde est=C3=A1 cada um dos valores f(1), f(2), ..., f(n). Por exemplo, se =
for n=3D3 e m=3D9 e escolhermos a fun=C3=A7=C3=A3o f(1)=3D2, f(2)=3D5 e f(3=
)=3D5, temos o seguinte diagrama:=0A=0A=0A =0A=0Aoo|ooo||oooo=0A=0A =0A=0AA=
 primeira barra diz que f(1)=3D2 (bolinhas =C3=A0 esquerda dela); a segunda=
 indica f(2)=3D5; a terceira indica f(3)=3D5 tamb=C3=A9m.=0A=0A =0A=0AAfirm=
amos que definir uma fun=C3=A7=C3=A3o n=C3=A3o-decrescente =C3=A9 equivalen=
te a escrever uma sucess=C3=A3o de bolinhas e barras como acima -- dada uma=
 fun=C3=A7=C3=A3o existe uma =C3=BAnica maneira de escrev=C3=AA-la com bola=
s e barras, e dada uma seq=C3=BC=C3=AAncia de n+m bolas e barras com m bola=
s e n barras existe uma =C3=BAnica fun=C3=A7=C3=A3o. Bom, para ser exato n=
=C3=A3o vale come=C3=A7ar com uma barra (pois n=C3=A3o vale f(1)=3D0), mas =
fora isso vale tudo. Vale at=C3=A9 terminar com uma barra (seria f(n)=3Dm) =
ou v=C3=A1rias (f(n)=3Df(n-1)=3D...=3Dm). Uma fun=C3=A7=C3=A3o constante, p=
or exemplo, teria todas as barras juntas entre duas bolinhas.=0A=0A=0A =0A=
=0AEnt=C3=A3o a pergunta =C3=A9: quantas seq=C3=BC=C3=AAncias de (m-1) bola=
s e n barras existem (descartei a primeira bola que n=C3=A3o pode ser mexid=
a)? Ora, s=C3=A3o m+n-1 posi=C3=A7=C3=B5es, das quais tenho de escolher n p=
osi=C3=A7=C3=B5es para colocar n barras (os outros lugares ter=C3=A3o de co=
nter as bolas), ent=C3=A3o a resposta =C3=A9 C(m+n-1,n).=0A=0A=0A =0A=0AAbr=
a=C3=A7o,=0A=0A       Ralph=0A=0A =0A=0AP.S.: n=C3=A3o =C3=A9 coinci=C3=AAn=
cia que este racioc=C3=ADnio se parece com a contagem do n=C3=BAmero de sol=
u=C3=A7=C3=B5es inteiras n=C3=A3o-negativas de x1+x2+...+xn+x(n+1)=3Dm -- b=
asta identificar x1=3Df(1), x(i)=3Df(i)-f(i-1) para i=3D2,3,...,n e finalme=
nte x(n+1)=3Dm-f(n). Cada solu=C3=A7=C3=A3o (x1,x2,...,x(n+1)) corresponde =
a uma =C3=BAnica f, e vice-versa.=0A=0A=0A =0A=0AOn Dec 7, 2007 9:53 AM, Ed=
uardo Estrada <eestradaitu@xxxxxxxxxxxx> wrote:=0A=0A=0A=0A=0AOl=C3=A1, Vit=
=C3=B3rio,=0A=0AMe parece que a resolu=C3=A7=C3=A3o =C3=A9 a seguinte:=0A=
=0Aa) Fun=C3=A7=C3=B5es crescentes;=0A=0ABasta que, do contradom=C3=ADnio c=
om m elementos, selecionem-se n. A cada sele=C3=A7=C3=A3o, associa-se uma =
=C3=BAnica fun=C3=A7=C3=A3o crescente, e vice-versa. Asim, a resposta =C3=
=A9 Cm,n. Observe que, quando m<n, o valor obtido =C3=A9 zero, o que =C3=A9=
 perfeitamente coerente.=0A=0A=0Ab) Fun=C3=A7=C3=B5es n=C3=A3o decrescentes=
;=0A=0AAnalogamente, o total de fun=C3=A7=C3=B5es decrescentes =C3=A9 Cm,n =
(de fato, observe que, a cada fun=C3=A7=C3=A3o crescente, associa-se uma =
=C3=BAnica fun=C3=A7=C3=A3o decrescente, e vice-versa). Como o total de fun=
=C3=A7=C3=B5es (de qualquer tipo) =C3=A9 m^n, temos que o valor procurado =
=C3=A9 m^n - Cm,n.=0A=0A=0AEspero ter ajudado, um abra=C3=A7o!=0AEduardo L.=
 Estrada=0A=0A=0A----- Mensagem original ----=0ADe: vitoriogauss <vitorioga=
uss@xxxxxxxxxx>=0A=0APara: obm-l <obm-l@xxxxxxxxxxxxxx>=0AEnviadas: Quinta-=
feira, 6 de Dezembro de 2007 17:01:58=0AAssunto: [obm-l] boa de combinatori=
a=0A=0A=0ACaros colegas...=0A=0A =0A=0A =0A=0ASeja In =3D {1,2,...,n}, anal=
ogamente Im, determinar o n=C3=BAmero de fun=C3=A7=C3=B5es f: In --> Im tai=
s que:=0A=0A =0A=0A =0A=0Aa) f seja crescente=0A=0A =0A=0Ab) f seja n=C3=A3=
o-decrescente=0A=0A =0A=0Adesde j=C3=A1 grato....=0A=0A=0A=0A=0A=0A=0A=0A=
=0A=0A=0A=0A=0AAbra sua conta no Yahoo! Mail, o =C3=BAnico sem limite de es=
pa=C3=A7o para armazenamento! =0A=0A=0A=0A=0A=0A=0A=0A=0A=0A=0A      Abra s=
ua conta no Yahoo! Mail, o =C3=BAnico sem limite de espa=C3=A7o para armaze=
namento!=0Ahttp://br.mail.yahoo.com/
--0-2049830293-1197138494=:31124
Content-Type: text/html; charset=utf-8
Content-Transfer-Encoding: quoted-printable

<html><head><style type=3D"text/css"><!-- DIV {margin:0px;} --></style></he=
ad><body><div style=3D"font-family:times new roman,new york,times,serif;fon=
t-size:12pt"><div style=3D"font-family: times new roman,new york,times,seri=
f; font-size: 12pt;">Ok, Ralph,<br><br>Respondi dizendo que atentei para mi=
nha distra=C3=A7=C3=A3o logo que enviei a resposta anterior. Mas n=C3=A3o c=
onhecia essa solu=C3=A7=C3=A3o que voc=C3=AA apresentou. De fato, muito int=
eressante.<br><br>Um abra=C3=A7o,<br>Eduardo<br><br><div style=3D"font-fami=
ly: times new roman,new york,times,serif; font-size: 12pt;">----- Mensagem =
original ----<br>De: Ralph Teixeira &lt;ralphct@xxxxxxxxx&gt;<br>Para: obm-=
l@xxxxxxxxxxxxxx<br>Enviadas: Sexta-feira, 7 de Dezembro de 2007 17:01:06<b=
r>Assunto: Re: [obm-l] boa de combinatoria<br><br><div>Hmmm... infelizmente=
, uma fun=C3=A7=C3=A3o "n=C3=A3o-decrescente" n=C3=A3o =C3=A9&nbsp;o mesmo =
que "uma fun=C3=A7=C3=A3o que n=C3=A3o =C3=A9 decrescente" -- =C3=A9, eu co=
ncordo que =C3=A9 uma p=C3=A9ssima p=C3=A9ssima p=C3=A9ssima denomina=C3=A7=
=C3=A3o, mas foi
 assim que os matem=C3=A1ticos convencionaram... =0A</div>=0A<div>&nbsp;</d=
iv>=0A<div>Uma fun=C3=A7=C3=A3o decrescente =C3=A9 uma que satisfaz f(x)&gt=
;f(y) sempre que x&lt;y.</div>=0A<div>Uma fun=C3=A7=C3=A3o n=C3=A3o-decresc=
ente =C3=A9 uma que satisfaz f(x)&lt;=3Df(y) sempre que x&lt;y.</div>=0A<di=
v>&nbsp;</div>=0A<div>Por exemplo, se f(1)=3D3, f(2)=3D1 e f(3)=3D2 ent=C3=
=A3o a fun=C3=A7=C3=A3o n=C3=A3o =C3=A9 decrescente (pois cresce de f(2) pa=
ra f(3))&nbsp;nem "n=C3=A3o-decrescente"&nbsp;(pois decresce de f(1)=3D3 pa=
ra f(2)=3D1). Denomina=C3=A7=C3=A3o horr=C3=ADvel, n=C3=A9?</div>=0A<div>&n=
bsp;</div>=0A<div>Solu=C3=A7=C3=A3o de (b): imagine bolinhas numeradas de 1=
 a m. Vamos colocar, entre as bolinhas, barras indicando onde est=C3=A1 cad=
a um dos valores f(1), f(2), ..., f(n). Por exemplo, se for n=3D3 e m=3D9 e=
 escolhermos a fun=C3=A7=C3=A3o f(1)=3D2, f(2)=3D5 e f(3)=3D5, temos o segu=
inte diagrama:=0A</div>=0A<div>&nbsp;</div>=0A<div>oo|ooo||oooo</div>=0A<di=
v>&nbsp;</div>=0A<div>A primeira barra diz que f(1)=3D2 (bolinhas =C3=A0 es=
querda dela); a segunda indica f(2)=3D5; a terceira indica f(3)=3D5 tamb=C3=
=A9m.</div>=0A<div>&nbsp;</div>=0A<div>Afirmamos que definir uma fun=C3=A7=
=C3=A3o n=C3=A3o-decrescente =C3=A9 equivalente a escrever uma sucess=C3=A3=
o de bolinhas e barras como acima -- dada uma fun=C3=A7=C3=A3o existe uma =
=C3=BAnica maneira de escrev=C3=AA-la com bolas e barras, e dada uma seq=C3=
=BC=C3=AAncia de n+m bolas e barras com m bolas e n barras existe uma =C3=
=BAnica&nbsp;fun=C3=A7=C3=A3o. Bom, para ser exato n=C3=A3o vale come=C3=A7=
ar com uma barra (pois n=C3=A3o vale f(1)=3D0), mas fora isso vale tudo.&nb=
sp;Vale at=C3=A9 terminar com uma barra (seria f(n)=3Dm) ou v=C3=A1rias (f(=
n)=3Df(n-1)=3D...=3Dm). Uma fun=C3=A7=C3=A3o constante, por exemplo, teria =
todas as barras juntas entre duas bolinhas.=0A</div>=0A<div>&nbsp;</div>=0A=
<div>Ent=C3=A3o a pergunta =C3=A9: quantas seq=C3=BC=C3=AAncias de (m-1) bo=
las e n barras existem (descartei&nbsp;a primeira bola que n=C3=A3o pode se=
r mexida)? Ora, s=C3=A3o m+n-1 posi=C3=A7=C3=B5es, das quais tenho de escol=
her n posi=C3=A7=C3=B5es&nbsp;para colocar n barras (os outros lugares ter=
=C3=A3o de conter as bolas), ent=C3=A3o a resposta =C3=A9 C(m+n-1,n).=0A</d=
iv>=0A<div>&nbsp;</div>=0A<div>Abra=C3=A7o,</div>=0A<div>&nbsp;&nbsp;&nbsp;=
&nbsp;&nbsp;&nbsp; Ralph</div>=0A<div>&nbsp;</div>=0A<div>P.S.: n=C3=A3o =
=C3=A9 coinci=C3=AAncia que este racioc=C3=ADnio se&nbsp;parece com a conta=
gem do n=C3=BAmero de solu=C3=A7=C3=B5es inteiras n=C3=A3o-negativas de&nbs=
p;x1+x2+...+xn+x(n+1)=3Dm -- basta identificar x1=3Df(1), x(i)=3Df(i)-f(i-1=
) para i=3D2,3,...,n e finalmente x(n+1)=3Dm-f(n). Cada solu=C3=A7=C3=A3o (=
x1,x2,...,x(n+1)) corresponde a uma =C3=BAnica f, e vice-versa.=0A</div>=0A=
<div>&nbsp;</div>=0A<div class=3D"gmail_quote">On Dec 7, 2007 9:53 AM, Edua=
rdo Estrada &lt;<a rel=3D"nofollow" ymailto=3D"mailto:eestradaitu@xxxxxxxxx=
.br" target=3D"_blank" href=3D"mailto:eestradaitu@xxxxxxxxxxxx";>eestradaitu=
@yahoo.com.br</a>&gt; wrote:<br>=0A<blockquote class=3D"gmail_quote" style=
=3D"border-left: 1px solid rgb(204, 204, 204); margin: 0px 0px 0px 0.8ex; p=
adding-left: 1ex;">=0A<div>=0A<div style=3D"font-size: 12pt; font-family: t=
imes new roman,new york,times,serif;">=0A<div style=3D"font-size: 12pt; fon=
t-family: times new roman,new york,times,serif;">Ol=C3=A1, Vit=C3=B3rio,<br=
><br>Me parece que a resolu=C3=A7=C3=A3o =C3=A9 a seguinte:<br><br>a) Fun=
=C3=A7=C3=B5es crescentes;<br><br>Basta que, do contradom=C3=ADnio com m el=
ementos, selecionem-se n. A cada sele=C3=A7=C3=A3o, associa-se uma =C3=BAni=
ca fun=C3=A7=C3=A3o crescente, e vice-versa. Asim, a resposta =C3=A9 Cm,n. =
Observe que, quando m&lt;n, o valor obtido =C3=A9 zero, o que =C3=A9 perfei=
tamente coerente.=0A<br><br>b) Fun=C3=A7=C3=B5es n=C3=A3o decrescentes;<br>=
<br>Analogamente, o total de fun=C3=A7=C3=B5es <span style=3D"font-style: i=
talic;">decrescentes</span> =C3=A9 Cm,n (de fato, observe que, a cada fun=
=C3=A7=C3=A3o crescente, associa-se uma =C3=BAnica fun=C3=A7=C3=A3o decresc=
ente, e vice-versa). Como o total de fun=C3=A7=C3=B5es (de qualquer tipo) =
=C3=A9 m^n, temos que o valor procurado =C3=A9 m^n - Cm,n.=0A<br><br>Espero=
 ter ajudado, um abra=C3=A7o!<br>Eduardo L. Estrada<br><br>=0A<div style=3D=
"font-size: 12pt; font-family: times new roman,new york,times,serif;">-----=
 Mensagem original ----<br>De: vitoriogauss &lt;<a rel=3D"nofollow" ymailto=
=3D"mailto:vitoriogauss@xxxxxxxxxx"; target=3D"_blank" href=3D"mailto:vitori=
ogauss@xxxxxxxxxx">vitoriogauss@xxxxxxxxxx</a>&gt;=0A<br>Para: obm-l &lt;<a=
 rel=3D"nofollow" ymailto=3D"mailto:obm-l@xxxxxxxxxxxxxx"; target=3D"_blank"=
 href=3D"mailto:obm-l@xxxxxxxxxxxxxx";>obm-l@xxxxxxxxxxxxxx</a>&gt;<br>Envia=
das: Quinta-feira, 6 de Dezembro de 2007 17:01:58<br>Assunto: [obm-l] boa d=
e combinatoria<br><br>=0A<div>Caros colegas...</div>=0A<div>&nbsp;</div>=0A=
<div>&nbsp;</div>=0A<div>Seja In =3D {1,2,...,n}, analogamente Im, determin=
ar o n=C3=BAmero de fun=C3=A7=C3=B5es f: In --&gt; Im tais que:</div>=0A<di=
v>&nbsp;</div>=0A<div>&nbsp;</div>=0A<div>a) f seja crescente</div>=0A<div>=
&nbsp;</div>=0A<div>b) f seja n=C3=A3o-decrescente</div>=0A<div>&nbsp;</div=
>=0A<div>desde j=C3=A1 grato....</div>=0A<div class=3D"WgoR0d"></div></div>=
=0A<div class=3D"WgoR0d"><br></div></div></div>=0A<div class=3D"WgoR0d"><br=
>=0A<hr size=3D"1">=0AAbra sua conta no <a rel=3D"nofollow" target=3D"_blan=
k" href=3D"http://br.rd.yahoo.com/mail/taglines/mail/*http://br.mail.yahoo.=
com/">Yahoo! Mail</a>, o =C3=BAnico sem limite de espa=C3=A7o para armazena=
mento! </div></div></blockquote></div><br>=0A</div><br></div></div><br>=0A=
=0A=0A      <hr size=3D1>Abra sua conta no <a href=3D"http://br.rd.yahoo.co=
m/mail/taglines/mail/*http://br.mail.yahoo.com/";>Yahoo! Mail</a>, o =C3=BAn=
ico sem limite de espa=C3=A7o para armazenamento! =0A</body></html>
--0-2049830293-1197138494=:31124--
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=========================================================================