Thread replies: 6
Thread images: 1
Thread images: 1
I know that the number of subsets of a set containing n elements is 2^n. But what is the maximum number of sets that can be created from these elements that none of them are a subset of another?
e.g I don't want to count set {1,2} if I count set {1,2,3}
>>
>>7957485
n + 1 for n sets each containing 1 element plus the null set?
>>
>>7957770
Null set is a subset of every set, so maybe not that.
n seems legit though, if you put any two elements in a set together then you'd lose the sets containing only the single elements.
>>
>>7957770
Null set doesn't count because it is a subset of all those singe element sets. Also, your answer is wrong. Consider {1,2,3,4} -> {1,2},{1,3},(1,4},{2,3},{2,4},{3,4}, which is more than the 4 single element sets.
Answer is n choose floor(n/2)
>>
>>7957485
maximize n choose x over x, calculating the derivative its at
[eqn] {n \choose x} \left(\psi (n-x+1) - \psi (x+1)\right) = 0[/eqn]
with psi the digamma function
This is satisfied when [math] H_{n-x} = H_{x} [/math], with H the harmonic functions.
Since x is positive and the harmonic function is monotonic for positive x, this is satisfied when n - x = x, or x = n/2.
so the answer is [math] n \choose n/2 [/math].
Thread posts: 6
Thread images: 1
Thread images: 1