|
seja N = 2k + s, com s = {0, 1}
0) você pode formar um subconjunto vazio e outro
com 2k+s elementos
1) um subconjunto com 1 elemento, outro com
2k+s-1
...
i) um com i elementos e outro com
2k+s-i
se i > k estamos contando alguns subconjuntos
duas vezes,
logo pegamos i <= k
seja S a soma de i = 0 até k de
Cn,i
se N for ímpar, temos
2*S = 2^n => S = 2^(n-1)
ex.
{1, 2, 3}, S = 2^2 = 4
{},{1, 2, 3} ; {1},{2,3} ; {2},{1,3} ; {3},{1,2}
se N for par, temos
2*S + Cn,n/2 = 2^n
=>
2*S - n!/[(n/2)!]² = 2^n
S = 2^(n-1) + 0,5Cn,n/2
para N=4, temos S = 1 + 4 + 6 = 11 = 2^3 +
0,5*C4,2
|