I have a system containing n variables. That is, the variables are $x_1$, $x_2$, ... , $x_n$. For all $x_i$, $x_i$ $\in$ {0,1}. How many different ways can one assign values to each $x_i$?
For example, one way is: 0, 0, ... , 0.
Another is 1, 1, ... , 1.
Another is 1, 0, 1, 0, ... , 1, 0.
My intuition says there are $2^n$ ways to assign these values, but I'm not quite sure why. Can someone help me out here?
Now let's take this a step further. Say I want to find out how many cases there are in which either one $x_i$ is 0, two $x_i$s are 0 or three $x_i$s are 0. Does that make sense? Any idea how to think on that?
$\endgroup$ 33 Answers
$\begingroup$Ok so you have a string of $n$ variables. Each variable can assume two values $\{ 0,1\}$. And your question is: How many different strings can we build ,right?
Your intuition is right and the answer is indeed $2^n$ but what could help understanding this result is drawing some trees, just to get started. Here is an example:
each edge brings you to a new combination. As you can easily see the possibilities for $1$ ,$2$, $3$ variables are $2$ , $4$ , $8$ respectively (since at each node you have the possibility of going left ,choosing $0$, or right , choosing $1$) or equivalently $2^1$ , $2^2$ , $2^3$ in accordance with your intuition.
The genral combinatorical rule is : If you have a string of $n$ variables each having possibility of assuming $x_n$ different values then the total number of different strings is given by :
$x_1 \cdot x_2 \cdot x_3 ... \cdot x_n$
In your special case: $x_1=x_2=x_3=...=x_n=2$
$\endgroup$ 4 $\begingroup$It is $2^n$. Assuming each $x_i$ can only be either 0 or 1.
If $x_1$ is either 0 or 1, then it has two different possibilities. Having a second combination $(x_1,x_2)$, each $x_i$ is either 0 or 1, then the different possible combinations are (0,1),(0,0),(1,1),(1,0) or $2^2$ of them.
Try a 3 digit combination: $(x_1,x_2,x_3)$ with each $x_i$ being 0 or 1. The different possible combinations are:(0,1,0),(0,0,0),(1,1,0),(1,0,0),(0,1,1),(0,0,1),(1,1,1),(1,0,1) or $2^3$ of them.
Now, imagine a combination $(x_1,x_2,.....,x_n)$ with each $x_i$ being 0 or 1 then the number of different possible combinations is $2^n$. Same thing.
Can you see the pattern now?
$\endgroup$ $\begingroup$Suppose that there are $b_n$ ways to assigning binary values to $x_1,\dots,x_n$. Now we add an $(n+1)$-st variable $x_{n+1}$. Each of the $b_n$ assignments of values to $x_1,\dots,x_n$ can be extended to two assignments of values to $x_1,\dots,x_{n+1}$: we can set $x_{n+1}$ to $0$ or to $1$. Thus, $b_{n+1}=2b_n$. And since $b_1=2$, ...
$\endgroup$
