# Determining the different number of subsets (counting, permutations, combinations)

Given that any fixed integer $n>0$, let $S=\{1,2,3,4,...,n\}$. Now a Red-Blue subset of $S$ is called $T$. Every element of $T$ is given a colour (either red or blue). For instance $\{17 (\text{red})\}, \{1 (\text{red}), 5 (\text{red})\}$ and $\{1(\text{red}),5(\text{blue})\}$ are $3$ different subsets of $S$.

Determine the number of different RB-coloured subsets of $S$.

First thing I did was look at the problem without the colour restrictions to find out how many different subsets I can have. The number of different I calculated was $2^n - 1$. The $-1$ is from subtracting the null set.

I'm not sure how to number of possibilities when the colour restrictions are introduced.

Also how would I go about determining the number of different subsets of size $i$, where $0<i<n$?

First thing to notice is that for a give subset size (we'll say there are $i$ elements of these subsets), there are $2^i$ different ways to color them.

For example, size 2:

$$(1_{red}, 5_{red}), (1_{red}, 5_{blue}), (1_{blue}, 5_{red}), (1_{blue}, 5_{blue})$$

Now we just need to find out how many subsets are of size $i$. Let's try building up from some examples:

For a set of size 0 there is 1 option: the null set (we will count this).

For the set of size 1 there are $n$ options. (One for each element of S).

For the set of size 2 there are $\dbinom{n}{2}$ ways. (See why?)

So in general, there are $\dbinom{n}{i}$ subsets of size $i$.

Now we need to add all of this up:

$$\sum_{i=0}^n \dbinom{n}{i}2^i = \sum_{i=0}^n \frac{n!}{i!(n-i)!}2^i$$

Edit: As kingW3 points out in the comments, this is equal to $3^n$ because of the binomial theorem:

$$\sum_{i=0}^n \dbinom{n}{i}2^i = \sum_{i=0}^n \dbinom{n}{i}1^{n-i}2^i = (1+2)^n = 3^n$$

• By the binomial theorem $$(1+2)^n=\sum_{i=0}^n{n\choose i}2^i$$,to verify :) – kingW3 Jul 7 '14 at 22:07
• Ah, yes! Thank you! – BeaumontTaz Jul 7 '14 at 22:12

Call the elements that are not in you red-blue subset white. Then you are just giving one of three colours to each of the $n$ elements, without any restriction (the question does not say that the subset must be proper, or non-empty, or that both colours must be used). So there are $3^n$ ways to do it.