I have $q$ unordered values, and I want to split them into 2 groups. How many possible splits are there? I know the answer is $2^{q-1}-1$, and I can verify cases that $p = 1,2,3$;but I do not know how does this derived.
I know this($q-1$ & $-1$) has some thing to do with the last value, but I am not sure how.
Consider the set $S = \{a_1, a_2, a_3, \ldots, a_q\}$. Each element is either in the same group as $a_1$ or it is not. There are $q - 1$ elements other than $a_1$. Since there are two choices for each of those $q - 1$ elements, there are $2^{q - 1}$ ways to place them in the two groups. However, if we place all $q - 1$ elements in the same group as $a_1$, we will only be left with one group. Thus, there are $2^{q - 1} - 1$ ways to divide the $q$ elements into two nonempty groups.