Re: [obm-l] boa de combinatoria

["Ralph Teixeira" <ralphct@xxxxxxxxx>]

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 <eestradaitu@xxxxxxxxxxxx> 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 <vitoriogauss@xxxxxxxxxx>
Para: obm-l <obm-l@xxxxxxxxxxxxxx>
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!