Ok, Ralph,
Respondi dizendo que atentei para minha distração logo que enviei a resposta
anterior. Mas não conhecia essa solução que você apresentou. De fato, muito
interessante.
Um abraço,
Eduardo
----- Mensagem original ----
De: Ralph Teixeira <[EMAIL PROTECTED]>
Para: obm-l@mat.puc-rio.br
Enviadas: Sexta-feira, 7 de Dezembro de 2007 17:01:06
Assunto: Re: [obm-l] boa de combinatoria
Hmmm... infelizmente, uma função "não-decrescente" não é o mesmo que "uma
função que não é decrescente" -- é, eu concordo que é uma péssima péssima
péssima denominação, mas foi assim que os matemáticos convencionaram...
Uma função decrescente é uma que satisfaz f(x)>f(y) sempre que x<y.
Uma função não-decrescente é uma que satisfaz f(x)<=f(y) sempre que x<y.
Por exemplo, se f(1)=3, f(2)=1 e f(3)=2 então a função não é decrescente (pois
cresce de f(2) para f(3)) nem "não-decrescente" (pois decresce de f(1)=3 para
f(2)=1). Denominação horrível, né?
Solução de (b): imagine bolinhas numeradas de 1 a m. Vamos colocar, entre as
bolinhas, barras indicando onde está cada um dos valores f(1), f(2), ..., f(n).
Por exemplo, se for n=3 e m=9 e escolhermos a função f(1)=2, f(2)=5 e f(3)=5,
temos o seguinte diagrama:
oo|ooo||oooo
A primeira barra diz que f(1)=2 (bolinhas à esquerda dela); a segunda indica
f(2)=5; a terceira indica f(3)=5 também.
Afirmamos que definir uma função não-decrescente é equivalente a escrever uma
sucessão de bolinhas e barras como acima -- dada uma função existe uma única
maneira de escrevê-la com bolas e barras, e dada uma seqüência de n+m bolas e
barras com m bolas e n barras existe uma única função. Bom, para ser exato não
vale começar com uma barra (pois não vale f(1)=0), mas fora isso vale tudo.
Vale até terminar com uma barra (seria f(n)=m) ou várias (f(n)=f(n-1)=...=m).
Uma função constante, por exemplo, teria todas as barras juntas entre duas
bolinhas.
Então a pergunta é: quantas seqüências de (m-1) bolas e n barras existem
(descartei a primeira bola que não pode ser mexida)? Ora, são m+n-1 posições,
das quais tenho de escolher n posições para colocar n barras (os outros lugares
terão de conter as bolas), então a resposta é C(m+n-1,n).
Abraço,
Ralph
P.S.: não é coinciência que este raciocínio se parece com a contagem do número
de soluções inteiras não-negativas de x1+x2+...+xn+x(n+1)=m -- basta
identificar x1=f(1), x(i)=f(i)-f(i-1) para i=2,3,...,n e finalmente
x(n+1)=m-f(n). Cada solução (x1,x2,...,x(n+1)) corresponde a uma única f, e
vice-versa.
On Dec 7, 2007 9:53 AM, Eduardo Estrada <[EMAIL PROTECTED]> wrote:
Olá, Vitório,
Me parece que a resolução é a seguinte:
a) Funções crescentes;
Basta que, do contradomínio com m elementos, selecionem-se n. A cada seleção,
associa-se uma única função crescente, e vice-versa. Asim, a resposta é Cm,n.
Observe que, quando m<n, o valor obtido é zero, o que é perfeitamente coerente.
b) Funções não decrescentes;
Analogamente, o total de funções decrescentes é Cm,n (de fato, observe que, a
cada função crescente, associa-se uma única função decrescente, e vice-versa).
Como o total de funções (de qualquer tipo) é m^n, temos que o valor procurado é
m^n - Cm,n.
Espero ter ajudado, um abraço!
Eduardo L. Estrada
----- Mensagem original ----
De: vitoriogauss <[EMAIL PROTECTED]>
Para: obm-l <obm-l@mat.puc-rio.br>
Enviadas: Quinta-feira, 6 de Dezembro de 2007 17:01:58
Assunto: [obm-l] boa de combinatoria
Caros colegas...
Seja In = {1,2,...,n}, analogamente Im, determinar o número de funções f: In
--> Im tais que:
a) f seja crescente
b) f seja não-decrescente
desde já grato....
Abra sua conta no Yahoo! Mail, o único sem limite de espaço para armazenamento!
Abra sua conta no Yahoo! Mail, o único sem limite de espaço para
armazenamento!
http://br.mail.yahoo.com/
