Pigeon Hole Principle: Six positive integers whose maximum is at most $14$

Question

I was reading this example from my textbook:

Let $S$ be a set of six positive integers whose maximum is at most $14$. Show that the sums of the elements in all the nonempty subsets of $S$ cannot all be distinct. For each nonempty subset $A$ of $S$ the sum of the elements in A denoted $S$ satisfies: $1 \leq S \leq 9 + 10 + 11 + 12 + 13 + 14 = 69 $

And then there are $2^6 - 1 = 63$ non empty subsets of $S$.

Could somebody please explain me the logic of $63$. How is this being calculated.

Thanks,

Rahul

Answer 1

Imagine the six integers as either being in the subset or not in the subset. Each integer can have 2 states. For a total of $2^6=64$ total states or subsets. Subtracting out the empty set, you are left with 63 subsets.

Answer 2

We denote the size, or cardinality, of $S$ by $|S|=6$. Now for any nonempty set $X$ there are $2^{|X|}$ subsets of $X$ in total, these include $X$ itself and the empty set $\varnothing$.

So for your set there are $2^{|S|}=2^6$ subsets of $S$ in total. Since the empty set $\varnothing$ is empty by definition you must subtract $1$ from $2^6$ to obtain the number of nonempty sets.