Como você pediu *qualquer* ajuda:
defina f(n, p, d) como o número de matrizes A, 2 x n, com elementos de
{1,..,p} e respeitando (ii) com A(2,1) = d.
A seguinte recorrência apareceu:
f(n+1, p, d) = f(n+1, p-1, d) + soma{k=1..d-1} f(n, p-1, k)
a idéia é:
Se A(1,1) != p, então a matriz A tem elementos em {1,..,p-1}, logo
contamos f(n+1, p-1, d).
Se A(1,1) = p então a primeira coluna é [p, d] e as n colunas da direita de
A formam uma matriz A' contida em {1,..,p-1} respeitando (ii) e com A'(2,1)
< d, logo soma{k=1..d-1} f(n, p-1, k).
considerando a recorrência temos:
f(n+1, p-1, d) = f(n+1, p-2, d) + soma{k=1..d-1} f(n, p-2, k)
e portanto:
f(n+1, p, d) = f(n+1, p-2, d) + soma{k=1..d-1} [f(n, p-2, k) + f(n, p-1,
k)]
continuando...
f(n+1, p, d) = soma{j=1..p-1} [ soma{k=1..d-1} f(n, j, k) ]
base:
f(n, p, d) = 0 se p <= n
f(n, n+1, n) = 1
f(n, n+1, d) = 0, se d != n
f(1, p, d) = 1 se d < p
f(1, p, d) = 0 se d >= p
é simples ver que o valor desejado é
g(n, p) = soma{d=1..p-1} f(n, p, d)
Talvez seja possível entrar recorrências mais simples para esse problema,
amanhã a gente conversa!
[ ]'s
----- Original Message -----
From: "Claudio Buffara" <[EMAIL PROTECTED]>
To: "Lista OBM" <[EMAIL PROTECTED]>
Sent: Tuesday, November 25, 2003 10:33 PM
Subject: [obm-l] Combinatoria com Matrizes
| Oi, pessoal:
|
| Estou enrolado com esse aqui:
|
| Quantas matrizes A(2 x n) existem satisfazendo a:
| i) Cada A(i,j) pertence a {1,2,...,p} (p: inteiro positivo)
| ii) A(i,j) > A(i+1,j) e A(i,j) > A(i,j+1) (ou seja, cada elemento da
| matriz eh maior do que o elemento imediatamente abaixo e do que o elemento
| imediatamente a direita.
|
| Esse eh um caso particular de um problema proposto ha algum tempo pelo
| Nicolau - ele falava de uma matriz m x n.
|
| Qualquer ajuda serah bem vinda.
|
| Um abraco,
| Claudio.
=========================================================================
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
=========================================================================
