|
a restrição é só para x e y?
bom, faça assim para cada possível valor de z + w,
obtenha o número de pares x, y com x > y que satisfazem
x + y = 20 - (z + w),
assim, por exemplo para z + w = 0,
temos
x + y = 20, e isso tem como sol. 20 + 0, 19 + 1,
..., 11+9, ou seja 10 soluções (e z + w = 0 só tem uma)
para z + w = 1, temos 2 soluções em z, w e
x + y = 19 tem sol. 19 + 0, 18 + 1, ..., 10 + 9 (10
soluções em x, y * 2 sol. em z, w dá 20 soluções)
continue a soma (mecanizando o processo,
claro!).
se A = {1} e B={1,2,..., n}
existem n funções não decrescentes
f:A->B
suponha que g(m, n) conte quantas funções
existem com f:[m] -> [n] (onde [x] = {1, 2, ..., x})
então g(1, n) = n e g(m, 1)
= 1
vamos tentar obter então uma
recorrência
suponha f uma função não decrescente em
f:[m+1] -> [n]
f| é a função f definida apenas em [m], ela também
é não decrescente, se soubermos qual o valor de f(m) fica fácil saber quantas
funções possíveis podemos ter que sejam não decrescentes.
proposição:
g(m+1, n) = soma[i=1..n] { g(m,
i) }
a idéia é, precisamos contar todas as funções em
que f(m)=k e multiplicar por n-k+1, para k = 1..n
então vemos que g(m, 1) conta todas as funções
com f(m) = 1 uma vez
g(m, 2) conta novamente todas as funções com f(m) =
1 + uma vez
...
g(m, n) conta " " " + uma vez
ou seja somando todas estaremos contando as funções
com f(m) = 1 exatamente n vezes
o mesmo argumento se repete para um i
qualquer
g(m, i) conta todas as funções com f(m) = i uma
vez
g(m, i + 1), conta + uma vez
...
g(m, n) conta + uma vez,
onde as funções com f(m) = i são contadas
exatamente n-i+1 vezes.
[ ]'s
|