2
$\begingroup$

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$?

$\endgroup$
1
$\begingroup$

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$$

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.