Combinations of a set $\{x_1, x_2, ... , x_n\}$ of size less than or equal to $3$

Question

Sorry, this is rudimentary combinatorics but I wanted to make sure I was doing it right

Say I have a set of values $S=\{x_1,x_2, ... , x_n\}$ and I want to know how many different combinations of $1,2,3$ values there are. That would be

$$ \binom{n}{3}+\binom{n}{2}+\binom{n}{1} = \dfrac{n!}{3!(n-3)!}+\dfrac{n!}{2!(n-2)!}+\dfrac{n!}{1!(n-1)!} $$

which simplifies to

$$ \dfrac{1}{6}(n)(n-1)(n-2)+\dfrac{1}{2}(n)(n-1)+n=\dfrac{1}{6}(n^3+5n) $$

This I think I'm correct on. However now imagine each variable as a light switch that can be either "up" or "down". Let $x_k$ denote a variable that is down, and $x_k'$ denote one up. So now instead of just having combinations

$$ x_1, x_1x_2,x_1x_2x_3, ... $$

we can have

$$ x_1,x_1',x_1x_2,x_1'x_2,x_1x_2', ... $$

My gut instinct says that each variable now has two possibilities, so we can say that the total number of combinations now becomes

$$ 2^3\binom{n}{3}+2^2\binom{n}{2}+2\binom{n}{1} $$

But I wasn't sure.

Thank you!

Answer 1

Yes, you're right: each $n$-element subset now occurs $2^n$ times, once for every configuration of up/down of the $n$ elements. Thus you count an $n$-element subset $2^n$ times for the correct total.

Answer 2

Once you have chosen a configuration (such as $x_1 x_5 x_2$) you have independently $2\times 2\times 2$ ways to decorate it with primes.

Therefore you are correct, by the fundamental principle of counting.

This is, of course, assuming that you can't have words with both $x_i$ and $x_i'$ in them.