[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
=========================================================================