Skip to main content
added 320 characters in body
Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

The sharp bound isIt does not exceed ${n\choose \lceil n/2\rceil}$ by Sperner's theorem (the subsets with the same sum are not contained one in another). On the other hand, if $n$ is even and we get $n$ copies of 2, we get exactly ${n\choose n/2}$ subsets with sum $n$, so the bound is tight. If $n$ is odd, we may take 1 and $(n-1)$ copies of 2 to get ${n-1\choose (n-1)/2}$ subsets with sum $n$, which is worse than the above upper bound approximately by a factor of 2.

The sharp bound is ${n\choose \lceil n/2\rceil}$ by Sperner's theorem (the subsets with the same sum are not contained one in another).

It does not exceed ${n\choose \lceil n/2\rceil}$ by Sperner's theorem (the subsets with the same sum are not contained one in another). On the other hand, if $n$ is even and we get $n$ copies of 2, we get exactly ${n\choose n/2}$ subsets with sum $n$, so the bound is tight. If $n$ is odd, we may take 1 and $(n-1)$ copies of 2 to get ${n-1\choose (n-1)/2}$ subsets with sum $n$, which is worse than the above upper bound approximately by a factor of 2.

Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

The sharp bound is ${n\choose \lceil n/2\rceil}$ by Sperner's theorem (the subsets with the same sum are not contained one in another).