Re: [obm-l] Combinatoria com Matrizes

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

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" <claudio.buffara@terra.com.br>
To: "Lista OBM" <obm-l@mat.puc-rio.br>
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
=========================================================================