|
|
Post by Alexandre Frias on Jan 5, 2015 22:40:52 GMT -3
Seja $I_n =\{i\in\mathbb{Z}|1\leq i\leq n\}$. Qual a cardinalidade da coleção $C=\{X\subset I_n | \sum_{x\in X}x\leq n\}$ ?
Exemplo:
$$I_5=\{1,2,3,4,5\}
$$
$$\{1\},\{2\},\{3\},\{4\},\{5\},\{1,2\},\{1,3\},\{1,4\},\{2,3\}
$$
o tamanho da coleção é 9.
|
|
|
|
Post by Alexandre Cezar on Jan 7, 2015 12:22:21 GMT -3
Já devo ter visto esse problema umas duas vezes. Não lembro se vi resposta, mas sempre achei interessante. Sabes a resposta?
|
|
|
|
Post by Alexandre Frias on Jan 7, 2015 17:16:11 GMT -3
Tenho a solução do André Vitor numa recorrência.
Considere a coleção $C_{i,j}=\{X\subset I_i|\sum_{x\in X}x=j\}$. O tamanho dessa coleção é dado pela recorrência
$$|C_{i,j}|=|C_{i-1,j}|+|C_{i-1,j-i}|$$
e a solução final do problema é dada por
$$\sum_{k=1}^{n} |C_{n,k}|$$
|
|
|
|
Post by Alexandre Frias on Jan 7, 2015 18:48:30 GMT -3
O jeito que pensei foi expandir $$ \prod_{k=1}^{n}(1+x^k)$$ e somar os coeficientes onde $x$ tem grau menor ou igual a $n$
$$\sum_{i=1}^{n}[x^i]\left(\prod_{k=1}^{n}(1+x^k)\right)$$, mas fica gigante.
|
|
|
|
Post by Alexandre Cezar on Jan 8, 2015 8:53:57 GMT -3
Também pensei nisso, mas pensei em $I_n \setminus I_i$ em vez do próprio $I_i$. (E considerei o conjunto vazio como sendo um $X$ que satisfaça à inequação)
Para mim isso parece apenas transformar o problema em outro.
Indo pelo lado que eu fui, chega-se na seguinte recursão:
Em $k = 0$, considere a lista formada apenas pelo elemento $n$.
Para um dado $k$ com lista $(x_1, x_2, ..., x_{2^k})$, a lista para $k+1$ é dada por:
$$(x_1, x_2, ..., x_{2^k}, x_1-(k+1), x_2-(k+1), ..., x_{2^k}-(k+1))$$
Ou seja, é a concatenação da lista normal, com a lista formada pela subtração de $k+1$ de cada elemento.
Assim a sequência de listas fica:
k = 0
$$n$$
k = 1
$$n, n-1$$
k = 2
$$n, n-1, n-2, n-3$$
k = 3
$$n, n-1, n-2, n-3, n-3, n-4, n-5, n-6$$
E assim por diante.
Daí a solução do problema é achar quantos elementos em $k = n$ são não negativos. O que é basicamente o mesmo problema. ;P
|
|
