Calculate all possible combinations of 1 to n variables taking 2 values

combinatorics

I am trying to calculate all possible combinations of n variables taking 2 values (1, 0) with the number of variables being allowed to vary between 1 and n. E.g.:

For 1 variable (A), the number is 2.

A
0
1

For 2 variables (A, B), the number is 8.

For 3 variables (A, B, C), I think the number is 26 (correct me if I am wrong).

I did the same exercise with 4 variables (A, B, C, D) and I came to 80 combinations (again, correct me if I am wrong). I will not list them here because the minimal illustration above should suffice.

I tried to find the formula giving the total number of possible combinations but I did not succeed. Could someone help me?

Best Answer

You have three choices for each of the $n$ variables: $0$, $1$, or omit. That would give you $3^n$ choices. However, in your lists, you are omitting the case where all omits occurs, which leaves you with $3^n - 1$ possible outcomes when you have $n$ variables.

Related Solutions

[Math] How many possible combinations of a HEX string

I think the sanest way to split this is by how many different letters and numbers is contained in the string. Call the total number of different symbols $k$. The possibilities are then:

k=5    1+4  2+3  3+2  4+1
k=6    1+5  2+4  3+3  4+2  5+1
k=7    1+6  2+5  3+4  4+3  5+2  6+1
k=8    1+7  2+6  3+5  4+4  5+3  6+2
k=9    1+8  2+7  3+6  4+5  5+4  6+3
k=10   1+9  2+8  3+7  4+6  5+5  6+4

For each of the 33 entries in the table, the number of ways to select which hex digit appear at all is a simple product of binomial coefficients.

From there each row of the table can be summed and treated uniformly. First select which $10-k$ of the $k$ symbols are going to appear twice, for a factor of $\binom{k}{10-k}$. Then multiply by $10!$ for the ways to arrange the symbols you have selected, and divide by $2^{10-k}$ to account for the fact that each pair of two equal symbols cannot be distinguished.

Combinatorics – Find the Total Possible Combinations of Three Variables

For each of the $2$ possible values of $A$ there are $3$ possible values of $B$; that makes $2\cdot 3=6$ possible combinations, as you can see by setting up a $2\times 3$ grid showing all $6$ combinations.

$$\begin{array}{|c|c|c|c|}\\ \hline &b_1&b_2&b_3\\ \hline a_1&(a_1,b_1)&(a_1,b_2)&(a_1,b_3)\\ \hline a_2&(a_2,b_1)&(a_2,b_2)&(a_2,b_3)\\ \hline \end{array}$$

Each of these $6$ combinations can in turn be combined with any of the $5$ possible values of $C$, so the same reasoning gives you a total of $6\cdot5=30$ combinations.

The general principle, sometimes called the multiplication or Chinese menu principle, is that if you have a sequence of $n$ choices to be made, and the $k$-th choice can be make in $m_k$ ways independently of the other choices, then the total number of ways to make the combined choice is $$m_1m_2m_3\dots m_n\;,$$ the product of the numbers of ways to make the individual choices.

Best Answer

Related Solutions

[Math] How many possible combinations of a HEX string

Combinatorics – Find the Total Possible Combinations of Three Variables

Related Question