# Number of combinations for N elements with M states

I have $N$ elements:

$$e_1, e_2, e_3, e_4, ..., e_N$$

and each of them has $M$ possible states:

$$e_i:\, e_{i1}, e_{i2}, ..., e_{iM}$$

I need to find the total number of combinations of these $N$ elements assuming all of their states.

For example if $N=2$ & $M=3$, I have elements $e_{1}, e_{2}$ with states:

$$e_{11}, e_{12}, e_{13} \;\&\; e_{21}, e_{22}, e_{23}$$

for which there are 9 possible combinations in total:

$$e_{11}, e_{21} / e_{11}, e_{22} / e_{11}, e_{23} / e_{12}, e_{21} / e_{12}, e_{22} / e_{12}, e_{23} / e_{13}, e_{21} / e_{13}, e_{22} / e_{13}, e_{23}$$

Notice that the position is irrelevant, which is why I don't count $e_{21}, e_{11}$ as a different permutation from $e_{11}, e_{21}$.

I've tried with small numbers and I believe the answer is $M^N$, but I'm not sure how to prove this.

• Your presumption is right. – callculus Aug 4 '15 at 18:01

Consider the following set: $$S=\{(s_1,s_2,s_3, \ldots , s_{N}) \, | \, s_i \in \{e_{i1}, e_{i2}. \ldots ,e_{iM}\} \quad \text{ where } 1 \leq i \leq N\}.$$ Then the size of $S$ will give you all the possible states. Since each $s_i$ can be chosen in $M$ ways, therefore the number of such $N-$tuple vectors is $M^N$.
For the first object, there are $M$ possible states. For each of these states, we have $M$ possible states for the second object, giving a new total of $M \times M = M^2$ states. For each of these states, the third object has $M$ possible states, giving a new total of $M^2 \times M = M^3$. If we carry on with this process for all $N$ objects, we can easily see that the total number of states is given by $M^N$.