[obm-l] Contando caminhos em reticulados

["Domingos Jr." <dopikas@xxxxxxxxxx>]

Ol�!

Eu proponho o seguinte problema combinat�rio que me parece bem dif�cil:
Seja k > 1 e seja R um reticulado retangular m x n (linhas x colunas). 
Vamos considerar caminhos de (0, 0) a (n, m) em R.
Se P e Q s�o caminhos de (0, 0) a (n, m) em R, podemos dizer que P <= Q 
sse para todo j, 0 <= j <= m, temos max{i : (i, j) est� em P} <= max{k : 
(k, j) est� em Q}.
Tra�ando um gr�fico com caminhos P <= Q, vemos que os tra�os de P nunca 
invadem a �rea delimitada por Q (por baixo).
De quantas maneiras podemos tra�ar k caminhos, P_1 <=  ... <= P_k, em R?

Este � um problema que apareceu quando eu tentei resolver uma quest�o 
proposta pelo Cl�udio ou pelo Nicolau (n�o sei direito!) onde 
perguntava-se quantas maneiras podemos preencher uma matriz A, m x n, 
com elementos de {1, ..., p} tal que A(i, j) > A(i + 1, j) e A(i, j) > 
A(i, j + 1) para todo (i, j). � simples mostrar uma bije��o com um 
problema similar, onde trocamos '>' por '>=' e o conjunto de valores 
para as entradas da matriz � menor. Quando olhamos para este segundo 
problema, podemos pensar na matriz como um reticulado m x n e as 
fronteiras que agrupam n�meros iguais seriam caminhos de (0, 0) a (n, 
m). Se contarmos o n�mero de caminhos poss�veis, teremos determinado 
todas as matrizes satisfazendo o segundo problema e, pela bije��o 
montada, teremos resolvido o problema original.

Talvez a id�ia n�o seja o melhor caminho para chegar na resposta. De 
qualquer forma, o problema que eu propus parece ser interessante por si 
s�. Eu lembro que o Nicolau havia comentado algo sobre o paper dele em 
Matem�tica Qu�ntica. Bem, eu li o primeiro cap�tulo (por cima) mas ainda 
n�o tive id�ias para resolver o problema. Socorro, Nicolau! ;-)

[ ]'s e boa sorte pra quem tentar o desafio.
=========================================================================
Instru��es para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================