1
$\begingroup$

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$
3
  • $\begingroup$ your intuition is right. Can you build a reasoning on that? $\endgroup$
    – sigmatau
    Jul 18, 2013 at 20:50
  • $\begingroup$ Perhaps because there's 2 possibilities for each variable, and n variables..? $\endgroup$
    – user66360
    Jul 18, 2013 at 20:55
  • $\begingroup$ yes. I posted an answer bellow that could help visualizing your intutition. $\endgroup$
    – sigmatau
    Jul 18, 2013 at 21:05

3 Answers 3

Reset to default
2
$\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:

http://commons.wikimedia.org/wiki/File:Binary_tree.png

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$ Ok now the fact the there are $2^n$ total possibilities makes sense. But let's say I want to know how many ways there are to have exactly 1, 2 or 3 ones. Then I assume for 1 one, there would just be n ways, that's easy. For 2 ones, perhaps there are $n^2$ ways. For three ones, $n^3$ ways. By this logic, there are $n^n$ ways to have n ones. Does that sound correct? $\endgroup$
    – user66360
    Jul 18, 2013 at 21:16
  • 1
    $\begingroup$ That's a bit more complicated to explain. The idea is that you have $(n-k)$ zeros and $k$ ones hence all together still $n$ elements. Now forming strings with exactly $k$ ones is the same as choosing $k$ ones out of $n$ elements wich can be done in $n \choose k$ ways. $\endgroup$
    – sigmatau
    Jul 18, 2013 at 22:18
  • $\begingroup$ So say n = 16. And I want to know how many ways I can have exactly 3 $x_i$s equal 1. Then I would do $\frac{16!}{(16-3)!}$ ? $\endgroup$
    – user66360
    Jul 18, 2013 at 23:00
  • 1
    $\begingroup$ it would be $16 \choose 3$ wich is $\frac{16!}{(16-3)!3!}$. $\endgroup$
    – sigmatau
    Jul 18, 2013 at 23:02
2
$\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$
1
$\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$

You must log in to answer this question.